#graph-algorithms #cycle

graph-cycles

Detect all cycles in a petgraph graph

2 unstable releases

Uses new Rust 2024

0.2.0 Feb 28, 2025
0.1.0 Jan 13, 2023

#130 in Math

Download history 1452/week @ 2024-12-09 1367/week @ 2024-12-16 647/week @ 2024-12-23 1229/week @ 2024-12-30 2355/week @ 2025-01-06 2480/week @ 2025-01-13 2033/week @ 2025-01-20 2899/week @ 2025-01-27 2575/week @ 2025-02-03 2425/week @ 2025-02-10 1429/week @ 2025-02-17 1363/week @ 2025-02-24 3514/week @ 2025-03-03 2561/week @ 2025-03-10 1839/week @ 2025-03-17 2206/week @ 2025-03-24

10,216 downloads per month
Used in 32 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.

Dependencies

~3MB
~45K SLoC