I have an array of tuples; say,
[(1,2), (2,1), (3,4), (4,5), (5,3)]
There are two cycles in the above; one of length 2 and one of length 3. Is there a built-in function (or package) in Python that allows me to return a list of all cycle lengths? For the above example, it should return [2, 3].
The other answer demonstrated NetworkX, which would be my choice here too. But that is a 3rd-party project, and since you specifically asked:
Is there a built-in function (or package) ...
There is actually a stdlib which can help: graphlib (new in Python 3.9).
There's not much in there yet. It does not have a function for extracting cycle lengths from a graph, but there is a TopologicalSorter class which can produce a topological ordering of nodes in acyclic graphs. A CycleError exception is raised when the topological sorter has detected a cycle in the input:
class CycleError(ValueError):
"""Subclass of ValueError raised by TopologicalSorter.prepare if cycles
exist in the working graph.
If multiple cycles exist, only one undefined choice among them will be reported
and included in the exception. The detected cycle can be accessed via the second
element in the *args* attribute of the exception instance and consists in a list
of nodes, such that each node is, in the graph, an immediate predecessor of the
next node in the list. In the reported list, the first and the last node will be
the same, to make it clear that it is cyclic.
"""
Of particular note is that the error actually reveals the cycle, so without too much extra work you could extract cycle lengths from a graph via the topological sorter. Create the graph sorter:
import graphlib
edges = [(1,2), (2,1), (3,4), (4,5), (5,3)]
ts = graphlib.TopologicalSorter()
for edge in edges:
ts.add(*edge)
And then write a helper function to extract a cycle from a failed prepare() call:
def get_cycle(ts):
try:
ts.prepare()
except graphlib.CycleError as err:
msg, cycle = err.args
return list(zip(cycle[1:], cycle))
Example:
>>> cycle = get_cycle(ts)
>>> print(cycle)
[(2, 1), (1, 2)]
>>> print(len(cycle))
2
Note that this only returns the first cycle encountered. To find another cycle, remove an edge of the detected one from the graph (breaking that cycle) and repeat this process until all are found.
>>> edges.remove(cycle[0])
>>> ts = ...
>>> get_cycle(ts)
[(5, 3), (4, 5), (3, 4)]
NetworkX is probably easier, so just use that if you can!
You can use the third-party library networkx:
import networkx as nx
edges = [(1, 2), (2, 1), (3, 4), (4, 5), (5, 3)]
G = nx.DiGraph(edges)
[len(cycle) for cycle in list(nx.simple_cycles(G))] # [3, 2]
