d3.ForceBundle

KO | EN

gitlite — search

#python #hacktoberfest #react #typescript #golang #go #android #docker #kubernetes #pytorch #security #ios #openai #mcp

(★ 284)

Force Directed Edge Bundling (FDEB) in Javascript; d3.js ready. (https://www.win.tue.nl/vis1/home/dholten/papers/forcebundles_eurovis.pdf)

파일 탐색기

최종 버전 다운로드 (.zip)

- - airlines.xml
  - migrations.xml
- airline_routes.html
- airline_graph.png
- airline_node_link_graph.png
- comp.png
- thumbnail.png
d3-ForceEdgeBundling.js
LICENSE
README.md

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# d3.ForceBundle

##### Javascript Force Edge Bundling for d3.js
![](https://raw.githubusercontent.com/upphiminn/d3.ForceBundle/master/readme_img/comp.png) 
---
## Description
#### Edge Bundling Algorithms (What Do They Do)
Node-link graphs with many edges and nodes suffer from visual clutter, edge-bundling algorithms transform and group the edges of a node-link graph in such a way as to improve the readability of the diagram. The process is for example analogous to bundling network cable wires along their route in order have a clear understanding of the links between entities and structural patterns of the network. There are several algorithms in this class, from ones that use hidden user-defined meshes to control the bundling **[1]**, to case specific ones such as for hierarchical data **[2]** and finally to self-organizing methods based on physical force interaction simulations **[3]**.
#### Force Edge Bundling
**Force edge bundling** **[3]** works by modelling edges between nodes as flexible springs which can attract each other if certain geometrical compatibility criterions are met. 
The input for the algorithm is a simple node-link diagram of a graph with nodes and edges. In order to change the shape of the basic straight line edges between nodes, the algorithm proceeds by subdividing edges into segments. Attraction *spring* forces are simulated between each pair of consecutive subdivision points on the same graph-edge. Moreover, attraction *electrostatic* forces are computed between subpoints of different edges which are geometrically compatible. The combined force acting on each subdivision point is computed and the points are moved a certain step size in the direction of the force. The force-simulation on these sub-points is repeted a certain amout of iterations. After the end of a cycle of iterations the resulting graph-edges are divided again in smaller segements and the whole process repeats itself until the end cycle is reached. It's important to note that the position of original node-points are fixed throughout the simulation.
#### Parameters Tuning
##### Fixed Parameters 
A certain number of parameters have been fixed to specific optimized values as found through experimentation by the authors. These include the spring constants **K** (=0.1), which controls the amount of bundling by controling the stiffness of edges. The number of iterations for simulating force interactions **I** (=60) and the number of cycles of subdivision-force simulation iterations **C** (=6). Moreover, the initial number of division points **P** is set to 1 and the rate at which it increases set to 2. The rate of the number of iterations **I** decreases each cycle is set to **2/3**.
All these parameters can be changed nonetheless if really needed by using the following methods:

- *bundling_stiffness ([new bundling stiffness: float value])*
- *iterations([new number of iterations to execute each cycle: int value])*
- *iterations_rate([new decrease rate for iteration number in each cycle: float value])*
- *cycles ([new number of cycles to execute: int value])*
- *subdivision_points_seed([new number subdivision points in first cycle: int value])*
- *subdivision_rate([new rate of subdivision each cycle: float value])*

##### Tuning Parameters For Your Specific Graph

Two parameters are **essential** for tuning the algorithm to produce usable diagrams for your graph. These are the geometric **compatibility score** above which pairs of edges should be considered compatible (default is set to 0.6, 60% compatiblity). The value provided should be between 0 and 1. Passing the new value to the  ***compatbility_threshold*** method will set the new threshold.

The **most important parameter** is the **initial step size** used to move the subdivision points after forces have been computed. This depends on both the scale of the graph and the number of edges and nodes contained. Having a step size which is too low will produce node-link like graphs while too high values will over distort edges. This can be set using the ***step_size*** function and passing your new step float size value. The default value is set to **0.1**.

## Usage
### Import The Plugin 
```html
	<script type="text/javascript" src="d3-ForceEdgeBundling.js"></script>
```
### Input Data
#### Node Data
The Nodes and their positions are stored by their id in a basic dictionary.
```javascript
var node_data = {
	"0": {"x":922.24444, "y":347.29444},
	"1": {"x":814.42222, "y":409.16111},
	"2": {"x":738, "y":427.33333000000005},
	"3": {"x":784.5, "y":381.33333},
	"4": {"x":1066.09167, "y":350.40278},
	"5": {"x":925.4861099999999, "y":313.275}
}
```
#### Edge Data
The edges are stored in an array, with each edge being represtend by an object with a *source* and *target* field. The id of the endpoints nodes are used as values. 
```javascript
var edge_data = [{"source":"0", "target":"1"}, {"source":"4", "target":"2"}, {"source":"0", "target":"3"}, {"source":"0","target":"4"}, {"source":"2", "target":"5"}, {"source":"3", "target":"2"}, {"source":"3", "target":"4"}]
```
	
### Output Data
The algorithm outputs an array of arrays of subdivision points obtained on the last cycle of the algorithm. For each initial edge we now have an array of subpoints. See dumbed-down example output below:
```javascript	
[
	[{"x":598.84446872426, "y":345.9168478350515},
	{"x":598.8966169857991, "y":342.6143388013737},
	{"x":598.9447663612947, "y":339.5650761251721},
	{"x":598.9889739987847, "y":336.00915574486953}],

[{"x":599.0255639503467, "y":332.7064433315037},
	{"x":599.0458427562561, "y":329.649667740391},
	{"x":599.0688393833738, "y":326.1832146974663},
	{"x":599.0815403651777, "y":322.79784918535125}],
		  
	[{"x":599.093286694284, "y":319.49494996957446},
	 {"x":599.0826911541287, "y":316.20380716501853},
	 {"x":599.0720260264579, "y":312.8891427199991},
	 {"x":599.0626270188833, "y":309.96251327852605}],
		  
	[{"x":599.0490564253139, "y":306.2833476821561},
	 {"x":599.0143146564005, "y":303.088731096524},
	 {"x":598.9769445742103, "y":299.67789993507586},
	 {"x":598.9402957673196, "y":296.5373242419396}]
]
```
### Running the algorithm
#### With Default Parameters Values:
```javascript
	var fbundling = d3.ForceEdgeBundling()
				.nodes(node_data)
				.edges(edge_data);
	var results   = fbundling();	
```

#### With Custom Parameters Values
```javascript
	var fbundling = d3.ForceEdgeBundling()
				.step_size(0.2)
				.compatibility_threshold(0.9)
				.nodes(node_data)
				.edges(edge_data);
	var results = fbundling();	  
```	
### How To Plot
Plotting can be done by using standard *d3* methods i.e. drawing lines between each of the subdivision subpoints for each the initial graph edges. Since there is no support for advanced blending modes in **SVG** yet we use the *stroke-opacity* to mark overlapping segments.
```javascript
	var d3line = d3.svg.line()
			.x(function(d){ return d.x; })
                        .y(function(d){ return d.y; })
                        .interpolate("linear");
                        
        results.forEach(function(edge_subpoint_data){	
        // for each of the arrays in the results 
        // draw a line between the subdivions points for that edge
        	svg.append("path")
        	.attr("d", d3line(edge_subpoint_data))
            	.style("stroke-width", 1)
            	.style("stroke", "#ff2222")
            	.style("fill", "none")
            	.style('stroke-opacity',0.15); //use opacity as blending
        });
```        
## Example
#### Live Demo
[Live Demo on bl.ocks.org](http://bl.ocks.org/upphiminn/6515478)

OR see source code in **example/airline_routes.html**.
##### Node-Link
![](https://raw.githubusercontent.com/upphiminn/d3.ForceBundle/master/readme_img/airline_node_link_graph.png) 
##### After FDEB 
![](https://raw.githubusercontent.com/upphiminn/d3.ForceBundle/master/readme_img/airline_graph.png)

## Future Extentions

- Barnes-Hut methods to optimize force calculations. 
- Use a color gradient to color edge subsegments with respect to number of overlapping subedges.
- Add edge smoothing support for subdivision points using a Gaussian kernels. 
- Automatical intialization with optimum step size with respect to given graph.

## Paper References

[1] Cui, Weiwei, et al. "Geometry-based edge clustering for graph visualization." Visualization and Computer Graphics, IEEE Transactions on 14.6 (2008): 1277-1284.

[2] Holten, Danny. "Hierarchical edge bundles: Visualization of adjacency relations in hierarchical data." Visualization and Computer Graphics, IEEE Transactions 12, no. 5 (2006): 741-748.

[3] Holten, Danny, and Jarke J. Van Wijk. "Force‐Directed Edge Bundling for Graph Visualization." Computer Graphics Forum (Blackwell Publishing Ltd) 28, no. 3 (2009): 983-990.

d3.ForceBundle

파일 탐색기

오늘의 추천 프로젝트

Was this content helpful?

Recent Feedback

d3.ForceBundle

파일 탐색기

오늘의 추천 프로젝트

Was this content helpful?

Recent Feedback

Download README