rustworkx.cycle_basis#

cycle_basis(graph, /, root=None)#

Return a list of cycles which form a basis for cycles of a given PyGraph

A basis for cycles of a graph is a minimal collection of cycles such that any cycle in the graph can be written as a sum of cycles in the basis. Here summation of cycles is defined as the exclusive or of the edges.

This is adapted from algorithm CACM 491 [1].

Note

The function implicitly assumes that there are no parallel edges. It may produce incorrect/unexpected results if the input graph has parallel edges.

Parameters:

  • graph (PyGraph) – The graph to find the cycle basis in

  • root (int) – Optional index for starting node for basis

Returns:

A list of cycle lists. Each list is a list of node ids which forms a cycle (loop) in the input graph

Return type:

list