adj_vector_graph/
adj_vector_graph.rs

1use modular_decomposition::{modular_decomposition, ModuleKind};
2use petgraph::dot::Config::EdgeNoLabel;
3use petgraph::dot::Dot;
4use petgraph::visit::{Dfs, GraphBase, GraphProp, IntoNeighbors, NodeCompactIndexable, NodeCount, NodeIndexable};
5use petgraph::{Incoming, Undirected};
6
7struct Graph(Vec<Vec<usize>>);
8
9impl Graph {
10    fn from_edges(edges: impl IntoIterator<Item = (usize, usize)>) -> Self {
11        let mut adj = vec![];
12        for (u, v) in edges {
13            assert_ne!(u, v);
14            if u >= adj.len() {
15                adj.resize(u + 1, vec![])
16            }
17            if v >= adj.len() {
18                adj.resize(v + 1, vec![])
19            }
20            adj[u].push(v);
21            adj[v].push(u);
22        }
23        Self(adj)
24    }
25}
26
27impl GraphBase for Graph {
28    type EdgeId = usize;
29    type NodeId = usize;
30}
31
32impl GraphProp for Graph {
33    type EdgeType = Undirected;
34}
35
36struct Neighbors<'a>(std::slice::Iter<'a, usize>);
37
38impl<'a> Iterator for Neighbors<'a> {
39    type Item = usize;
40    fn next(&mut self) -> Option<Self::Item> {
41        self.0.next().copied()
42    }
43}
44
45impl<'a> IntoNeighbors for &'a Graph {
46    type Neighbors = Neighbors<'a>;
47    fn neighbors(self, a: Self::NodeId) -> Self::Neighbors {
48        Neighbors(self.0[a].iter())
49    }
50}
51
52impl NodeCount for Graph {
53    fn node_count(&self) -> usize {
54        self.0.len()
55    }
56}
57
58impl NodeIndexable for Graph {
59    fn node_bound(&self) -> usize {
60        self.node_count()
61    }
62    fn to_index(&self, a: Self::NodeId) -> usize {
63        a
64    }
65    fn from_index(&self, i: usize) -> Self::NodeId {
66        i
67    }
68}
69
70impl NodeCompactIndexable for Graph {}
71
72fn main() {
73    let graph = Graph::from_edges([(0, 1), (1, 2), (2, 3)]);
74    let tree = modular_decomposition(&graph).map(|tree| tree.into_digraph()).unwrap_or_default();
75    println!("{:?}", Dot::with_config(&tree, &[EdgeNoLabel]));
76
77    let mut factorizing_permutation = Vec::new();
78    let root = tree.externals(Incoming).next().unwrap();
79    let mut dfs = Dfs::new(&tree, root);
80    while let Some(node) = dfs.next(&tree) {
81        if let ModuleKind::Node(u) = tree[node] {
82            factorizing_permutation.push(u);
83        }
84    }
85    let factorizing_permutation: Vec<_> = factorizing_permutation.to_vec();
86    println!("{:?}", factorizing_permutation);
87}
adj_vector_graph/adj_vector_graph.rs

adj_vector_graph/
adj_vector_graph.rs
