1 | import { error } from '../../util';
|
2 |
|
3 | const sqrt2 = Math.sqrt(2);
|
4 |
|
5 |
|
6 |
|
7 |
|
8 | const collapse = function( edgeIndex, nodeMap, remainingEdges ){
|
9 | if( remainingEdges.length === 0 ){
|
10 | error(`Karger-Stein must be run on a connected (sub)graph`);
|
11 | }
|
12 |
|
13 | let edgeInfo = remainingEdges[ edgeIndex ];
|
14 | let sourceIn = edgeInfo[1];
|
15 | let targetIn = edgeInfo[2];
|
16 | let partition1 = nodeMap[ sourceIn ];
|
17 | let partition2 = nodeMap[ targetIn ];
|
18 | let newEdges = remainingEdges;
|
19 |
|
20 |
|
21 | for( let i = newEdges.length - 1; i >=0; i-- ){
|
22 | let edge = newEdges[i];
|
23 | let src = edge[1];
|
24 | let tgt = edge[2];
|
25 |
|
26 | if(
|
27 | ( nodeMap[ src ] === partition1 && nodeMap[ tgt ] === partition2 ) ||
|
28 | ( nodeMap[ src ] === partition2 && nodeMap[ tgt ] === partition1 )
|
29 | ){
|
30 | newEdges.splice(i, 1);
|
31 | }
|
32 | }
|
33 |
|
34 |
|
35 | for( let i = 0; i < newEdges.length; i++ ){
|
36 | let edge = newEdges[i];
|
37 |
|
38 | if( edge[1] === partition2 ){
|
39 | newEdges[i] = edge.slice();
|
40 | newEdges[i][1] = partition1;
|
41 | } else if( edge[2] === partition2 ){
|
42 | newEdges[i] = edge.slice();
|
43 | newEdges[i][2] = partition1;
|
44 | }
|
45 | }
|
46 |
|
47 |
|
48 | for( let i = 0; i < nodeMap.length; i++ ){
|
49 | if( nodeMap[i] === partition2 ){
|
50 | nodeMap[i] = partition1;
|
51 | }
|
52 | }
|
53 |
|
54 | return newEdges;
|
55 | };
|
56 |
|
57 |
|
58 | const contractUntil = function( metaNodeMap, remainingEdges, size, sizeLimit ){
|
59 | while( size > sizeLimit ){
|
60 |
|
61 | let edgeIndex = Math.floor( (Math.random() * remainingEdges.length) );
|
62 |
|
63 |
|
64 | remainingEdges = collapse( edgeIndex, metaNodeMap, remainingEdges );
|
65 |
|
66 | size--;
|
67 | }
|
68 |
|
69 | return remainingEdges;
|
70 | };
|
71 |
|
72 | const elesfn = ({
|
73 |
|
74 |
|
75 |
|
76 | kargerStein: function(){
|
77 | let { nodes, edges } = this.byGroup();
|
78 | edges.unmergeBy(edge => edge.isLoop());
|
79 |
|
80 | let numNodes = nodes.length;
|
81 | let numEdges = edges.length;
|
82 | let numIter = Math.ceil( Math.pow( Math.log( numNodes ) / Math.LN2, 2 ) );
|
83 | let stopSize = Math.floor( numNodes / sqrt2 );
|
84 |
|
85 | if( numNodes < 2 ){
|
86 | error( 'At least 2 nodes are required for Karger-Stein algorithm' );
|
87 | return undefined;
|
88 | }
|
89 |
|
90 |
|
91 |
|
92 | let edgeIndexes = [];
|
93 | for( let i = 0; i < numEdges; i++ ){
|
94 | let e = edges[ i ];
|
95 | edgeIndexes.push([ i, nodes.indexOf(e.source()), nodes.indexOf(e.target()) ]);
|
96 | }
|
97 |
|
98 |
|
99 | let minCutSize = Infinity;
|
100 | let minCutEdgeIndexes = [];
|
101 | let minCutNodeMap = new Array(numNodes);
|
102 |
|
103 |
|
104 | let metaNodeMap = new Array(numNodes);
|
105 | let metaNodeMap2 = new Array(numNodes);
|
106 |
|
107 | let copyNodesMap = (from, to) => {
|
108 | for( let i = 0; i < numNodes; i++ ){
|
109 | to[i] = from[i];
|
110 | }
|
111 | };
|
112 |
|
113 |
|
114 | for( let iter = 0; iter <= numIter; iter++ ){
|
115 |
|
116 | for( let i = 0; i < numNodes; i++ ){ metaNodeMap[i] = i; }
|
117 |
|
118 |
|
119 | let edgesState = contractUntil( metaNodeMap, edgeIndexes.slice(), numNodes, stopSize );
|
120 | let edgesState2 = edgesState.slice();
|
121 |
|
122 |
|
123 | copyNodesMap(metaNodeMap, metaNodeMap2);
|
124 |
|
125 |
|
126 | let res1 = contractUntil( metaNodeMap, edgesState, stopSize, 2 );
|
127 | let res2 = contractUntil( metaNodeMap2, edgesState2, stopSize, 2 );
|
128 |
|
129 |
|
130 | if( res1.length <= res2.length && res1.length < minCutSize ){
|
131 | minCutSize = res1.length;
|
132 | minCutEdgeIndexes = res1;
|
133 | copyNodesMap(metaNodeMap, minCutNodeMap);
|
134 | } else if( res2.length <= res1.length && res2.length < minCutSize ){
|
135 | minCutSize = res2.length;
|
136 | minCutEdgeIndexes = res2;
|
137 | copyNodesMap(metaNodeMap2, minCutNodeMap);
|
138 | }
|
139 | }
|
140 |
|
141 |
|
142 |
|
143 | let cut = this.spawn( minCutEdgeIndexes.map(e => edges[e[0]]) );
|
144 | let partition1 = this.spawn();
|
145 | let partition2 = this.spawn();
|
146 |
|
147 |
|
148 | let witnessNodePartition = minCutNodeMap[0];
|
149 | for( let i = 0; i < minCutNodeMap.length; i++ ){
|
150 | let partitionId = minCutNodeMap[i];
|
151 | let node = nodes[i];
|
152 |
|
153 | if( partitionId === witnessNodePartition ){
|
154 | partition1.merge( node );
|
155 | } else {
|
156 | partition2.merge( node );
|
157 | }
|
158 | }
|
159 |
|
160 |
|
161 | const constructComponent = (subset) => {
|
162 | const component = this.spawn();
|
163 |
|
164 | subset.forEach(node => {
|
165 | component.merge(node);
|
166 |
|
167 | node.connectedEdges().forEach(edge => {
|
168 |
|
169 | if (this.contains(edge) && !cut.contains(edge)) {
|
170 | component.merge(edge);
|
171 | }
|
172 | });
|
173 | });
|
174 |
|
175 | return component;
|
176 | };
|
177 |
|
178 | const components = [
|
179 | constructComponent(partition1),
|
180 | constructComponent(partition2)
|
181 | ];
|
182 |
|
183 | let ret = {
|
184 | cut,
|
185 | components,
|
186 |
|
187 |
|
188 |
|
189 | partition1,
|
190 | partition2
|
191 | };
|
192 |
|
193 | return ret;
|
194 | }
|
195 | });
|
196 |
|
197 |
|
198 | export default elesfn;
|