weavatrix_graph/algo/components/
condensation.rs

1use super::scc;
2use crate::{EdgeEndpoints, GraphError, IndexGraphView, NodeIndex, Result, Topology};
3use std::collections::HashMap;
4use std::hash::Hash;
5
6#[derive(Clone, Debug)]
7pub struct Condensation<Node> {
8    components: Vec<Vec<Node>>,
9    component_by_node: HashMap<Node, NodeIndex>,
10    topology: Topology,
11}
12
13impl<Node> Condensation<Node>
14where
15    Node: Copy + Eq + Hash,
16{
17    #[must_use]
18    pub fn components(&self) -> &[Vec<Node>] {
19        &self.components
20    }
21
22    #[must_use]
23    pub fn component(&self, index: NodeIndex) -> Option<&[Node]> {
24        self.components.get(index.index()).map(Vec::as_slice)
25    }
26
27    #[must_use]
28    pub fn component_of(&self, node: Node) -> Option<NodeIndex> {
29        self.component_by_node.get(&node).copied()
30    }
31
32    #[must_use]
33    pub const fn topology(&self) -> &Topology {
34        &self.topology
35    }
36
37    #[must_use]
38    pub fn into_parts(self) -> (Vec<Vec<Node>>, Topology) {
39        (self.components, self.topology)
40    }
41}
42
43/// Builds the acyclic graph of strongly connected components.
44///
45/// # Errors
46///
47/// Returns an error when the compact component topology exceeds index capacity.
48pub fn condensation<G>(graph: &G) -> Result<Condensation<G::Node>>
49where
50    G: IndexGraphView,
51{
52    let allows_edge = |_| true;
53    let components = scc::with_filter(graph, &allows_edge);
54    build(graph, components, &allows_edge)
55}
56
57/// Builds a condensation DAG using only edges accepted by `allows_edge`.
58///
59/// # Errors
60///
61/// Returns an error when the compact component topology exceeds index capacity.
62pub fn condensation_filtered<G, F>(graph: &G, allows_edge: F) -> Result<Condensation<G::Node>>
63where
64    G: IndexGraphView,
65    F: Fn(G::Edge) -> bool,
66{
67    let components = scc::with_filter(graph, &allows_edge);
68    build(graph, components, &allows_edge)
69}
70
71fn build<G, F>(
72    graph: &G,
73    components: Vec<Vec<G::Node>>,
74    allows_edge: &F,
75) -> Result<Condensation<G::Node>>
76where
77    G: IndexGraphView,
78    F: Fn(G::Edge) -> bool,
79{
80    let mut component_by_node = HashMap::with_capacity(graph.node_count());
81    let mut component_by_slot = vec![None; graph.node_bound()];
82    for (position, component) in components.iter().enumerate() {
83        let compact = u32::try_from(position).map_err(|_| GraphError::IndexCapacityExceeded {
84            category: "components",
85            count: components.len(),
86        })?;
87        for &node in component {
88            let index = NodeIndex::new(compact);
89            component_by_node.insert(node, index);
90            if let Some(slot) = component_by_slot.get_mut(G::node_slot(node)) {
91                *slot = Some(index);
92            }
93        }
94    }
95
96    let mut edges = Vec::new();
97    for (edge, endpoints) in graph.edge_references() {
98        if !allows_edge(edge) {
99            continue;
100        }
101        let (Some(Some(source)), Some(Some(target))) = (
102            component_by_slot.get(G::node_slot(endpoints.source())),
103            component_by_slot.get(G::node_slot(endpoints.target())),
104        ) else {
105            continue;
106        };
107        if source != target {
108            edges.push(EdgeEndpoints::new(*source, *target));
109        }
110    }
111    edges.sort_unstable_by_key(|edge| (edge.source().index(), edge.target().index()));
112    edges.dedup();
113    let topology = Topology::try_from_edges(components.len(), edges)?;
114    Ok(Condensation {
115        components,
116        component_by_node,
117        topology,
118    })
119}
weavatrix_graph/algo/components/condensation.rs

weavatrix_graph/algo/components/
condensation.rs
