weavatrix_graph/algo/components/
condensation.rs

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

weavatrix_graph/algo/components/
condensation.rs
