all_circuits

Contents

all_circuits#

graph_tool.topology.all_circuits(g, unique=False)[source]#

Return an iterator over all the cycles in a directed graph.

Parameters:
gGraph

A directed graph to be used. (Undirected graphs are also accepted, in which case each undirected edge is assumed to be equivalent to two directed edges in both directions.)

uniquebool (optional, default: None)

If True, parallel edges and self-loops will be ignored.

Returns:
cycle_iteratoriterator over a sequence of integers

Iterator over sequences of vertices that form a circuit.

Notes

This algorithm [R93ec26dfef43-johnson-finding-1975]_[R93ec26dfef43-hawick-enumerating-2008]_ runs in worst time \(O[(V + E)(C + 1)]\), where \(C\) is the number of circuits.

References

[johnson-finding-1975]

D.B. Johnson, “Finding all the elementary circuits of a directed graph”, SIAM Journal on Computing, 1975. DOI: 10.1137/0204007 [sci-hub, @tor]

[hawick-enumerating-2008]

K.A. Hawick and H.A. James, “Enumerating Circuits and Loops in Graphs with Self-Arcs and Multiple-Arcs.”, In Proceedings of FCS. 2008, 14-20, http://cssg.massey.ac.nz/cstn/013/cstn-013.html

Examples

>>> g = gt.random_graph(10, lambda: (1, 1))
>>> for c in gt.all_circuits(g):
...     print(c)
[0 6]
[1 5 4 9 7 2 8 3]
Contents