graph-cycles

找到图中的所有循环

Johnson算法寻找图中所有循环的原始实现。基于petgraph。

示例

三角形图恰好有一个循环，即完全图本身。

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:?}");
});

注意事项

此crate基本上未经测试。

参考文献

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

许可证：MIT或Apache-2.0

lib.rs:

找到图中的所有循环

Johnson算法寻找图中所有循环的原始实现。基于petgraph。

示例

三角形图恰好有一个循环，即完全图本身。

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:?}");
});

注意事项

此crate基本上未经测试。

参考文献

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

底层图的节点标识符