Skip to content

Commit 9b168f9

Browse files
64json64json
committed
add UndirectedGraph
1 parent 22fcb4a commit 9b168f9

File tree

3 files changed

+138
-7
lines changed

3 files changed

+138
-7
lines changed

‎index.html

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -109,6 +109,7 @@ <h3>Reference</h3>
109109
<script src="js/ace/ace.js"></script>
110110
<script src="js/module/tracer.js"></script>
111111
<script src="js/module/directed_graph.js"></script>
112+
<script src="js/module/undirected_graph.js"></script>
112113
<script src="js/module/weighted_directed_graph.js"></script>
113114
<script src="js/module/array2d.js"></script>
114115
<script src="js/module/array1d.js"></script>

‎js/module/directed_graph.js

Lines changed: 6 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -68,8 +68,7 @@ DirectedGraphTracer.prototype = $.extend(true, Object.create(Tracer.prototype),
6868
root = root || 0;
6969
var maxDepth = -1;
7070

71-
var chk = [];
72-
for (var i = 0; i < G.length; i++) chk.push(false);
71+
var chk = new Array(G.length);
7372
var getDepth = function (node, depth) {
7473
if (chk[node]) throw "the given graph is not a tree because it forms a circuit";
7574
chk[node] = true;
@@ -233,6 +232,7 @@ DirectedGraphTracer.prototype = $.extend(true, Object.create(Tracer.prototype),
233232
color = defaultEdgeColor;
234233
break;
235234
}
235+
236236
return color;
237237
},
238238
drawLabel: function (node, context, settings) {
@@ -306,10 +306,10 @@ DirectedGraphTracer.prototype = $.extend(true, Object.create(Tracer.prototype),
306306
drawOnHover: function (node, context, settings, next) {
307307
var tracer = this;
308308

309+
context.setLineDash([5, 5]);
309310
var nodeIdx = node.id.substring(1);
310311
graph.edges().forEach(function (edge) {
311312
var ends = edge.id.substring(1).split("_");
312-
context.setLineDash([5, 5]);
313313
if (ends[0] == nodeIdx) {
314314
var color = '#0ff';
315315
var source = node;
@@ -331,12 +331,11 @@ var DirectedGraph = {
331331
random: function (N, ratio) {
332332
if (!N) N = 5;
333333
if (!ratio) ratio = .3;
334-
var G = [];
334+
var G = new Array(N);
335335
for (var i = 0; i < N; i++) {
336-
G.push([]);
336+
G[i] = new Array(N);
337337
for (var j = 0; j < N; j++) {
338-
if (i == j) G[i].push(0);
339-
else G[i].push((Math.random() * (1 / ratio) | 0) == 0 ? 1 : 0);
338+
if (i != j) G[i][j] = (Math.random() * (1 / ratio) | 0) == 0 ? 1 : 0;
340339
}
341340
}
342341
return G;

‎js/module/undirected_graph.js

Lines changed: 131 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,131 @@
1+
function UndirectedGraphTracer(module) {
2+
if (DirectedGraphTracer.call(this, module || UndirectedGraphTracer)) {
3+
UndirectedGraphTracer.prototype.init.call(this);
4+
return true;
5+
}
6+
return false;
7+
}
8+
9+
UndirectedGraphTracer.prototype = $.extend(true, Object.create(DirectedGraphTracer.prototype), {
10+
constructor: UndirectedGraphTracer,
11+
init: function () {
12+
var tracer = this;
13+
14+
s.settings({
15+
defaultEdgeType: 'def'
16+
});
17+
sigma.canvas.edges.def = function (edge, source, target, context, settings) {
18+
var color = tracer.getColor(edge, source, target, settings);
19+
tracer.drawEdge(edge, source, target, color, context, settings);
20+
};
21+
},
22+
_setData: function (G) {
23+
if (Tracer.prototype._setData.call(this, arguments)) return true;
24+
25+
graph.clear();
26+
var nodes = [];
27+
var edges = [];
28+
var unitAngle = 2 * Math.PI / G.length;
29+
var currentAngle = 0;
30+
for (var i = 0; i < G.length; i++) {
31+
currentAngle += unitAngle;
32+
nodes.push({
33+
id: this.n(i),
34+
label: '' + i,
35+
x: .5 + Math.sin(currentAngle) / 2,
36+
y: .5 + Math.cos(currentAngle) / 2,
37+
size: 1,
38+
color: this.color.default
39+
});
40+
}
41+
for (var i = 0; i < G.length; i++) {
42+
for (var j = 0; j <= i; j++) {
43+
if (G[i][j] || G[j][i]) {
44+
edges.push({
45+
id: this.e(i, j),
46+
source: this.n(i),
47+
target: this.n(j),
48+
color: this.color.default,
49+
size: 1
50+
});
51+
}
52+
}
53+
}
54+
55+
graph.read({
56+
nodes: nodes,
57+
edges: edges
58+
});
59+
s.camera.goTo({
60+
x: 0,
61+
y: 0,
62+
angle: 0,
63+
ratio: 1
64+
});
65+
this.refresh();
66+
67+
return false;
68+
},
69+
e: function (v1, v2) {
70+
if (v1 > v2) {
71+
var temp = v1;
72+
v1 = v2;
73+
v2 = temp;
74+
}
75+
return 'e' + v1 + '_' + v2;
76+
},
77+
drawOnHover: function (node, context, settings, next) {
78+
var tracer = this;
79+
80+
context.setLineDash([5, 5]);
81+
var nodeIdx = node.id.substring(1);
82+
graph.edges().forEach(function (edge) {
83+
var ends = edge.id.substring(1).split("_");
84+
if (ends[0] == nodeIdx) {
85+
var color = '#0ff';
86+
var source = node;
87+
var target = graph.nodes('n' + ends[1]);
88+
tracer.drawEdge(edge, source, target, color, context, settings);
89+
if (next) next(edge, source, target, color, context, settings);
90+
} else if (ends[1] == nodeIdx) {
91+
var color = '#0ff';
92+
var source = graph.nodes('n' + ends[0]);
93+
var target = node;
94+
tracer.drawEdge(edge, source, target, color, context, settings);
95+
if (next) next(edge, source, target, color, context, settings);
96+
}
97+
});
98+
},
99+
drawEdge: function (edge, source, target, color, context, settings) {
100+
var prefix = settings('prefix') || '',
101+
size = edge[prefix + 'size'] || 1;
102+
103+
context.strokeStyle = color;
104+
context.lineWidth = size;
105+
context.beginPath();
106+
context.moveTo(
107+
source[prefix + 'x'],
108+
source[prefix + 'y']
109+
);
110+
context.lineTo(
111+
target[prefix + 'x'],
112+
target[prefix + 'y']
113+
);
114+
context.stroke();
115+
}
116+
});
117+
118+
var UndirectedGraph = {
119+
random: function (N, ratio) {
120+
if (!N) N = 5;
121+
if (!ratio) ratio = .3;
122+
var G = new Array(N);
123+
for (var i = 0; i < N; i++) G[i] = new Array(N);
124+
for (var i = 0; i < N; i++) {
125+
for (var j = 0; j < N; j++) {
126+
if (i > j) G[i][j] = G[j][i] = (Math.random() * (1 / ratio) | 0) == 0 ? 1 : 0;
127+
}
128+
}
129+
return G;
130+
}
131+
};

0 commit comments

Comments
 (0)