weavatrix_graph/algo/components/
dag.rs

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

weavatrix_graph/algo/components/
dag.rs
