Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/cycles.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """ | |
2 ======================== | |
3 Cycle finding algorithms | |
4 ======================== | |
5 """ | |
6 | |
7 from collections import defaultdict | |
8 | |
9 import networkx as nx | |
10 from networkx.utils import not_implemented_for, pairwise | |
11 | |
12 __all__ = [ | |
13 "cycle_basis", | |
14 "simple_cycles", | |
15 "recursive_simple_cycles", | |
16 "find_cycle", | |
17 "minimum_cycle_basis", | |
18 ] | |
19 | |
20 | |
21 @not_implemented_for("directed") | |
22 @not_implemented_for("multigraph") | |
23 def cycle_basis(G, root=None): | |
24 """ Returns a list of cycles which form a basis for cycles of G. | |
25 | |
26 A basis for cycles of a network is a minimal collection of | |
27 cycles such that any cycle in the network can be written | |
28 as a sum of cycles in the basis. Here summation of cycles | |
29 is defined as "exclusive or" of the edges. Cycle bases are | |
30 useful, e.g. when deriving equations for electric circuits | |
31 using Kirchhoff's Laws. | |
32 | |
33 Parameters | |
34 ---------- | |
35 G : NetworkX Graph | |
36 root : node, optional | |
37 Specify starting node for basis. | |
38 | |
39 Returns | |
40 ------- | |
41 A list of cycle lists. Each cycle list is a list of nodes | |
42 which forms a cycle (loop) in G. | |
43 | |
44 Examples | |
45 -------- | |
46 >>> G = nx.Graph() | |
47 >>> nx.add_cycle(G, [0, 1, 2, 3]) | |
48 >>> nx.add_cycle(G, [0, 3, 4, 5]) | |
49 >>> print(nx.cycle_basis(G, 0)) | |
50 [[3, 4, 5, 0], [1, 2, 3, 0]] | |
51 | |
52 Notes | |
53 ----- | |
54 This is adapted from algorithm CACM 491 [1]_. | |
55 | |
56 References | |
57 ---------- | |
58 .. [1] Paton, K. An algorithm for finding a fundamental set of | |
59 cycles of a graph. Comm. ACM 12, 9 (Sept 1969), 514-518. | |
60 | |
61 See Also | |
62 -------- | |
63 simple_cycles | |
64 """ | |
65 gnodes = set(G.nodes()) | |
66 cycles = [] | |
67 while gnodes: # loop over connected components | |
68 if root is None: | |
69 root = gnodes.pop() | |
70 stack = [root] | |
71 pred = {root: root} | |
72 used = {root: set()} | |
73 while stack: # walk the spanning tree finding cycles | |
74 z = stack.pop() # use last-in so cycles easier to find | |
75 zused = used[z] | |
76 for nbr in G[z]: | |
77 if nbr not in used: # new node | |
78 pred[nbr] = z | |
79 stack.append(nbr) | |
80 used[nbr] = {z} | |
81 elif nbr == z: # self loops | |
82 cycles.append([z]) | |
83 elif nbr not in zused: # found a cycle | |
84 pn = used[nbr] | |
85 cycle = [nbr, z] | |
86 p = pred[z] | |
87 while p not in pn: | |
88 cycle.append(p) | |
89 p = pred[p] | |
90 cycle.append(p) | |
91 cycles.append(cycle) | |
92 used[nbr].add(z) | |
93 gnodes -= set(pred) | |
94 root = None | |
95 return cycles | |
96 | |
97 | |
98 @not_implemented_for("undirected") | |
99 def simple_cycles(G): | |
100 """Find simple cycles (elementary circuits) of a directed graph. | |
101 | |
102 A `simple cycle`, or `elementary circuit`, is a closed path where | |
103 no node appears twice. Two elementary circuits are distinct if they | |
104 are not cyclic permutations of each other. | |
105 | |
106 This is a nonrecursive, iterator/generator version of Johnson's | |
107 algorithm [1]_. There may be better algorithms for some cases [2]_ [3]_. | |
108 | |
109 Parameters | |
110 ---------- | |
111 G : NetworkX DiGraph | |
112 A directed graph | |
113 | |
114 Returns | |
115 ------- | |
116 cycle_generator: generator | |
117 A generator that produces elementary cycles of the graph. | |
118 Each cycle is represented by a list of nodes along the cycle. | |
119 | |
120 Examples | |
121 -------- | |
122 >>> edges = [(0, 0), (0, 1), (0, 2), (1, 2), (2, 0), (2, 1), (2, 2)] | |
123 >>> G = nx.DiGraph(edges) | |
124 >>> len(list(nx.simple_cycles(G))) | |
125 5 | |
126 | |
127 To filter the cycles so that they don't include certain nodes or edges, | |
128 copy your graph and eliminate those nodes or edges before calling | |
129 | |
130 >>> copyG = G.copy() | |
131 >>> copyG.remove_nodes_from([1]) | |
132 >>> copyG.remove_edges_from([(0, 1)]) | |
133 >>> len(list(nx.simple_cycles(copyG))) | |
134 3 | |
135 | |
136 | |
137 Notes | |
138 ----- | |
139 The implementation follows pp. 79-80 in [1]_. | |
140 | |
141 The time complexity is $O((n+e)(c+1))$ for $n$ nodes, $e$ edges and $c$ | |
142 elementary circuits. | |
143 | |
144 References | |
145 ---------- | |
146 .. [1] Finding all the elementary circuits of a directed graph. | |
147 D. B. Johnson, SIAM Journal on Computing 4, no. 1, 77-84, 1975. | |
148 https://doi.org/10.1137/0204007 | |
149 .. [2] Enumerating the cycles of a digraph: a new preprocessing strategy. | |
150 G. Loizou and P. Thanish, Information Sciences, v. 27, 163-182, 1982. | |
151 .. [3] A search strategy for the elementary cycles of a directed graph. | |
152 J.L. Szwarcfiter and P.E. Lauer, BIT NUMERICAL MATHEMATICS, | |
153 v. 16, no. 2, 192-204, 1976. | |
154 | |
155 See Also | |
156 -------- | |
157 cycle_basis | |
158 """ | |
159 | |
160 def _unblock(thisnode, blocked, B): | |
161 stack = {thisnode} | |
162 while stack: | |
163 node = stack.pop() | |
164 if node in blocked: | |
165 blocked.remove(node) | |
166 stack.update(B[node]) | |
167 B[node].clear() | |
168 | |
169 # Johnson's algorithm requires some ordering of the nodes. | |
170 # We assign the arbitrary ordering given by the strongly connected comps | |
171 # There is no need to track the ordering as each node removed as processed. | |
172 # Also we save the actual graph so we can mutate it. We only take the | |
173 # edges because we do not want to copy edge and node attributes here. | |
174 subG = type(G)(G.edges()) | |
175 sccs = [scc for scc in nx.strongly_connected_components(subG) if len(scc) > 1] | |
176 | |
177 # Johnson's algorithm exclude self cycle edges like (v, v) | |
178 # To be backward compatible, we record those cycles in advance | |
179 # and then remove from subG | |
180 for v in subG: | |
181 if subG.has_edge(v, v): | |
182 yield [v] | |
183 subG.remove_edge(v, v) | |
184 | |
185 while sccs: | |
186 scc = sccs.pop() | |
187 sccG = subG.subgraph(scc) | |
188 # order of scc determines ordering of nodes | |
189 startnode = scc.pop() | |
190 # Processing node runs "circuit" routine from recursive version | |
191 path = [startnode] | |
192 blocked = set() # vertex: blocked from search? | |
193 closed = set() # nodes involved in a cycle | |
194 blocked.add(startnode) | |
195 B = defaultdict(set) # graph portions that yield no elementary circuit | |
196 stack = [(startnode, list(sccG[startnode]))] # sccG gives comp nbrs | |
197 while stack: | |
198 thisnode, nbrs = stack[-1] | |
199 if nbrs: | |
200 nextnode = nbrs.pop() | |
201 if nextnode == startnode: | |
202 yield path[:] | |
203 closed.update(path) | |
204 # print "Found a cycle", path, closed | |
205 elif nextnode not in blocked: | |
206 path.append(nextnode) | |
207 stack.append((nextnode, list(sccG[nextnode]))) | |
208 closed.discard(nextnode) | |
209 blocked.add(nextnode) | |
210 continue | |
211 # done with nextnode... look for more neighbors | |
212 if not nbrs: # no more nbrs | |
213 if thisnode in closed: | |
214 _unblock(thisnode, blocked, B) | |
215 else: | |
216 for nbr in sccG[thisnode]: | |
217 if thisnode not in B[nbr]: | |
218 B[nbr].add(thisnode) | |
219 stack.pop() | |
220 # assert path[-1] == thisnode | |
221 path.pop() | |
222 # done processing this node | |
223 H = subG.subgraph(scc) # make smaller to avoid work in SCC routine | |
224 sccs.extend(scc for scc in nx.strongly_connected_components(H) if len(scc) > 1) | |
225 | |
226 | |
227 @not_implemented_for("undirected") | |
228 def recursive_simple_cycles(G): | |
229 """Find simple cycles (elementary circuits) of a directed graph. | |
230 | |
231 A `simple cycle`, or `elementary circuit`, is a closed path where | |
232 no node appears twice. Two elementary circuits are distinct if they | |
233 are not cyclic permutations of each other. | |
234 | |
235 This version uses a recursive algorithm to build a list of cycles. | |
236 You should probably use the iterator version called simple_cycles(). | |
237 Warning: This recursive version uses lots of RAM! | |
238 | |
239 Parameters | |
240 ---------- | |
241 G : NetworkX DiGraph | |
242 A directed graph | |
243 | |
244 Returns | |
245 ------- | |
246 A list of cycles, where each cycle is represented by a list of nodes | |
247 along the cycle. | |
248 | |
249 Example: | |
250 | |
251 >>> edges = [(0, 0), (0, 1), (0, 2), (1, 2), (2, 0), (2, 1), (2, 2)] | |
252 >>> G = nx.DiGraph(edges) | |
253 >>> nx.recursive_simple_cycles(G) | |
254 [[0], [2], [0, 1, 2], [0, 2], [1, 2]] | |
255 | |
256 See Also | |
257 -------- | |
258 cycle_basis (for undirected graphs) | |
259 | |
260 Notes | |
261 ----- | |
262 The implementation follows pp. 79-80 in [1]_. | |
263 | |
264 The time complexity is $O((n+e)(c+1))$ for $n$ nodes, $e$ edges and $c$ | |
265 elementary circuits. | |
266 | |
267 References | |
268 ---------- | |
269 .. [1] Finding all the elementary circuits of a directed graph. | |
270 D. B. Johnson, SIAM Journal on Computing 4, no. 1, 77-84, 1975. | |
271 https://doi.org/10.1137/0204007 | |
272 | |
273 See Also | |
274 -------- | |
275 simple_cycles, cycle_basis | |
276 """ | |
277 # Jon Olav Vik, 2010-08-09 | |
278 def _unblock(thisnode): | |
279 """Recursively unblock and remove nodes from B[thisnode].""" | |
280 if blocked[thisnode]: | |
281 blocked[thisnode] = False | |
282 while B[thisnode]: | |
283 _unblock(B[thisnode].pop()) | |
284 | |
285 def circuit(thisnode, startnode, component): | |
286 closed = False # set to True if elementary path is closed | |
287 path.append(thisnode) | |
288 blocked[thisnode] = True | |
289 for nextnode in component[thisnode]: # direct successors of thisnode | |
290 if nextnode == startnode: | |
291 result.append(path[:]) | |
292 closed = True | |
293 elif not blocked[nextnode]: | |
294 if circuit(nextnode, startnode, component): | |
295 closed = True | |
296 if closed: | |
297 _unblock(thisnode) | |
298 else: | |
299 for nextnode in component[thisnode]: | |
300 if thisnode not in B[nextnode]: # TODO: use set for speedup? | |
301 B[nextnode].append(thisnode) | |
302 path.pop() # remove thisnode from path | |
303 return closed | |
304 | |
305 path = [] # stack of nodes in current path | |
306 blocked = defaultdict(bool) # vertex: blocked from search? | |
307 B = defaultdict(list) # graph portions that yield no elementary circuit | |
308 result = [] # list to accumulate the circuits found | |
309 | |
310 # Johnson's algorithm exclude self cycle edges like (v, v) | |
311 # To be backward compatible, we record those cycles in advance | |
312 # and then remove from subG | |
313 for v in G: | |
314 if G.has_edge(v, v): | |
315 result.append([v]) | |
316 G.remove_edge(v, v) | |
317 | |
318 # Johnson's algorithm requires some ordering of the nodes. | |
319 # They might not be sortable so we assign an arbitrary ordering. | |
320 ordering = dict(zip(G, range(len(G)))) | |
321 for s in ordering: | |
322 # Build the subgraph induced by s and following nodes in the ordering | |
323 subgraph = G.subgraph(node for node in G if ordering[node] >= ordering[s]) | |
324 # Find the strongly connected component in the subgraph | |
325 # that contains the least node according to the ordering | |
326 strongcomp = nx.strongly_connected_components(subgraph) | |
327 mincomp = min(strongcomp, key=lambda ns: min(ordering[n] for n in ns)) | |
328 component = G.subgraph(mincomp) | |
329 if len(component) > 1: | |
330 # smallest node in the component according to the ordering | |
331 startnode = min(component, key=ordering.__getitem__) | |
332 for node in component: | |
333 blocked[node] = False | |
334 B[node][:] = [] | |
335 dummy = circuit(startnode, startnode, component) | |
336 return result | |
337 | |
338 | |
339 def find_cycle(G, source=None, orientation=None): | |
340 """Returns a cycle found via depth-first traversal. | |
341 | |
342 The cycle is a list of edges indicating the cyclic path. | |
343 Orientation of directed edges is controlled by `orientation`. | |
344 | |
345 Parameters | |
346 ---------- | |
347 G : graph | |
348 A directed/undirected graph/multigraph. | |
349 | |
350 source : node, list of nodes | |
351 The node from which the traversal begins. If None, then a source | |
352 is chosen arbitrarily and repeatedly until all edges from each node in | |
353 the graph are searched. | |
354 | |
355 orientation : None | 'original' | 'reverse' | 'ignore' (default: None) | |
356 For directed graphs and directed multigraphs, edge traversals need not | |
357 respect the original orientation of the edges. | |
358 When set to 'reverse' every edge is traversed in the reverse direction. | |
359 When set to 'ignore', every edge is treated as undirected. | |
360 When set to 'original', every edge is treated as directed. | |
361 In all three cases, the yielded edge tuples add a last entry to | |
362 indicate the direction in which that edge was traversed. | |
363 If orientation is None, the yielded edge has no direction indicated. | |
364 The direction is respected, but not reported. | |
365 | |
366 Returns | |
367 ------- | |
368 edges : directed edges | |
369 A list of directed edges indicating the path taken for the loop. | |
370 If no cycle is found, then an exception is raised. | |
371 For graphs, an edge is of the form `(u, v)` where `u` and `v` | |
372 are the tail and head of the edge as determined by the traversal. | |
373 For multigraphs, an edge is of the form `(u, v, key)`, where `key` is | |
374 the key of the edge. When the graph is directed, then `u` and `v` | |
375 are always in the order of the actual directed edge. | |
376 If orientation is not None then the edge tuple is extended to include | |
377 the direction of traversal ('forward' or 'reverse') on that edge. | |
378 | |
379 Raises | |
380 ------ | |
381 NetworkXNoCycle | |
382 If no cycle was found. | |
383 | |
384 Examples | |
385 -------- | |
386 In this example, we construct a DAG and find, in the first call, that there | |
387 are no directed cycles, and so an exception is raised. In the second call, | |
388 we ignore edge orientations and find that there is an undirected cycle. | |
389 Note that the second call finds a directed cycle while effectively | |
390 traversing an undirected graph, and so, we found an "undirected cycle". | |
391 This means that this DAG structure does not form a directed tree (which | |
392 is also known as a polytree). | |
393 | |
394 >>> G = nx.DiGraph([(0, 1), (0, 2), (1, 2)]) | |
395 >>> try: | |
396 ... nx.find_cycle(G, orientation="original") | |
397 ... except: | |
398 ... pass | |
399 ... | |
400 >>> list(nx.find_cycle(G, orientation="ignore")) | |
401 [(0, 1, 'forward'), (1, 2, 'forward'), (0, 2, 'reverse')] | |
402 | |
403 See Also | |
404 -------- | |
405 simple_cycles | |
406 """ | |
407 if not G.is_directed() or orientation in (None, "original"): | |
408 | |
409 def tailhead(edge): | |
410 return edge[:2] | |
411 | |
412 elif orientation == "reverse": | |
413 | |
414 def tailhead(edge): | |
415 return edge[1], edge[0] | |
416 | |
417 elif orientation == "ignore": | |
418 | |
419 def tailhead(edge): | |
420 if edge[-1] == "reverse": | |
421 return edge[1], edge[0] | |
422 return edge[:2] | |
423 | |
424 explored = set() | |
425 cycle = [] | |
426 final_node = None | |
427 for start_node in G.nbunch_iter(source): | |
428 if start_node in explored: | |
429 # No loop is possible. | |
430 continue | |
431 | |
432 edges = [] | |
433 # All nodes seen in this iteration of edge_dfs | |
434 seen = {start_node} | |
435 # Nodes in active path. | |
436 active_nodes = {start_node} | |
437 previous_head = None | |
438 | |
439 for edge in nx.edge_dfs(G, start_node, orientation): | |
440 # Determine if this edge is a continuation of the active path. | |
441 tail, head = tailhead(edge) | |
442 if head in explored: | |
443 # Then we've already explored it. No loop is possible. | |
444 continue | |
445 if previous_head is not None and tail != previous_head: | |
446 # This edge results from backtracking. | |
447 # Pop until we get a node whose head equals the current tail. | |
448 # So for example, we might have: | |
449 # (0, 1), (1, 2), (2, 3), (1, 4) | |
450 # which must become: | |
451 # (0, 1), (1, 4) | |
452 while True: | |
453 try: | |
454 popped_edge = edges.pop() | |
455 except IndexError: | |
456 edges = [] | |
457 active_nodes = {tail} | |
458 break | |
459 else: | |
460 popped_head = tailhead(popped_edge)[1] | |
461 active_nodes.remove(popped_head) | |
462 | |
463 if edges: | |
464 last_head = tailhead(edges[-1])[1] | |
465 if tail == last_head: | |
466 break | |
467 edges.append(edge) | |
468 | |
469 if head in active_nodes: | |
470 # We have a loop! | |
471 cycle.extend(edges) | |
472 final_node = head | |
473 break | |
474 else: | |
475 seen.add(head) | |
476 active_nodes.add(head) | |
477 previous_head = head | |
478 | |
479 if cycle: | |
480 break | |
481 else: | |
482 explored.update(seen) | |
483 | |
484 else: | |
485 assert len(cycle) == 0 | |
486 raise nx.exception.NetworkXNoCycle("No cycle found.") | |
487 | |
488 # We now have a list of edges which ends on a cycle. | |
489 # So we need to remove from the beginning edges that are not relevant. | |
490 | |
491 for i, edge in enumerate(cycle): | |
492 tail, head = tailhead(edge) | |
493 if tail == final_node: | |
494 break | |
495 | |
496 return cycle[i:] | |
497 | |
498 | |
499 @not_implemented_for("directed") | |
500 @not_implemented_for("multigraph") | |
501 def minimum_cycle_basis(G, weight=None): | |
502 """ Returns a minimum weight cycle basis for G | |
503 | |
504 Minimum weight means a cycle basis for which the total weight | |
505 (length for unweighted graphs) of all the cycles is minimum. | |
506 | |
507 Parameters | |
508 ---------- | |
509 G : NetworkX Graph | |
510 weight: string | |
511 name of the edge attribute to use for edge weights | |
512 | |
513 Returns | |
514 ------- | |
515 A list of cycle lists. Each cycle list is a list of nodes | |
516 which forms a cycle (loop) in G. Note that the nodes are not | |
517 necessarily returned in a order by which they appear in the cycle | |
518 | |
519 Examples | |
520 -------- | |
521 >>> G = nx.Graph() | |
522 >>> nx.add_cycle(G, [0, 1, 2, 3]) | |
523 >>> nx.add_cycle(G, [0, 3, 4, 5]) | |
524 >>> print([sorted(c) for c in nx.minimum_cycle_basis(G)]) | |
525 [[0, 1, 2, 3], [0, 3, 4, 5]] | |
526 | |
527 References: | |
528 [1] Kavitha, Telikepalli, et al. "An O(m^2n) Algorithm for | |
529 Minimum Cycle Basis of Graphs." | |
530 http://link.springer.com/article/10.1007/s00453-007-9064-z | |
531 [2] de Pina, J. 1995. Applications of shortest path methods. | |
532 Ph.D. thesis, University of Amsterdam, Netherlands | |
533 | |
534 See Also | |
535 -------- | |
536 simple_cycles, cycle_basis | |
537 """ | |
538 # We first split the graph in commected subgraphs | |
539 return sum( | |
540 (_min_cycle_basis(G.subgraph(c), weight) for c in nx.connected_components(G)), | |
541 [], | |
542 ) | |
543 | |
544 | |
545 def _min_cycle_basis(comp, weight): | |
546 cb = [] | |
547 # We extract the edges not in a spanning tree. We do not really need a | |
548 # *minimum* spanning tree. That is why we call the next function with | |
549 # weight=None. Depending on implementation, it may be faster as well | |
550 spanning_tree_edges = list(nx.minimum_spanning_edges(comp, weight=None, data=False)) | |
551 edges_excl = [frozenset(e) for e in comp.edges() if e not in spanning_tree_edges] | |
552 N = len(edges_excl) | |
553 | |
554 # We maintain a set of vectors orthogonal to sofar found cycles | |
555 set_orth = [{edge} for edge in edges_excl] | |
556 for k in range(N): | |
557 # kth cycle is "parallel" to kth vector in set_orth | |
558 new_cycle = _min_cycle(comp, set_orth[k], weight=weight) | |
559 cb.append(list(set().union(*new_cycle))) | |
560 # now update set_orth so that k+1,k+2... th elements are | |
561 # orthogonal to the newly found cycle, as per [p. 336, 1] | |
562 base = set_orth[k] | |
563 set_orth[k + 1 :] = [ | |
564 orth ^ base if len(orth & new_cycle) % 2 else orth | |
565 for orth in set_orth[k + 1 :] | |
566 ] | |
567 return cb | |
568 | |
569 | |
570 def _min_cycle(G, orth, weight=None): | |
571 """ | |
572 Computes the minimum weight cycle in G, | |
573 orthogonal to the vector orth as per [p. 338, 1] | |
574 """ | |
575 T = nx.Graph() | |
576 | |
577 nodes_idx = {node: idx for idx, node in enumerate(G.nodes())} | |
578 idx_nodes = {idx: node for node, idx in nodes_idx.items()} | |
579 | |
580 nnodes = len(nodes_idx) | |
581 | |
582 # Add 2 copies of each edge in G to T. If edge is in orth, add cross edge; | |
583 # otherwise in-plane edge | |
584 for u, v, data in G.edges(data=True): | |
585 uidx, vidx = nodes_idx[u], nodes_idx[v] | |
586 edge_w = data.get(weight, 1) | |
587 if frozenset((u, v)) in orth: | |
588 T.add_edges_from( | |
589 [(uidx, nnodes + vidx), (nnodes + uidx, vidx)], weight=edge_w | |
590 ) | |
591 else: | |
592 T.add_edges_from( | |
593 [(uidx, vidx), (nnodes + uidx, nnodes + vidx)], weight=edge_w | |
594 ) | |
595 | |
596 all_shortest_pathlens = dict(nx.shortest_path_length(T, weight=weight)) | |
597 cross_paths_w_lens = { | |
598 n: all_shortest_pathlens[n][nnodes + n] for n in range(nnodes) | |
599 } | |
600 | |
601 # Now compute shortest paths in T, which translates to cyles in G | |
602 start = min(cross_paths_w_lens, key=cross_paths_w_lens.get) | |
603 end = nnodes + start | |
604 min_path = nx.shortest_path(T, source=start, target=end, weight="weight") | |
605 | |
606 # Now we obtain the actual path, re-map nodes in T to those in G | |
607 min_path_nodes = [node if node < nnodes else node - nnodes for node in min_path] | |
608 # Now remove the edges that occur two times | |
609 mcycle_pruned = _path_to_cycle(min_path_nodes) | |
610 | |
611 return {frozenset((idx_nodes[u], idx_nodes[v])) for u, v in mcycle_pruned} | |
612 | |
613 | |
614 def _path_to_cycle(path): | |
615 """ | |
616 Removes the edges from path that occur even number of times. | |
617 Returns a set of edges | |
618 """ | |
619 edges = set() | |
620 for edge in pairwise(path): | |
621 # Toggle whether to keep the current edge. | |
622 edges ^= {edge} | |
623 return edges |