Function cycle_basis

pub fn cycle_basis<G>(graph: G, root: Option<G::NodeId>) -> Vec<Vec<G::NodeId>>
where
    G: NodeCount + IntoNeighbors + IntoNodeIdentifiers,
    G::NodeId: Eq + Hash,

Return a list of cycles which form a basis for cycles of a given graph.

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 Paton, K. An algorithm for finding a fundamental set of cycles of a graph. Comm. ACM 12, 9 (Sept 1969), 514-518.

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

Arguments:

• graph - The graph in which to find the basis.
• root - Optional node index for starting the basis search. If not specified, an arbitrary node is chosen.

Example

use petgraph::prelude::*;
use rustworkx_core::connectivity::cycle_basis;

let edge_list = [(0, 1), (0, 3), (0, 5), (1, 2), (2, 3), (3, 4), (4, 5)];
let graph = UnGraph::<i32, i32>::from_edges(&edge_list);
let mut res: Vec<Vec<NodeIndex>> = cycle_basis(&graph, Some(NodeIndex::new(0)));