weavatrix_graph/algo/
transitive.rs

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

weavatrix_graph/algo/
transitive.rs
