id_graph_sccs

下载： crates.io/crates/id_graph_sccs

文档： docs.rs/id_graph_sccs

一个小型库，用于查找有向图的强连通分量。

此库基于id_collections库构建，旨在与节点由整数索引标记的图一起使用，这些索引属于从零到某个上界的不连续范围。输入图的边不需要以任何特定格式存储；调用者通过回调函数提供每个节点的出边，该函数在算法遍历图时按需调用。

算法的实现不依赖于递归，因此可以在不冒险栈溢出的情况下安全地运行在任意大小的图上。

示例

use id_collections::{id_type, IdVec};
use id_graph_sccs::{find_components, Sccs, Scc, SccKind};

#[id_type]
struct NodeId(u32);

#[id_type]
struct SccId(u32);

// Note: you are not required to store the edges of the input graph in an 'IdVec'; all that
// matters is that you are able to pass a closure to the 'find_components' function which
// returns the edges for a given node.
let mut graph: IdVec<NodeId, Vec<NodeId>> = IdVec::new();

let node_a = graph.push(Vec::new());
let node_b = graph.push(Vec::new());
let node_c = graph.push(Vec::new());
let node_d = graph.push(Vec::new());

graph[node_a].extend([node_a, node_b]);
graph[node_b].extend([node_c]);
graph[node_c].extend([node_b, node_d]);

let sccs: Sccs<SccId, NodeId> = find_components(graph.count(), |node| &graph[node]);

// We can iterate over 'sccs' to obtain the components of the graph:
let mut components: Vec<Scc<NodeId>> = Vec::new();
for (_scc_id, component) in &sccs {
    components.push(component);
}

assert_eq!(components.len(), 3);

assert_eq!(components[0].kind, SccKind::Acyclic);
assert_eq!(components[0].nodes, &[node_d]);

assert_eq!(components[1].kind, SccKind::Cyclic);
assert!(components[1].nodes.contains(&node_b));
assert!(components[1].nodes.contains(&node_c));

assert_eq!(components[2].kind, SccKind::Cyclic);
assert_eq!(components[2].nodes, &[node_a]);