Skip to content

Commit ced7b72

Browse files
mbostockmbostock
committed
Better force-directed layout.
Use the Floyd-Warshall algorithm to compute the shortest path between nodes, and use that graph theoretic distance as the distance constraint for the Gauss- Seidel relaxation. In addition, have the constraint alpha decay over time, as in Simulated Annealing.
1 parent 1d9ed5a commit ced7b72

4 files changed

Lines changed: 80 additions & 79 deletions

File tree

‎examples/force/cluster.html‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -178,6 +178,7 @@
178178
var m = d3.svg.mouse(vis[0][0]);
179179
active.x = m[0];
180180
active.y = m[1];
181+
force.resume(); // restart annealing
181182
});
182183

183184
return false;
@@ -221,8 +222,7 @@
221222
.nodes(net.nodes)
222223
.links(net.links)
223224
.size({x: w, y: h})
224-
.nodeDistance(100)
225-
.linkDistance(60)
225+
.distance(60)
226226
.start();
227227

228228
hullg.selectAll("path.hull").remove();

‎examples/force/force.css‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,9 @@
11
circle.node {
2-
fill: lightsteelblue;
3-
stroke: steelblue;
2+
stroke: #fff;
43
stroke-width: 1.5px;
54
}
65

76
line.link {
8-
stroke: #333;
7+
stroke: #999;
8+
stroke-opacity: .6;
99
}

‎examples/force/force.js‎

Lines changed: 4 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,6 @@
11
var w = 960,
2-
h = 500;
2+
h = 500,
3+
fill = d3.scale.category20();
34

45
var vis = d3.select("#chart")
56
.append("svg:svg")
@@ -28,7 +29,8 @@ d3.json("miserables.json", function(json) {
2829
.attr("class", "node")
2930
.attr("cx", function(d) { return d.x; })
3031
.attr("cy", function(d) { return d.y; })
31-
.attr("r", 4.5);
32+
.attr("r", 5)
33+
.style("fill", function(d) { return fill(d.group); });
3234

3335
vis.attr("opacity", 0)
3436
.transition()

‎examples/force/layout.js‎

Lines changed: 71 additions & 72 deletions
Original file line numberDiff line numberDiff line change
@@ -3,85 +3,53 @@ function layout_force() {
33
var force = {},
44
event = d3.dispatch("tick"),
55
size = {x: 1, y: 1},
6-
alpha = .1,
7-
nodeDistance = 60,
8-
linkDistance = 30,
6+
alpha = .5,
7+
distance = 30,
98
interval,
109
nodes,
11-
links;
12-
13-
// TODO
14-
// slow the interval as the graph stabilizes
15-
// allow the nodes to be dragged interactively
10+
links,
11+
distances;
1612

1713
function tick() {
18-
var n = nodes.length,
19-
m = links.length,
14+
var n = distances.length,
2015
i, // current index
21-
j, // current index
2216
o, // current link
2317
s, // current source
2418
t, // current target
2519
l, // current distance
26-
x,
27-
y;
20+
x, // x-distance
21+
y; // y-distance
2822

29-
// repel nodes
23+
// gauss-seidel relaxation
3024
for (i = 0; i < n; ++i) {
31-
s = nodes[i];
32-
for (j = i + 1; j < n; ++j) {
33-
t = nodes[j];
34-
x = t.x - s.x;
35-
y = t.y - s.y;
36-
l = Math.sqrt(x * x + y * y);
37-
if (l < nodeDistance) {
38-
l = alpha * (l - nodeDistance) / l;
39-
x *= l;
40-
y *= l;
41-
if (s.fixed) {
42-
if (t.fixed) continue;
43-
t.x -= x;
44-
t.y -= y;
45-
} else if (t.fixed) {
46-
s.x += x;
47-
s.y += y;
48-
} else {
49-
s.x += x;
50-
s.y += y;
51-
t.x -= x;
52-
t.y -= y;
53-
}
54-
}
55-
}
56-
}
57-
58-
// position constraint for links
59-
for (i = 0; i < m; ++i) {
60-
o = links[i];
25+
o = distances[i];
6126
s = o.source;
6227
t = o.target;
6328
x = t.x - s.x;
6429
y = t.y - s.y;
65-
l = Math.sqrt(x * x + y * y);
66-
if (l <= 0) l = 0.01;
67-
l = alpha * (l - linkDistance) / l;
68-
x *= l;
69-
y *= l;
70-
if (s.fixed) {
71-
if (t.fixed) continue;
72-
t.x -= x;
73-
t.y -= y;
74-
} else if (t.fixed) {
75-
s.x += x;
76-
s.y += y;
77-
} else {
78-
s.x += x;
79-
s.y += y;
80-
t.x -= x;
81-
t.y -= y;
30+
if (l = Math.sqrt(x * x + y * y)) {
31+
l = alpha / (o.distance * o.distance) * (l - distance * o.distance) / l;
32+
x *= l;
33+
y *= l;
34+
if (s.fixed) {
35+
if (t.fixed) continue;
36+
t.x -= x;
37+
t.y -= y;
38+
} else if (t.fixed) {
39+
s.x += x;
40+
s.y += y;
41+
} else {
42+
s.x += x;
43+
s.y += y;
44+
t.x -= x;
45+
t.y -= y;
46+
}
8247
}
8348
}
8449

50+
// simulated annealing, basically
51+
if ((alpha *= .99) < 1e-6) force.stop();
52+
8553
event.tick.dispatch({type: "tick"});
8654
}
8755

@@ -108,44 +76,75 @@ function layout_force() {
10876
return force;
10977
};
11078

111-
force.nodeDistance = function(d) {
112-
if (!arguments.length) return nodeDistance;
113-
nodeDistance = d;
114-
return force;
115-
};
116-
117-
force.linkDistance = function(d) {
118-
if (!arguments.length) return linkDistance;
119-
linkDistance = d;
79+
force.distance = function(d) {
80+
if (!arguments.length) return distance;
81+
distance = d;
12082
return force;
12183
};
12284

12385
force.start = function() {
12486
var i,
87+
j,
88+
k,
12589
n = nodes.length,
12690
m = links.length,
12791
w = size.x,
12892
h = size.y,
12993
o;
94+
95+
var paths = [];
13096
for (i = 0; i < n; ++i) {
13197
o = nodes[i];
13298
o.x = o.x || Math.random() * w;
13399
o.y = o.y || Math.random() * h;
134100
o.fixed = 0;
101+
paths[i] = [];
102+
for (j = 0; j < n; ++j) {
103+
paths[i][j] = Infinity;
104+
}
105+
paths[i][i] = 0;
135106
}
107+
136108
for (i = 0; i < m; ++i) {
137109
o = links[i];
110+
paths[o.source][o.target] = 1;
111+
paths[o.target][o.source] = 1;
138112
o.source = nodes[o.source];
139113
o.target = nodes[o.target];
140114
}
115+
116+
// Floyd-Warshall
117+
for (k = 0; k < n; ++k) {
118+
for (i = 0; i < n; ++i) {
119+
for (j = 0; j < n; ++j) {
120+
paths[i][j] = Math.min(paths[i][j], paths[i][k] + paths[k][j]);
121+
}
122+
}
123+
}
124+
125+
distances = [];
126+
for (i = 0; i < n; ++i) {
127+
for (j = i + 1; j < n; ++j) {
128+
distances.push({
129+
source: nodes[i],
130+
target: nodes[j],
131+
distance: paths[i][j] * paths[i][j]
132+
});
133+
}
134+
}
135+
136+
distances.sort(function(a, b) {
137+
return a.distance - b.distance;
138+
});
139+
141140
if (interval) clearInterval(interval);
142141
interval = setInterval(tick, 24);
143142
return force;
144143
};
145144

146145
force.resume = function() {
147-
if (interval) clearInterval(interval);
148-
interval = setInterval(tick, 24);
146+
alpha = .1;
147+
if (!interval) interval = setInterval(tick, 24);
149148
return force;
150149
};
151150

0 commit comments

Comments
 (0)