weavatrix_graph/algo/
transitive.rs

1use super::topological_sort_filtered;
2use crate::{EdgeEndpoints, IndexGraphView};
3
4#[derive(Debug, Clone, PartialEq, Eq)]
5pub struct DagTransitive<Node> {
6    reduction: Vec<EdgeEndpoints<Node>>,
7    closure: Vec<EdgeEndpoints<Node>>,
8}
9
10impl<Node> DagTransitive<Node> {
11    #[must_use]
12    pub fn reduction_edges(&self) -> &[EdgeEndpoints<Node>] {
13        &self.reduction
14    }
15
16    #[must_use]
17    pub fn closure_edges(&self) -> &[EdgeEndpoints<Node>] {
18        &self.closure
19    }
20
21    #[must_use]
22    pub fn into_parts(self) -> (Vec<EdgeEndpoints<Node>>, Vec<EdgeEndpoints<Node>>) {
23        (self.reduction, self.closure)
24    }
25}
26
27/// Computes a DAG's unique transitive reduction and transitive closure.
28///
29/// Returns `None` when the selected graph contains a directed cycle.
30#[must_use]
31pub fn dag_transitive_reduction_closure<G>(graph: &G) -> Option<DagTransitive<G::Node>>
32where
33    G: IndexGraphView,
34{
35    dag_transitive_reduction_closure_filtered(graph, |_| true)
36}
37
38/// Computes transitive reduction and closure over selected edges.
39///
40/// Results are deterministically ordered by the graph's topological order.
41/// Returns `None` when the selected graph contains a directed cycle.
42#[must_use]
43pub fn dag_transitive_reduction_closure_filtered<G, F>(
44    graph: &G,
45    allows_edge: F,
46) -> Option<DagTransitive<G::Node>>
47where
48    G: IndexGraphView,
49    F: Fn(G::Edge) -> bool,
50{
51    let order = topological_sort_filtered(graph, &allows_edge)?;
52    let mut position = vec![None; graph.node_bound()];
53    for (index, &node) in order.iter().enumerate() {
54        position[G::node_slot(node)] = Some(index);
55    }
56    let mut successors = vec![Vec::new(); order.len()];
57    for (edge, endpoints) in graph.edge_references() {
58        if !allows_edge(edge) {
59            continue;
60        }
61        let source = position[G::node_slot(endpoints.source())]?;
62        let target = position[G::node_slot(endpoints.target())]?;
63        successors[source].push(target);
64    }
65    for targets in &mut successors {
66        targets.sort_unstable();
67        targets.dedup();
68    }
69
70    let words = order.len().div_ceil(u64::BITS as usize);
71    let mut reachable = vec![vec![0_u64; words]; order.len()];
72    let mut reduction = Vec::new();
73    for source in (0..order.len()).rev() {
74        for &target in &successors[source] {
75            if contains(&reachable[source], target) {
76                continue;
77            }
78            reduction.push((source, target));
79            let (before_target, target_and_after) = reachable.split_at_mut(target);
80            let source_row = &mut before_target[source];
81            let target_row = &target_and_after[0];
82            insert(source_row, target);
83            for (word, inherited) in source_row.iter_mut().zip(target_row) {
84                *word |= inherited;
85            }
86        }
87    }
88    reduction.sort_unstable();
89    let reduction = reduction
90        .into_iter()
91        .map(|(source, target)| EdgeEndpoints::new(order[source], order[target]))
92        .collect();
93    let mut closure = Vec::new();
94    for (source, row) in reachable.iter().enumerate() {
95        for target in 0..order.len() {
96            if contains(row, target) {
97                closure.push(EdgeEndpoints::new(order[source], order[target]));
98            }
99        }
100    }
101    Some(DagTransitive { reduction, closure })
102}
103
104fn contains(bits: &[u64], index: usize) -> bool {
105    bits[index / u64::BITS as usize] & (1_u64 << (index % u64::BITS as usize)) != 0
106}
107
108fn insert(bits: &mut [u64], index: usize) {
109    bits[index / u64::BITS as usize] |= 1_u64 << (index % u64::BITS as usize);
110}
weavatrix_graph/algo/transitive.rs

weavatrix_graph/algo/
transitive.rs
