## iof-tools / networkxMiCe / networkx-master / networkx / algorithms / cycles.py @ 5cef0f13

History | View | Annotate | Download (21.6 KB)

1 | 5cef0f13 | tiamilani | ```
# Copyright (C) 2010-2019 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), 514-518.
``` |
||

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 last-in 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. 79-80 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, 77-84, 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, 163-182, 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, 192-204, 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. 79-80 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, 77-84, 1975.
``` |
||

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

283 | ```
``` |
||

284 | ```
See Also
``` |
||

285 | ```
--------
``` |
||

286 | ```
simple_cycles, cycle_basis
``` |
||

287 | ```
"""
``` |
||

288 | ```
# Jon Olav Vik, 2010-08-09
``` |
||

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 depth-first 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/s00453-007-9064-z
``` |
||

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 in-plane 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, re-map 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` |