ioftools / networkxMiCe / networkxmaster / networkx / algorithms / cycles.py @ 5cef0f13
History  View  Annotate  Download (21.6 KB)
1 
# Copyright (C) 20102019 by


2 
# Aric Hagberg <hagberg@lanl.gov>

3 
# Dan Schult <dschult@colgate.edu>

4 
# Pieter Swart <swart@lanl.gov>

5 
# All rights reserved.

6 
# BSD license.

7 
#

8 
# Authors: Jon Olav Vik <jonovik@gmail.com>

9 
# Dan Schult <dschult@colgate.edu>

10 
# Aric Hagberg <hagberg@lanl.gov>

11 
# Debsankha Manik <dmanik@nld.ds.mpg.de>

12 
"""

13 
========================

14 
Cycle finding algorithms

15 
========================

16 
"""

17  
18 
from collections import defaultdict 
19 
from itertools import tee 
20  
21 
import networkx as nx 
22 
from networkx.utils import not_implemented_for, pairwise 
23  
24 
__all__ = [ 
25 
'cycle_basis', 'simple_cycles', 
26 
'recursive_simple_cycles', 'find_cycle', 
27 
'minimum_cycle_basis',

28 
] 
29  
30  
31 
@not_implemented_for('directed') 
32 
@not_implemented_for('multigraph') 
33 
def cycle_basis(G, root=None): 
34 
""" Returns a list of cycles which form a basis for cycles of G.

35 

36 
A basis for cycles of a network is a minimal collection of

37 
cycles such that any cycle in the network can be written

38 
as a sum of cycles in the basis. Here summation of cycles

39 
is defined as "exclusive or" of the edges. Cycle bases are

40 
useful, e.g. when deriving equations for electric circuits

41 
using Kirchhoff's Laws.

42 

43 
Parameters

44 


45 
G : NetworkX Graph

46 
root : node, optional

47 
Specify starting node for basis.

48 

49 
Returns

50 


51 
A list of cycle lists. Each cycle list is a list of nodes

52 
which forms a cycle (loop) in G.

53 

54 
Examples

55 


56 
>>> G = nx.Graph()

57 
>>> nx.add_cycle(G, [0, 1, 2, 3])

58 
>>> nx.add_cycle(G, [0, 3, 4, 5])

59 
>>> print(nx.cycle_basis(G, 0))

60 
[[3, 4, 5, 0], [1, 2, 3, 0]]

61 

62 
Notes

63 


64 
This is adapted from algorithm CACM 491 [1]_.

65 

66 
References

67 


68 
.. [1] Paton, K. An algorithm for finding a fundamental set of

69 
cycles of a graph. Comm. ACM 12, 9 (Sept 1969), 514518.

70 

71 
See Also

72 


73 
simple_cycles

74 
"""

75 
gnodes = set(G.nodes())

76 
cycles = [] 
77 
while gnodes: # loop over connected components 
78 
if root is None: 
79 
root = gnodes.pop() 
80 
stack = [root] 
81 
pred = {root: root} 
82 
used = {root: set()}

83 
while stack: # walk the spanning tree finding cycles 
84 
z = stack.pop() # use lastin so cycles easier to find

85 
zused = used[z] 
86 
for nbr in G[z]: 
87 
if nbr not in used: # new node 
88 
pred[nbr] = z 
89 
stack.append(nbr) 
90 
used[nbr] = set([z])

91 
elif nbr == z: # self loops 
92 
cycles.append([z]) 
93 
elif nbr not in zused: # found a cycle 
94 
pn = used[nbr] 
95 
cycle = [nbr, z] 
96 
p = pred[z] 
97 
while p not in pn: 
98 
cycle.append(p) 
99 
p = pred[p] 
100 
cycle.append(p) 
101 
cycles.append(cycle) 
102 
used[nbr].add(z) 
103 
gnodes = set(pred)

104 
root = None

105 
return cycles

106  
107  
108 
@not_implemented_for('undirected') 
109 
def simple_cycles(G): 
110 
"""Find simple cycles (elementary circuits) of a directed graph.

111 

112 
A `simple cycle`, or `elementary circuit`, is a closed path where

113 
no node appears twice. Two elementary circuits are distinct if they

114 
are not cyclic permutations of each other.

115 

116 
This is a nonrecursive, iterator/generator version of Johnson's

117 
algorithm [1]_. There may be better algorithms for some cases [2]_ [3]_.

118 

119 
Parameters

120 


121 
G : NetworkX DiGraph

122 
A directed graph

123 

124 
Returns

125 


126 
cycle_generator: generator

127 
A generator that produces elementary cycles of the graph.

128 
Each cycle is represented by a list of nodes along the cycle.

129 

130 
Examples

131 


132 
>>> edges = [(0, 0), (0, 1), (0, 2), (1, 2), (2, 0), (2, 1), (2, 2)]

133 
>>> G = nx.DiGraph(edges)

134 
>>> len(list(nx.simple_cycles(G)))

135 
5

136 

137 
To filter the cycles so that they don't include certain nodes or edges,

138 
copy your graph and eliminate those nodes or edges before calling

139 

140 
>>> copyG = G.copy()

141 
>>> copyG.remove_nodes_from([1])

142 
>>> copyG.remove_edges_from([(0, 1)])

143 
>>> len(list(nx.simple_cycles(copyG)))

144 
3

145 

146 

147 
Notes

148 


149 
The implementation follows pp. 7980 in [1]_.

150 

151 
The time complexity is $O((n+e)(c+1))$ for $n$ nodes, $e$ edges and $c$

152 
elementary circuits.

153 

154 
References

155 


156 
.. [1] Finding all the elementary circuits of a directed graph.

157 
D. B. Johnson, SIAM Journal on Computing 4, no. 1, 7784, 1975.

158 
https://doi.org/10.1137/0204007

159 
.. [2] Enumerating the cycles of a digraph: a new preprocessing strategy.

160 
G. Loizou and P. Thanish, Information Sciences, v. 27, 163182, 1982.

161 
.. [3] A search strategy for the elementary cycles of a directed graph.

162 
J.L. Szwarcfiter and P.E. Lauer, BIT NUMERICAL MATHEMATICS,

163 
v. 16, no. 2, 192204, 1976.

164 

165 
See Also

166 


167 
cycle_basis

168 
"""

169 
def _unblock(thisnode, blocked, B): 
170 
stack = set([thisnode])

171 
while stack:

172 
node = stack.pop() 
173 
if node in blocked: 
174 
blocked.remove(node) 
175 
stack.update(B[node]) 
176 
B[node].clear() 
177  
178 
# Johnson's algorithm requires some ordering of the nodes.

179 
# We assign the arbitrary ordering given by the strongly connected comps

180 
# There is no need to track the ordering as each node removed as processed.

181 
# Also we save the actual graph so we can mutate it. We only take the

182 
# edges because we do not want to copy edge and node attributes here.

183 
subG = type(G)(G.edges())

184 
sccs = [scc for scc in nx.strongly_connected_components(subG) 
185 
if len(scc) > 1] 
186  
187 
# Johnson's algorithm exclude self cycle edges like (v, v)

188 
# To be backward compatible, we record those cycles in advance

189 
# and then remove from subG

190 
for v in subG: 
191 
if subG.has_edge(v, v):

192 
yield [v]

193 
subG.remove_edge(v, v) 
194  
195 
while sccs:

196 
scc = sccs.pop() 
197 
sccG = subG.subgraph(scc) 
198 
# order of scc determines ordering of nodes

199 
startnode = scc.pop() 
200 
# Processing node runs "circuit" routine from recursive version

201 
path = [startnode] 
202 
blocked = set() # vertex: blocked from search? 
203 
closed = set() # nodes involved in a cycle 
204 
blocked.add(startnode) 
205 
B = defaultdict(set) # graph portions that yield no elementary circuit 
206 
stack = [(startnode, list(sccG[startnode]))] # sccG gives comp nbrs 
207 
while stack:

208 
thisnode, nbrs = stack[1]

209 
if nbrs:

210 
nextnode = nbrs.pop() 
211 
if nextnode == startnode:

212 
yield path[:]

213 
closed.update(path) 
214 
# print "Found a cycle", path, closed

215 
elif nextnode not in blocked: 
216 
path.append(nextnode) 
217 
stack.append((nextnode, list(sccG[nextnode])))

218 
closed.discard(nextnode) 
219 
blocked.add(nextnode) 
220 
continue

221 
# done with nextnode... look for more neighbors

222 
if not nbrs: # no more nbrs 
223 
if thisnode in closed: 
224 
_unblock(thisnode, blocked, B) 
225 
else:

226 
for nbr in sccG[thisnode]: 
227 
if thisnode not in B[nbr]: 
228 
B[nbr].add(thisnode) 
229 
stack.pop() 
230 
# assert path[1] == thisnode

231 
path.pop() 
232 
# done processing this node

233 
H = subG.subgraph(scc) # make smaller to avoid work in SCC routine

234 
sccs.extend(scc for scc in nx.strongly_connected_components(H) 
235 
if len(scc) > 1) 
236  
237  
238 
@not_implemented_for('undirected') 
239 
def recursive_simple_cycles(G): 
240 
"""Find simple cycles (elementary circuits) of a directed graph.

241 

242 
A `simple cycle`, or `elementary circuit`, is a closed path where

243 
no node appears twice. Two elementary circuits are distinct if they

244 
are not cyclic permutations of each other.

245 

246 
This version uses a recursive algorithm to build a list of cycles.

247 
You should probably use the iterator version called simple_cycles().

248 
Warning: This recursive version uses lots of RAM!

249 

250 
Parameters

251 


252 
G : NetworkX DiGraph

253 
A directed graph

254 

255 
Returns

256 


257 
A list of cycles, where each cycle is represented by a list of nodes

258 
along the cycle.

259 

260 
Example:

261 

262 
>>> edges = [(0, 0), (0, 1), (0, 2), (1, 2), (2, 0), (2, 1), (2, 2)]

263 
>>> G = nx.DiGraph(edges)

264 
>>> nx.recursive_simple_cycles(G)

265 
[[0], [2], [0, 1, 2], [0, 2], [1, 2]]

266 

267 
See Also

268 


269 
cycle_basis (for undirected graphs)

270 

271 
Notes

272 


273 
The implementation follows pp. 7980 in [1]_.

274 

275 
The time complexity is $O((n+e)(c+1))$ for $n$ nodes, $e$ edges and $c$

276 
elementary circuits.

277 

278 
References

279 


280 
.. [1] Finding all the elementary circuits of a directed graph.

281 
D. B. Johnson, SIAM Journal on Computing 4, no. 1, 7784, 1975.

282 
https://doi.org/10.1137/0204007

283 

284 
See Also

285 


286 
simple_cycles, cycle_basis

287 
"""

288 
# Jon Olav Vik, 20100809

289 
def _unblock(thisnode): 
290 
"""Recursively unblock and remove nodes from B[thisnode]."""

291 
if blocked[thisnode]:

292 
blocked[thisnode] = False

293 
while B[thisnode]:

294 
_unblock(B[thisnode].pop()) 
295  
296 
def circuit(thisnode, startnode, component): 
297 
closed = False # set to True if elementary path is closed 
298 
path.append(thisnode) 
299 
blocked[thisnode] = True

300 
for nextnode in component[thisnode]: # direct successors of thisnode 
301 
if nextnode == startnode:

302 
result.append(path[:]) 
303 
closed = True

304 
elif not blocked[nextnode]: 
305 
if circuit(nextnode, startnode, component):

306 
closed = True

307 
if closed:

308 
_unblock(thisnode) 
309 
else:

310 
for nextnode in component[thisnode]: 
311 
if thisnode not in B[nextnode]: # TODO: use set for speedup? 
312 
B[nextnode].append(thisnode) 
313 
path.pop() # remove thisnode from path

314 
return closed

315  
316 
path = [] # stack of nodes in current path

317 
blocked = defaultdict(bool) # vertex: blocked from search? 
318 
B = defaultdict(list) # graph portions that yield no elementary circuit 
319 
result = [] # list to accumulate the circuits found

320  
321 
# Johnson's algorithm exclude self cycle edges like (v, v)

322 
# To be backward compatible, we record those cycles in advance

323 
# and then remove from subG

324 
for v in G: 
325 
if G.has_edge(v, v):

326 
result.append([v]) 
327 
G.remove_edge(v, v) 
328  
329 
# Johnson's algorithm requires some ordering of the nodes.

330 
# They might not be sortable so we assign an arbitrary ordering.

331 
ordering = dict(zip(G, range(len(G)))) 
332 
for s in ordering: 
333 
# Build the subgraph induced by s and following nodes in the ordering

334 
subgraph = G.subgraph(node for node in G 
335 
if ordering[node] >= ordering[s])

336 
# Find the strongly connected component in the subgraph

337 
# that contains the least node according to the ordering

338 
strongcomp = nx.strongly_connected_components(subgraph) 
339 
mincomp = min(strongcomp, key=lambda ns: min(ordering[n] for n in ns)) 
340 
component = G.subgraph(mincomp) 
341 
if len(component) > 1: 
342 
# smallest node in the component according to the ordering

343 
startnode = min(component, key=ordering.__getitem__)

344 
for node in component: 
345 
blocked[node] = False

346 
B[node][:] = [] 
347 
dummy = circuit(startnode, startnode, component) 
348 
return result

349  
350  
351 
def find_cycle(G, source=None, orientation=None): 
352 
"""Returns a cycle found via depthfirst traversal.

353 

354 
The cycle is a list of edges indicating the cyclic path.

355 
Orientation of directed edges is controlled by `orientation`.

356 

357 
Parameters

358 


359 
G : graph

360 
A directed/undirected graph/multigraph.

361 

362 
source : node, list of nodes

363 
The node from which the traversal begins. If None, then a source

364 
is chosen arbitrarily and repeatedly until all edges from each node in

365 
the graph are searched.

366 

367 
orientation : None  'original'  'reverse'  'ignore' (default: None)

368 
For directed graphs and directed multigraphs, edge traversals need not

369 
respect the original orientation of the edges.

370 
When set to 'reverse' every edge is traversed in the reverse direction.

371 
When set to 'ignore', every edge is treated as undirected.

372 
When set to 'original', every edge is treated as directed.

373 
In all three cases, the yielded edge tuples add a last entry to

374 
indicate the direction in which that edge was traversed.

375 
If orientation is None, the yielded edge has no direction indicated.

376 
The direction is respected, but not reported.

377 

378 
Returns

379 


380 
edges : directed edges

381 
A list of directed edges indicating the path taken for the loop.

382 
If no cycle is found, then an exception is raised.

383 
For graphs, an edge is of the form `(u, v)` where `u` and `v`

384 
are the tail and head of the edge as determined by the traversal.

385 
For multigraphs, an edge is of the form `(u, v, key)`, where `key` is

386 
the key of the edge. When the graph is directed, then `u` and `v`

387 
are always in the order of the actual directed edge.

388 
If orientation is not None then the edge tuple is extended to include

389 
the direction of traversal ('forward' or 'reverse') on that edge.

390 

391 
Raises

392 


393 
NetworkXNoCycle

394 
If no cycle was found.

395 

396 
Examples

397 


398 
In this example, we construct a DAG and find, in the first call, that there

399 
are no directed cycles, and so an exception is raised. In the second call,

400 
we ignore edge orientations and find that there is an undirected cycle.

401 
Note that the second call finds a directed cycle while effectively

402 
traversing an undirected graph, and so, we found an "undirected cycle".

403 
This means that this DAG structure does not form a directed tree (which

404 
is also known as a polytree).

405 

406 
>>> import networkx as nx

407 
>>> G = nx.DiGraph([(0, 1), (0, 2), (1, 2)])

408 
>>> try:

409 
... nx.find_cycle(G, orientation='original')

410 
... except:

411 
... pass

412 
...

413 
>>> list(nx.find_cycle(G, orientation='ignore'))

414 
[(0, 1, 'forward'), (1, 2, 'forward'), (0, 2, 'reverse')]

415 

416 
"""

417 
if not G.is_directed() or orientation in (None, 'original'): 
418 
def tailhead(edge): 
419 
return edge[:2] 
420 
elif orientation == 'reverse': 
421 
def tailhead(edge): 
422 
return edge[1], edge[0] 
423 
elif orientation == 'ignore': 
424 
def tailhead(edge): 
425 
if edge[1] == 'reverse': 
426 
return edge[1], edge[0] 
427 
return edge[:2] 
428  
429 
explored = set()

430 
cycle = [] 
431 
final_node = None

432 
for start_node in G.nbunch_iter(source): 
433 
if start_node in explored: 
434 
# No loop is possible.

435 
continue

436  
437 
edges = [] 
438 
# All nodes seen in this iteration of edge_dfs

439 
seen = {start_node} 
440 
# Nodes in active path.

441 
active_nodes = {start_node} 
442 
previous_head = None

443  
444 
for edge in nx.edge_dfs(G, start_node, orientation): 
445 
# Determine if this edge is a continuation of the active path.

446 
tail, head = tailhead(edge) 
447 
if head in explored: 
448 
# Then we've already explored it. No loop is possible.

449 
continue

450 
if previous_head is not None and tail != previous_head: 
451 
# This edge results from backtracking.

452 
# Pop until we get a node whose head equals the current tail.

453 
# So for example, we might have:

454 
# (0, 1), (1, 2), (2, 3), (1, 4)

455 
# which must become:

456 
# (0, 1), (1, 4)

457 
while True: 
458 
try:

459 
popped_edge = edges.pop() 
460 
except IndexError: 
461 
edges = [] 
462 
active_nodes = {tail} 
463 
break

464 
else:

465 
popped_head = tailhead(popped_edge)[1]

466 
active_nodes.remove(popped_head) 
467  
468 
if edges:

469 
last_head = tailhead(edges[1])[1] 
470 
if tail == last_head:

471 
break

472 
edges.append(edge) 
473  
474 
if head in active_nodes: 
475 
# We have a loop!

476 
cycle.extend(edges) 
477 
final_node = head 
478 
break

479 
else:

480 
seen.add(head) 
481 
active_nodes.add(head) 
482 
previous_head = head 
483  
484 
if cycle:

485 
break

486 
else:

487 
explored.update(seen) 
488  
489 
else:

490 
assert(len(cycle) == 0) 
491 
raise nx.exception.NetworkXNoCycle('No cycle found.') 
492  
493 
# We now have a list of edges which ends on a cycle.

494 
# So we need to remove from the beginning edges that are not relevant.

495  
496 
for i, edge in enumerate(cycle): 
497 
tail, head = tailhead(edge) 
498 
if tail == final_node:

499 
break

500  
501 
return cycle[i:]

502  
503  
504 
@not_implemented_for('directed') 
505 
@not_implemented_for('multigraph') 
506 
def minimum_cycle_basis(G, weight=None): 
507 
""" Returns a minimum weight cycle basis for G

508 

509 
Minimum weight means a cycle basis for which the total weight

510 
(length for unweighted graphs) of all the cycles is minimum.

511 

512 
Parameters

513 


514 
G : NetworkX Graph

515 
weight: string

516 
name of the edge attribute to use for edge weights

517 

518 
Returns

519 


520 
A list of cycle lists. Each cycle list is a list of nodes

521 
which forms a cycle (loop) in G. Note that the nodes are not

522 
necessarily returned in a order by which they appear in the cycle

523 

524 
Examples

525 


526 
>>> G=nx.Graph()

527 
>>> G.add_cycle([0,1,2,3])

528 
>>> G.add_cycle([0,3,4,5])

529 
>>> print(nx.minimum_cycle_basis(G))

530 
[[0, 1, 2, 3], [0, 3, 4, 5]]

531 

532 
References:

533 
[1] Kavitha, Telikepalli, et al. "An O(m^2n) Algorithm for

534 
Minimum Cycle Basis of Graphs."

535 
http://link.springer.com/article/10.1007/s004530079064z

536 
[2] de Pina, J. 1995. Applications of shortest path methods.

537 
Ph.D. thesis, University of Amsterdam, Netherlands

538 

539 
See Also

540 


541 
simple_cycles, cycle_basis

542 
"""

543 
# We first split the graph in commected subgraphs

544 
return sum((_min_cycle_basis(c, weight) for c in 
545 
nx.connected_component_subgraphs(G)), []) 
546  
547  
548 
def _min_cycle_basis(comp, weight): 
549 
cb = [] 
550 
# We extract the edges not in a spanning tree. We do not really need a

551 
# *minimum* spanning tree. That is why we call the next function with

552 
# weight=None. Depending on implementation, it may be faster as well

553 
spanning_tree_edges = list(nx.minimum_spanning_edges(comp, weight=None, 
554 
data=False))

555 
edges_excl = [frozenset(e) for e in comp.edges() 
556 
if e not in spanning_tree_edges] 
557 
N = len(edges_excl)

558  
559 
# We maintain a set of vectors orthogonal to sofar found cycles

560 
set_orth = [set([edge]) for edge in edges_excl] 
561 
for k in range(N): 
562 
# kth cycle is "parallel" to kth vector in set_orth

563 
new_cycle = _min_cycle(comp, set_orth[k], weight=weight) 
564 
cb.append(list(set().union(*new_cycle))) 
565 
# now update set_orth so that k+1,k+2... th elements are

566 
# orthogonal to the newly found cycle, as per [p. 336, 1]

567 
base = set_orth[k] 
568 
set_orth[k + 1:] = [orth ^ base if len(orth & new_cycle) % 2 else orth 
569 
for orth in set_orth[k + 1:]] 
570 
return cb

571  
572  
573 
def _min_cycle(G, orth, weight=None): 
574 
"""

575 
Computes the minimum weight cycle in G,

576 
orthogonal to the vector orth as per [p. 338, 1]

577 
"""

578 
T = nx.Graph() 
579  
580 
nodes_idx = {node: idx for idx, node in enumerate(G.nodes())} 
581 
idx_nodes = {idx: node for node, idx in nodes_idx.items()} 
582  
583 
nnodes = len(nodes_idx)

584  
585 
# Add 2 copies of each edge in G to T. If edge is in orth, add cross edge;

586 
# otherwise inplane edge

587 
for u, v, data in G.edges(data=True): 
588 
uidx, vidx = nodes_idx[u], nodes_idx[v] 
589 
edge_w = data.get(weight, 1)

590 
if frozenset((u, v)) in orth: 
591 
T.add_edges_from( 
592 
[(uidx, nnodes + vidx), (nnodes + uidx, vidx)], weight=edge_w) 
593 
else:

594 
T.add_edges_from( 
595 
[(uidx, vidx), (nnodes + uidx, nnodes + vidx)], weight=edge_w) 
596  
597 
all_shortest_pathlens = dict(nx.shortest_path_length(T, weight=weight))

598 
cross_paths_w_lens = {n: all_shortest_pathlens[n][nnodes + n] 
599 
for n in range(nnodes)} 
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, remap nodes in T to those in G

607 
min_path_nodes = [node if node < nnodes else node  nnodes 
608 
for node in min_path] 
609 
# Now remove the edges that occur two times

610 
mcycle_pruned = _path_to_cycle(min_path_nodes) 
611  
612 
return {frozenset((idx_nodes[u], idx_nodes[v])) for u, v in mcycle_pruned} 
613  
614  
615 
def _path_to_cycle(path): 
616 
"""

617 
Removes the edges from path that occur even number of times.

618 
Returns a set of edges

619 
"""

620 
edges = set()

621 
for edge in pairwise(path): 
622 
# Toggle whether to keep the current edge.

623 
edges ^= {edge} 
624 
return edges
