1 | let tarjanStronglyConnected = function() {
|
2 |
|
3 | let eles = this;
|
4 | let nodes = {};
|
5 | let index = 0;
|
6 | let components = [];
|
7 | let stack = [];
|
8 | let cut = eles.spawn(eles);
|
9 |
|
10 | const stronglyConnectedSearch = sourceNodeId => {
|
11 | stack.push(sourceNodeId);
|
12 | nodes[sourceNodeId] = {
|
13 | index : index,
|
14 | low : index++,
|
15 | explored : false
|
16 | };
|
17 |
|
18 | let connectedEdges = eles.getElementById(sourceNodeId)
|
19 | .connectedEdges()
|
20 | .intersection(eles);
|
21 |
|
22 | connectedEdges.forEach(edge => {
|
23 | let targetNodeId = edge.target().id();
|
24 | if (targetNodeId !== sourceNodeId) {
|
25 | if (!(targetNodeId in nodes)) {
|
26 | stronglyConnectedSearch(targetNodeId);
|
27 | }
|
28 | if (!(nodes[targetNodeId].explored)) {
|
29 | nodes[sourceNodeId].low = Math.min(nodes[sourceNodeId].low,
|
30 | nodes[targetNodeId].low);
|
31 | }
|
32 | }
|
33 | });
|
34 |
|
35 | if (nodes[sourceNodeId].index === nodes[sourceNodeId].low) {
|
36 | let componentNodes = eles.spawn();
|
37 | for (;;) {
|
38 | const nodeId = stack.pop();
|
39 | componentNodes.merge(eles.getElementById(nodeId));
|
40 | nodes[nodeId].low = nodes[sourceNodeId].index;
|
41 | nodes[nodeId].explored = true;
|
42 | if (nodeId === sourceNodeId) {
|
43 | break;
|
44 | }
|
45 | }
|
46 |
|
47 | let componentEdges = componentNodes.edgesWith(componentNodes);
|
48 | let component = componentNodes.merge(componentEdges);
|
49 | components.push(component);
|
50 | cut = cut.difference(component);
|
51 | }
|
52 | };
|
53 |
|
54 | eles.forEach(ele => {
|
55 | if (ele.isNode()) {
|
56 | let nodeId = ele.id();
|
57 | if (!(nodeId in nodes)) {
|
58 | stronglyConnectedSearch(nodeId);
|
59 | }
|
60 | }
|
61 | });
|
62 |
|
63 | return {
|
64 | cut,
|
65 | components
|
66 | };
|
67 |
|
68 | };
|
69 |
|
70 | export default {
|
71 | tarjanStronglyConnected,
|
72 | tsc: tarjanStronglyConnected,
|
73 | tscc: tarjanStronglyConnected,
|
74 | tarjanStronglyConnectedComponents: tarjanStronglyConnected
|
75 | };
|