1 unstable release

0.1.0 Jan 13, 2023

#1323 in Math

Download history 1298/week @ 2024-07-22 1743/week @ 2024-07-29 1064/week @ 2024-08-05 1730/week @ 2024-08-12 2383/week @ 2024-08-19 2541/week @ 2024-08-26 2299/week @ 2024-09-02 1695/week @ 2024-09-09 2769/week @ 2024-09-16 2449/week @ 2024-09-23 2002/week @ 2024-09-30 1984/week @ 2024-10-07 2060/week @ 2024-10-14 3413/week @ 2024-10-21 2409/week @ 2024-10-28 2046/week @ 2024-11-04

10,071 downloads per month
Used in 25 crates (2 directly)

MIT/Apache

10KB
144 lines

graph-cycles

Find all cycles in a graph

A naive implementation of Johnson's algorithm to find all cycles in a graph. Based on petgraph.

Example

The triangle graph has exactly one cycle, namely the full graph itself.

use graph_cycles::Cycles;
use petgraph::graph::Graph;

let g = Graph::<(), ()>::from_edges([(0, 1), (1, 2), (2, 0)]);

// find all cycles
let cycles = g.cycles();
assert_eq!(cycles.len(), 1);
assert_eq!(cycles[0].len(), 3);

// print each cycle in turn
g.visit_all_cycles(|_g, c| {
   println!("Found new cycle with vertices {c:?}");
});

Caveats

This crate is essentially untested.

References

Donald B. Johnson, Finding all the elementary circuits of a directed graph, SIAM Journal on Computing, 1975.

License: MIT or Apache-2.0


lib.rs:

Find all cycles in a graph

A naive implementation of Johnson's algorithm to find all cycles in a graph. Based on petgraph.

Example

The triangle graph has exactly one cycle, namely the full graph itself.

use graph_cycles::Cycles;
use petgraph::graph::Graph;

let g = Graph::<(), ()>::from_edges([(0, 1), (1, 2), (2, 0)]);

// find all cycles
let cycles = g.cycles();
assert_eq!(cycles.len(), 1);
assert_eq!(cycles[0].len(), 3);

// print each cycle in turn
g.visit_all_cycles(|_g, c| {
   println!("Found new cycle with vertices {c:?}");
});

Caveats

This crate is essentially untested.

References

Donald B. Johnson, Finding all the elementary circuits of a directed graph, SIAM Journal on Computing, 1975.

The node identifier of the underlying graph

Dependencies

~3.5MB
~58K SLoC