networkx.algorithms.cycles.minimum_cycle_basis¶
-
minimum_cycle_basis
(G, weight=None)[source]¶ Returns a minimum weight cycle basis for G
Minimum weight means a cycle basis for which the total weight (length for unweighted graphs) of all the cycles is minimum.
Parameters: - G (NetworkX Graph)
- weight (string) – name of the edge attribute to use for edge weights
Returns: - A list of cycle lists. Each cycle list is a list of nodes
- which forms a cycle (loop) in G. Note that the nodes are not
- necessarily returned in a order by which they appear in the cycle
Examples
>>> G=nx.Graph() >>> G.add_cycle([0,1,2,3]) >>> G.add_cycle([0,3,4,5]) >>> print(nx.minimum_cycle_basis(G)) [[0, 1, 2, 3], [0, 3, 4, 5]]
References
[1] Kavitha, Telikepalli, et al. “An O(m^2n) Algorithm for Minimum Cycle Basis of Graphs.” http://link.springer.com/article/10.1007/s00453-007-9064-z [2] de Pina, J. 1995. Applications of shortest path methods. Ph.D. thesis, University of Amsterdam, Netherlands
See also