all_circuits

Contents

all_circuits#

graph_tool.topology.all_circuits(g, unique=False, max_length=0)[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.

max_length: ``int`` (optional, default: ``0``)

The maximum circuit length to consider. Beyond this it truncates the depth-first search, reducing the computation time by ignoring longer circuits. The default value of max_length = 0 implies no maximum.

Returns:
cycle_iteratoriterator over a sequence of integers

Iterator over sequences of vertices that form a circuit.

Notes

This algorithm [johnson-finding-1975] [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