weavatrix_graph/
operator.rs

1use crate::{EdgeEndpoints, GraphError, IndexGraphView, NodeIndex, Result, Topology, Vec};
2
3#[derive(Debug, Clone)]
4pub struct TopologyProjection<Node> {
5    topology: Topology,
6    original_nodes: Vec<Node>,
7}
8
9impl<Node> TopologyProjection<Node> {
10    #[must_use]
11    pub const fn topology(&self) -> &Topology {
12        &self.topology
13    }
14
15    #[must_use]
16    pub fn original_nodes(&self) -> &[Node] {
17        &self.original_nodes
18    }
19
20    #[must_use]
21    pub fn original_node(&self, projected: NodeIndex) -> Option<&Node> {
22        self.original_nodes.get(projected.index())
23    }
24
25    #[must_use]
26    pub fn into_parts(self) -> (Topology, Vec<Node>) {
27        (self.topology, self.original_nodes)
28    }
29}
30
31/// Materializes the directed simple-graph complement.
32///
33/// Parallel edges collapse to one adjacency relation.
34///
35/// # Errors
36///
37/// Returns an error when the dense pair space or compact topology overflows.
38pub fn complement<G>(graph: &G, include_self_loops: bool) -> Result<TopologyProjection<G::Node>>
39where
40    G: IndexGraphView,
41{
42    let nodes = graph.node_indices().collect::<Vec<_>>();
43    let pair_count =
44        nodes
45            .len()
46            .checked_mul(nodes.len())
47            .ok_or(GraphError::ArithmeticOverflow {
48                operation: "graph complement pair count",
49            })?;
50    let mut positions = vec![None; graph.node_bound()];
51    for (index, node) in nodes.iter().copied().enumerate() {
52        positions[G::node_slot(node)] = Some(index);
53    }
54    let mut present = vec![false; pair_count];
55    for (_, endpoints) in graph.edge_references() {
56        let Some(source) = positions[G::node_slot(endpoints.source())] else {
57            continue;
58        };
59        let Some(target) = positions[G::node_slot(endpoints.target())] else {
60            continue;
61        };
62        present[source * nodes.len() + target] = true;
63    }
64    let mut edges = Vec::new();
65    for source in 0..nodes.len() {
66        for target in 0..nodes.len() {
67            if (include_self_loops || source != target) && !present[source * nodes.len() + target] {
68                edges.push(projected_endpoints(source, target)?);
69            }
70        }
71    }
72    Ok(TopologyProjection {
73        topology: Topology::try_from_edges(nodes.len(), edges)?,
74        original_nodes: nodes,
75    })
76}
77
78/// Materializes the simple union of two graphs by node identity.
79///
80/// # Errors
81///
82/// Returns an error when the compact result exceeds topology capacity.
83pub fn union<Left, Right>(left: &Left, right: &Right) -> Result<TopologyProjection<Left::Node>>
84where
85    Left: IndexGraphView,
86    Right: IndexGraphView<Node = Left::Node>,
87{
88    let mut nodes = left.node_indices().collect::<Vec<_>>();
89    for node in right.node_indices() {
90        if !nodes.contains(&node) {
91            nodes.push(node);
92        }
93    }
94    let mut edges = Vec::with_capacity(left.edge_count() + right.edge_count());
95    append_projected_edges(left, &nodes, &mut edges)?;
96    append_projected_edges(right, &nodes, &mut edges)?;
97    edges.sort_unstable_by_key(|edge| (edge.source(), edge.target()));
98    edges.dedup();
99    Ok(TopologyProjection {
100        topology: Topology::try_from_edges(nodes.len(), edges)?,
101        original_nodes: nodes,
102    })
103}
104
105fn append_projected_edges<G>(
106    graph: &G,
107    nodes: &[G::Node],
108    edges: &mut Vec<EdgeEndpoints>,
109) -> Result<()>
110where
111    G: IndexGraphView,
112{
113    for (_, endpoints) in graph.edge_references() {
114        let source = nodes
115            .iter()
116            .position(|node| *node == endpoints.source())
117            .ok_or(GraphError::InvalidNodeIndex {
118                node: G::node_slot(endpoints.source()),
119                node_count: nodes.len(),
120            })?;
121        let target = nodes
122            .iter()
123            .position(|node| *node == endpoints.target())
124            .ok_or(GraphError::InvalidNodeIndex {
125                node: G::node_slot(endpoints.target()),
126                node_count: nodes.len(),
127            })?;
128        edges.push(projected_endpoints(source, target)?);
129    }
130    Ok(())
131}
132
133fn projected_endpoints(source: usize, target: usize) -> Result<EdgeEndpoints> {
134    let source = u32::try_from(source).map_err(|_| GraphError::IndexCapacityExceeded {
135        category: "nodes",
136        count: source,
137    })?;
138    let target = u32::try_from(target).map_err(|_| GraphError::IndexCapacityExceeded {
139        category: "nodes",
140        count: target,
141    })?;
142    Ok(EdgeEndpoints::new(
143        NodeIndex::new(source),
144        NodeIndex::new(target),
145    ))
146}
weavatrix_graph/operator.rs

weavatrix_graph/
operator.rs
