1 | import * as is from '../../is';
|
2 | import { defaults } from '../../util';
|
3 |
|
4 | const floydWarshallDefaults = defaults({
|
5 | weight: edge => 1,
|
6 | directed: false
|
7 | });
|
8 |
|
9 | let elesfn = ({
|
10 |
|
11 |
|
12 | floydWarshall: function( options ){
|
13 | let cy = this.cy();
|
14 |
|
15 | let { weight, directed } = floydWarshallDefaults(options);
|
16 | let weightFn = weight;
|
17 |
|
18 | let { nodes, edges } = this.byGroup();
|
19 |
|
20 | let N = nodes.length;
|
21 | let Nsq = N * N;
|
22 |
|
23 | let indexOf = node => nodes.indexOf(node);
|
24 | let atIndex = i => nodes[i];
|
25 |
|
26 |
|
27 | let dist = new Array(Nsq);
|
28 | for( let n = 0; n < Nsq; n++ ){
|
29 | let j = n % N;
|
30 | let i = (n - j) / N;
|
31 |
|
32 | if( i === j ){
|
33 | dist[n] = 0;
|
34 | } else {
|
35 | dist[n] = Infinity;
|
36 | }
|
37 | }
|
38 |
|
39 |
|
40 |
|
41 | let next = new Array(Nsq);
|
42 | let edgeNext = new Array(Nsq);
|
43 |
|
44 |
|
45 | for( let i = 0; i < edges.length; i++ ){
|
46 | let edge = edges[i];
|
47 | let src = edge.source()[0];
|
48 | let tgt = edge.target()[0];
|
49 |
|
50 | if( src === tgt ){ continue; }
|
51 |
|
52 | let s = indexOf( src );
|
53 | let t = indexOf( tgt );
|
54 | let st = s * N + t;
|
55 | let weight = weightFn( edge );
|
56 |
|
57 |
|
58 | if( dist[st] > weight ){
|
59 | dist[st] = weight;
|
60 | next[st] = t;
|
61 | edgeNext[st] = edge;
|
62 | }
|
63 |
|
64 |
|
65 | if( !directed ){
|
66 | let ts = t * N + s;
|
67 |
|
68 | if( !directed && dist[ts] > weight ){
|
69 | dist[ts] = weight;
|
70 | next[ts] = s;
|
71 | edgeNext[ts] = edge;
|
72 | }
|
73 | }
|
74 | }
|
75 |
|
76 |
|
77 | for( let k = 0; k < N; k++ ){
|
78 |
|
79 | for( let i = 0; i < N; i++ ){
|
80 | let ik = i * N + k;
|
81 |
|
82 | for( let j = 0; j < N; j++ ){
|
83 | let ij = i * N + j;
|
84 | let kj = k * N + j;
|
85 |
|
86 | if( dist[ik] + dist[kj] < dist[ij] ){
|
87 | dist[ij] = dist[ik] + dist[kj];
|
88 | next[ij] = next[ik];
|
89 | }
|
90 | }
|
91 | }
|
92 | }
|
93 |
|
94 | let getArgEle = ele => ( is.string(ele) ? cy.filter(ele) : ele )[0];
|
95 | let indexOfArgEle = ele => indexOf(getArgEle(ele));
|
96 |
|
97 | let res = {
|
98 | distance: function( from, to ){
|
99 | let i = indexOfArgEle(from);
|
100 | let j = indexOfArgEle(to);
|
101 |
|
102 | return dist[ i * N + j ];
|
103 | },
|
104 |
|
105 | path: function( from, to ){
|
106 | let i = indexOfArgEle(from);
|
107 | let j = indexOfArgEle(to);
|
108 |
|
109 | let fromNode = atIndex(i);
|
110 |
|
111 | if( i === j ){ return fromNode.collection(); }
|
112 |
|
113 | if( next[i * N + j] == null ){ return cy.collection(); }
|
114 |
|
115 | let path = cy.collection();
|
116 | let prev = i;
|
117 | let edge;
|
118 |
|
119 | path.merge( fromNode );
|
120 |
|
121 | while( i !== j ){
|
122 | prev = i;
|
123 | i = next[i * N + j];
|
124 | edge = edgeNext[prev * N + i];
|
125 |
|
126 | path.merge( edge );
|
127 | path.merge( atIndex(i) );
|
128 | }
|
129 |
|
130 | return path;
|
131 | }
|
132 | };
|
133 |
|
134 | return res;
|
135 |
|
136 | }
|
137 |
|
138 | });
|
139 |
|
140 | export default elesfn;
|