1 unstable release
0.1.0 | Jan 13, 2023 |
---|
#1323 in Math
10,071 downloads per month
Used in 25 crates
(2 directly)
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