1 | import * as util from '../util';
|
2 | import * as is from '../is';
|
3 | import cache from './cache-traversal-call';
|
4 |
|
5 | let elesfn = {};
|
6 |
|
7 |
|
8 |
|
9 |
|
10 | let defineDagExtremity = function( params ){
|
11 | return function dagExtremityImpl( selector ){
|
12 | let eles = this;
|
13 | let ret = [];
|
14 |
|
15 | for( let i = 0; i < eles.length; i++ ){
|
16 | let ele = eles[ i ];
|
17 | if( !ele.isNode() ){
|
18 | continue;
|
19 | }
|
20 |
|
21 | let disqualified = false;
|
22 | let edges = ele.connectedEdges();
|
23 |
|
24 | for( let j = 0; j < edges.length; j++ ){
|
25 | let edge = edges[j];
|
26 | let src = edge.source();
|
27 | let tgt = edge.target();
|
28 |
|
29 | if(
|
30 | ( params.noIncomingEdges && tgt === ele && src !== ele )
|
31 | || ( params.noOutgoingEdges && src === ele && tgt !== ele )
|
32 | ){
|
33 | disqualified = true;
|
34 | break;
|
35 | }
|
36 | }
|
37 |
|
38 | if( !disqualified ){
|
39 | ret.push( ele );
|
40 | }
|
41 | }
|
42 |
|
43 | return this.spawn( ret, true ).filter( selector );
|
44 | };
|
45 | };
|
46 |
|
47 | let defineDagOneHop = function( params ){
|
48 | return function( selector ){
|
49 | let eles = this;
|
50 | let oEles = [];
|
51 |
|
52 | for( let i = 0; i < eles.length; i++ ){
|
53 | let ele = eles[ i ];
|
54 |
|
55 | if( !ele.isNode() ){ continue; }
|
56 |
|
57 | let edges = ele.connectedEdges();
|
58 | for( let j = 0; j < edges.length; j++ ){
|
59 | let edge = edges[ j ];
|
60 | let src = edge.source();
|
61 | let tgt = edge.target();
|
62 |
|
63 | if( params.outgoing && src === ele ){
|
64 | oEles.push( edge );
|
65 | oEles.push( tgt );
|
66 | } else if( params.incoming && tgt === ele ){
|
67 | oEles.push( edge );
|
68 | oEles.push( src );
|
69 | }
|
70 | }
|
71 | }
|
72 |
|
73 | return this.spawn( oEles, true ).filter( selector );
|
74 | };
|
75 | };
|
76 |
|
77 | let defineDagAllHops = function( params ){
|
78 | return function( selector ){
|
79 | let eles = this;
|
80 | let sEles = [];
|
81 | let sElesIds = {};
|
82 |
|
83 | for( ;; ){
|
84 | let next = params.outgoing ? eles.outgoers() : eles.incomers();
|
85 |
|
86 | if( next.length === 0 ){ break; }
|
87 |
|
88 | let newNext = false;
|
89 | for( let i = 0; i < next.length; i++ ){
|
90 | let n = next[ i ];
|
91 | let nid = n.id();
|
92 |
|
93 | if( !sElesIds[ nid ] ){
|
94 | sElesIds[ nid ] = true;
|
95 | sEles.push( n );
|
96 | newNext = true;
|
97 | }
|
98 | }
|
99 |
|
100 | if( !newNext ){ break; }
|
101 |
|
102 | eles = next;
|
103 | }
|
104 |
|
105 | return this.spawn( sEles, true ).filter( selector );
|
106 | };
|
107 | };
|
108 |
|
109 | elesfn.clearTraversalCache = function( ){
|
110 | for( let i = 0; i < this.length; i++ ){
|
111 | this[i]._private.traversalCache = null;
|
112 | }
|
113 | };
|
114 |
|
115 | util.extend( elesfn, {
|
116 |
|
117 | roots: defineDagExtremity({ noIncomingEdges: true }),
|
118 |
|
119 |
|
120 | leaves: defineDagExtremity({ noOutgoingEdges: true }),
|
121 |
|
122 |
|
123 |
|
124 | outgoers: cache( defineDagOneHop({ outgoing: true }) , 'outgoers' ),
|
125 |
|
126 |
|
127 | successors: defineDagAllHops({ outgoing: true }),
|
128 |
|
129 |
|
130 |
|
131 | incomers: cache( defineDagOneHop({ incoming: true }), 'incomers' ),
|
132 |
|
133 |
|
134 | predecessors: defineDagAllHops({ incoming: true })
|
135 | } );
|
136 |
|
137 |
|
138 |
|
139 |
|
140 |
|
141 | util.extend( elesfn, {
|
142 | neighborhood: cache(function( selector ){
|
143 | let elements = [];
|
144 | let nodes = this.nodes();
|
145 |
|
146 | for( let i = 0; i < nodes.length; i++ ){
|
147 | let node = nodes[ i ];
|
148 | let connectedEdges = node.connectedEdges();
|
149 |
|
150 |
|
151 | for( let j = 0; j < connectedEdges.length; j++ ){
|
152 | let edge = connectedEdges[ j ];
|
153 | let src = edge.source();
|
154 | let tgt = edge.target();
|
155 | let otherNode = node === src ? tgt : src;
|
156 |
|
157 |
|
158 | if( otherNode.length > 0 ){
|
159 | elements.push( otherNode[0] );
|
160 | }
|
161 |
|
162 |
|
163 | elements.push( edge[0] );
|
164 | }
|
165 |
|
166 | }
|
167 |
|
168 | return ( this.spawn( elements, true ) ).filter( selector );
|
169 | }, 'neighborhood'),
|
170 |
|
171 | closedNeighborhood: function( selector ){
|
172 | return this.neighborhood().add( this ).filter( selector );
|
173 | },
|
174 |
|
175 | openNeighborhood: function( selector ){
|
176 | return this.neighborhood( selector );
|
177 | }
|
178 | } );
|
179 |
|
180 |
|
181 | elesfn.neighbourhood = elesfn.neighborhood;
|
182 | elesfn.closedNeighbourhood = elesfn.closedNeighborhood;
|
183 | elesfn.openNeighbourhood = elesfn.openNeighborhood;
|
184 |
|
185 |
|
186 |
|
187 |
|
188 | util.extend( elesfn, {
|
189 | source: cache(function sourceImpl( selector ){
|
190 | let ele = this[0];
|
191 | let src;
|
192 |
|
193 | if( ele ){
|
194 | src = ele._private.source || ele.cy().collection();
|
195 | }
|
196 |
|
197 | return src && selector ? src.filter( selector ) : src;
|
198 | }, 'source'),
|
199 |
|
200 | target: cache(function targetImpl( selector ){
|
201 | let ele = this[0];
|
202 | let tgt;
|
203 |
|
204 | if( ele ){
|
205 | tgt = ele._private.target || ele.cy().collection();
|
206 | }
|
207 |
|
208 | return tgt && selector ? tgt.filter( selector ) : tgt;
|
209 | }, 'target'),
|
210 |
|
211 | sources: defineSourceFunction( {
|
212 | attr: 'source'
|
213 | } ),
|
214 |
|
215 | targets: defineSourceFunction( {
|
216 | attr: 'target'
|
217 | } )
|
218 | } );
|
219 |
|
220 | function defineSourceFunction( params ){
|
221 | return function sourceImpl( selector ){
|
222 | let sources = [];
|
223 |
|
224 | for( let i = 0; i < this.length; i++ ){
|
225 | let ele = this[ i ];
|
226 | let src = ele._private[ params.attr ];
|
227 |
|
228 | if( src ){
|
229 | sources.push( src );
|
230 | }
|
231 | }
|
232 |
|
233 | return this.spawn( sources, true ).filter( selector );
|
234 | };
|
235 | }
|
236 |
|
237 | util.extend( elesfn, {
|
238 | edgesWith: cache( defineEdgesWithFunction(), 'edgesWith' ),
|
239 |
|
240 | edgesTo: cache( defineEdgesWithFunction( {
|
241 | thisIsSrc: true
|
242 | } ), 'edgesTo' )
|
243 | } );
|
244 |
|
245 | function defineEdgesWithFunction( params ){
|
246 |
|
247 | return function edgesWithImpl( otherNodes ){
|
248 | let elements = [];
|
249 | let cy = this._private.cy;
|
250 | let p = params || {};
|
251 |
|
252 |
|
253 | if( is.string( otherNodes ) ){
|
254 | otherNodes = cy.$( otherNodes );
|
255 | }
|
256 |
|
257 | for( let h = 0; h < otherNodes.length; h++ ){
|
258 | let edges = otherNodes[ h ]._private.edges;
|
259 |
|
260 | for( let i = 0; i < edges.length; i++ ){
|
261 | let edge = edges[ i ];
|
262 | let edgeData = edge._private.data;
|
263 | let thisToOther = this.hasElementWithId( edgeData.source ) && otherNodes.hasElementWithId( edgeData.target );
|
264 | let otherToThis = otherNodes.hasElementWithId( edgeData.source ) && this.hasElementWithId( edgeData.target );
|
265 | let edgeConnectsThisAndOther = thisToOther || otherToThis;
|
266 |
|
267 | if( !edgeConnectsThisAndOther ){ continue; }
|
268 |
|
269 | if( p.thisIsSrc || p.thisIsTgt ){
|
270 | if( p.thisIsSrc && !thisToOther ){ continue; }
|
271 |
|
272 | if( p.thisIsTgt && !otherToThis ){ continue; }
|
273 | }
|
274 |
|
275 | elements.push( edge );
|
276 | }
|
277 | }
|
278 |
|
279 | return this.spawn( elements, true );
|
280 | };
|
281 | }
|
282 |
|
283 | util.extend( elesfn, {
|
284 | connectedEdges: cache(function( selector ){
|
285 | let retEles = [];
|
286 |
|
287 | let eles = this;
|
288 | for( let i = 0; i < eles.length; i++ ){
|
289 | let node = eles[ i ];
|
290 | if( !node.isNode() ){ continue; }
|
291 |
|
292 | let edges = node._private.edges;
|
293 |
|
294 | for( let j = 0; j < edges.length; j++ ){
|
295 | let edge = edges[ j ];
|
296 | retEles.push( edge );
|
297 | }
|
298 | }
|
299 |
|
300 | return this.spawn( retEles, true ).filter( selector );
|
301 | }, 'connectedEdges'),
|
302 |
|
303 | connectedNodes: cache(function( selector ){
|
304 | let retEles = [];
|
305 |
|
306 | let eles = this;
|
307 | for( let i = 0; i < eles.length; i++ ){
|
308 | let edge = eles[ i ];
|
309 | if( !edge.isEdge() ){ continue; }
|
310 |
|
311 | retEles.push( edge.source()[0] );
|
312 | retEles.push( edge.target()[0] );
|
313 | }
|
314 |
|
315 | return this.spawn( retEles, true ).filter( selector );
|
316 | }, 'connectedNodes'),
|
317 |
|
318 | parallelEdges: cache( defineParallelEdgesFunction(), 'parallelEdges' ),
|
319 |
|
320 | codirectedEdges: cache( defineParallelEdgesFunction( {
|
321 | codirected: true
|
322 | } ), 'codirectedEdges' )
|
323 | } );
|
324 |
|
325 | function defineParallelEdgesFunction( params ){
|
326 | let defaults = {
|
327 | codirected: false
|
328 | };
|
329 | params = util.extend( {}, defaults, params );
|
330 |
|
331 | return function parallelEdgesImpl( selector ){
|
332 | let elements = [];
|
333 | let edges = this.edges();
|
334 | let p = params;
|
335 |
|
336 |
|
337 | for( let i = 0; i < edges.length; i++ ){
|
338 | let edge1 = edges[ i ];
|
339 | let edge1_p = edge1._private;
|
340 | let src1 = edge1_p.source;
|
341 | let srcid1 = src1._private.data.id;
|
342 | let tgtid1 = edge1_p.data.target;
|
343 | let srcEdges1 = src1._private.edges;
|
344 |
|
345 |
|
346 | for( let j = 0; j < srcEdges1.length; j++ ){
|
347 | let edge2 = srcEdges1[ j ];
|
348 | let edge2data = edge2._private.data;
|
349 | let tgtid2 = edge2data.target;
|
350 | let srcid2 = edge2data.source;
|
351 |
|
352 | let codirected = tgtid2 === tgtid1 && srcid2 === srcid1;
|
353 | let oppdirected = srcid1 === tgtid2 && tgtid1 === srcid2;
|
354 |
|
355 | if( (p.codirected && codirected) || (!p.codirected && (codirected || oppdirected)) ){
|
356 | elements.push( edge2 );
|
357 | }
|
358 | }
|
359 | }
|
360 |
|
361 | return this.spawn( elements, true ).filter( selector );
|
362 | };
|
363 |
|
364 | }
|
365 |
|
366 |
|
367 |
|
368 |
|
369 | util.extend( elesfn, {
|
370 | components: function(root){
|
371 | let self = this;
|
372 | let cy = self.cy();
|
373 | let visited = cy.collection();
|
374 | let unvisited = root == null ? self.nodes() : root.nodes();
|
375 | let components = [];
|
376 |
|
377 | if( root != null && unvisited.empty() ){
|
378 | unvisited = root.sources();
|
379 | }
|
380 |
|
381 | let visitInComponent = ( node, component ) => {
|
382 | visited.merge( node );
|
383 | unvisited.unmerge( node );
|
384 | component.merge( node );
|
385 | };
|
386 |
|
387 | if( unvisited.empty() ){ return self.spawn(); }
|
388 |
|
389 | do {
|
390 | let cmpt = cy.collection();
|
391 | components.push( cmpt );
|
392 |
|
393 | let root = unvisited[0];
|
394 | visitInComponent( root, cmpt );
|
395 |
|
396 | self.bfs({
|
397 | directed: false,
|
398 | roots: root,
|
399 | visit: v => visitInComponent( v, cmpt )
|
400 | } );
|
401 |
|
402 | cmpt.forEach(node => {
|
403 | node.connectedEdges().forEach(e => {
|
404 | if( self.has(e) && cmpt.has(e.source()) && cmpt.has(e.target()) ){
|
405 | cmpt.merge(e);
|
406 | }
|
407 | });
|
408 | });
|
409 |
|
410 | } while( unvisited.length > 0 );
|
411 |
|
412 | return components;
|
413 | },
|
414 |
|
415 | component: function(){
|
416 | let ele = this[0];
|
417 |
|
418 | return ele.cy().mutableElements().components( ele )[0];
|
419 | }
|
420 | } );
|
421 |
|
422 | elesfn.componentsOf = elesfn.components;
|
423 |
|
424 | export default elesfn;
|