weavatrix_graph/algo/
components.rs

1use super::traversal::{Direction, for_each_neighbor};
2use crate::IndexGraphView;
3use std::collections::VecDeque;
4
5#[must_use]
6pub fn strongly_connected_components<G>(graph: &G) -> Vec<Vec<G::Node>>
7where
8    G: IndexGraphView,
9{
10    let mut seen = vec![false; graph.node_bound()];
11    let mut finish = Vec::with_capacity(graph.node_count());
12    for start in graph.node_indices() {
13        finish_from(graph, start, &mut seen, &mut finish);
14    }
15
16    seen.fill(false);
17    let mut components = Vec::new();
18    for start in finish.into_iter().rev() {
19        if seen[G::node_slot(start)] {
20            continue;
21        }
22        let mut component = Vec::new();
23        let mut stack = vec![start];
24        seen[G::node_slot(start)] = true;
25        while let Some(node) = stack.pop() {
26            component.push(node);
27            for_each_neighbor(
28                graph,
29                node,
30                Direction::Incoming,
31                &mut |_| true,
32                |neighbor| {
33                    let slot = G::node_slot(neighbor);
34                    if !seen[slot] {
35                        seen[slot] = true;
36                        stack.push(neighbor);
37                    }
38                },
39            );
40        }
41        components.push(component);
42    }
43    components
44}
45
46#[must_use]
47pub fn topological_sort<G>(graph: &G) -> Option<Vec<G::Node>>
48where
49    G: IndexGraphView,
50{
51    let mut indegree = vec![0_usize; graph.node_bound()];
52    for edge in graph.edge_indices() {
53        if let Some(endpoints) = graph.edge_endpoints(edge) {
54            indegree[G::node_slot(endpoints.target())] += 1;
55        }
56    }
57    let mut ready = graph
58        .node_indices()
59        .filter(|node| indegree[G::node_slot(*node)] == 0)
60        .collect::<VecDeque<_>>();
61    let mut order = Vec::with_capacity(graph.node_count());
62    while let Some(node) = ready.pop_front() {
63        order.push(node);
64        for edge in graph.outgoing_edges(node) {
65            let Some(endpoints) = graph.edge_endpoints(edge) else {
66                continue;
67            };
68            let slot = G::node_slot(endpoints.target());
69            indegree[slot] -= 1;
70            if indegree[slot] == 0 {
71                ready.push_back(endpoints.target());
72            }
73        }
74    }
75    (order.len() == graph.node_count()).then_some(order)
76}
77
78#[must_use]
79pub fn has_cycle<G>(graph: &G) -> bool
80where
81    G: IndexGraphView,
82{
83    topological_sort(graph).is_none()
84}
85
86#[must_use]
87pub fn find_cycle<G>(graph: &G) -> Option<Vec<G::Node>>
88where
89    G: IndexGraphView,
90{
91    let mut adjacency = vec![Vec::new(); graph.node_bound()];
92    for edge in graph.edge_indices() {
93        if let Some(endpoints) = graph.edge_endpoints(edge) {
94            adjacency[G::node_slot(endpoints.source())].push(endpoints.target());
95        }
96    }
97    let mut color = vec![0_u8; graph.node_bound()];
98    let mut parent = vec![None; graph.node_bound()];
99    for start in graph.node_indices() {
100        if color[G::node_slot(start)] != 0 {
101            continue;
102        }
103        color[G::node_slot(start)] = 1;
104        let mut stack = vec![(start, 0_usize)];
105        while let Some((node, next)) = stack.last_mut() {
106            let slot = G::node_slot(*node);
107            let Some(&target) = adjacency[slot].get(*next) else {
108                color[slot] = 2;
109                stack.pop();
110                continue;
111            };
112            *next += 1;
113            let target_slot = G::node_slot(target);
114            if color[target_slot] == 0 {
115                parent[target_slot] = Some(*node);
116                color[target_slot] = 1;
117                stack.push((target, 0));
118            } else if color[target_slot] == 1 {
119                return reconstruct_cycle::<G>(*node, target, &parent);
120            }
121        }
122    }
123    None
124}
125
126fn reconstruct_cycle<G>(
127    node: G::Node,
128    target: G::Node,
129    parent: &[Option<G::Node>],
130) -> Option<Vec<G::Node>>
131where
132    G: IndexGraphView,
133{
134    let mut cycle = vec![node];
135    let mut cursor = node;
136    while cursor != target {
137        cursor = parent[G::node_slot(cursor)]?;
138        cycle.push(cursor);
139    }
140    cycle.reverse();
141    cycle.push(target);
142    Some(cycle)
143}
144
145fn finish_from<G>(graph: &G, start: G::Node, seen: &mut [bool], finish: &mut Vec<G::Node>)
146where
147    G: IndexGraphView,
148{
149    if seen[G::node_slot(start)] {
150        return;
151    }
152    let mut stack = vec![(start, false)];
153    while let Some((node, exiting)) = stack.pop() {
154        let slot = G::node_slot(node);
155        if exiting {
156            finish.push(node);
157            continue;
158        }
159        if seen[slot] {
160            continue;
161        }
162        seen[slot] = true;
163        stack.push((node, true));
164        for edge in graph.outgoing_edges(node).rev() {
165            let Some(target) = graph.edge_endpoints(edge).map(crate::EdgeEndpoints::target) else {
166                continue;
167            };
168            if !seen[G::node_slot(target)] {
169                stack.push((target, false));
170            }
171        }
172    }
173}
weavatrix_graph/algo/components.rs

weavatrix_graph/algo/
components.rs
