weavatrix_graph/topology/
core.rs

1use super::csr::Csr;
2use super::{EdgeEndpoints, EdgeIndex, GraphView, IndexGraphView, NodeIndex};
3use crate::Vec;
4use crate::{GraphError, Result};
5use serde::{Deserialize, Deserializer, Serialize, de::Error as _};
6
7#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
8pub struct Topology {
9    node_count: u32,
10    endpoints: Vec<EdgeEndpoints>,
11    #[serde(skip)]
12    outgoing: Csr,
13    #[serde(skip)]
14    incoming: Csr,
15}
16
17impl Topology {
18    /// Builds a validated directed topology with incoming and outgoing CSR.
19    ///
20    /// # Errors
21    ///
22    /// Returns an error when the graph exceeds the compact index capacity or
23    /// an endpoint is outside `node_count`.
24    pub fn try_from_edges(
25        node_count: usize,
26        edges: impl IntoIterator<Item = EdgeEndpoints>,
27    ) -> Result<Self> {
28        Self::try_from_collected(node_count, edges.into_iter().collect())
29    }
30
31    pub(super) fn try_from_collected(
32        node_count: usize,
33        endpoints: Vec<EdgeEndpoints>,
34    ) -> Result<Self> {
35        let compact_node_count = Self::validate_capacity(node_count, endpoints.len())?;
36        let (outgoing, incoming) = Csr::try_build_pair(node_count, &endpoints)?;
37        Ok(Self::from_parts(
38            compact_node_count,
39            endpoints,
40            outgoing,
41            incoming,
42        ))
43    }
44
45    pub(super) fn validate_capacity(node_count: usize, edge_count: usize) -> Result<u32> {
46        let compact_node_count =
47            u32::try_from(node_count).map_err(|_| GraphError::IndexCapacityExceeded {
48                category: "nodes",
49                count: node_count,
50            })?;
51        u32::try_from(edge_count).map_err(|_| GraphError::IndexCapacityExceeded {
52            category: "edges",
53            count: edge_count,
54        })?;
55        Ok(compact_node_count)
56    }
57
58    pub(super) fn from_parts(
59        node_count: u32,
60        endpoints: Vec<EdgeEndpoints>,
61        outgoing: Csr,
62        incoming: Csr,
63    ) -> Self {
64        Self {
65            node_count,
66            endpoints,
67            outgoing,
68            incoming,
69        }
70    }
71
72    pub(crate) fn try_from_usize_edges(
73        node_count: usize,
74        edges: impl IntoIterator<Item = (usize, usize)>,
75    ) -> Result<Self> {
76        let mut endpoints = Vec::new();
77        for (source, target) in edges {
78            endpoints.push(EdgeEndpoints::new(
79                compact_node(source)?,
80                compact_node(target)?,
81            ));
82        }
83        Self::try_from_edges(node_count, endpoints)
84    }
85
86    #[must_use]
87    pub const fn node_count(&self) -> usize {
88        self.node_count as usize
89    }
90
91    #[must_use]
92    pub const fn edge_count(&self) -> usize {
93        self.endpoints.len()
94    }
95
96    #[must_use]
97    pub fn contains_node(&self, node: NodeIndex) -> bool {
98        node.index() < self.node_count()
99    }
100
101    #[must_use]
102    pub fn contains_edge(&self, edge: EdgeIndex) -> bool {
103        edge.index() < self.edge_count()
104    }
105
106    #[must_use]
107    pub fn edge_endpoints(&self, edge: EdgeIndex) -> Option<EdgeEndpoints> {
108        self.endpoints.get(edge.index()).copied()
109    }
110
111    #[must_use]
112    pub fn outgoing_edges(
113        &self,
114        node: NodeIndex,
115    ) -> impl DoubleEndedIterator<Item = EdgeIndex> + ExactSizeIterator + '_ {
116        self.outgoing.get(node.index()).iter().copied()
117    }
118
119    #[must_use]
120    pub fn incoming_edges(
121        &self,
122        node: NodeIndex,
123    ) -> impl DoubleEndedIterator<Item = EdgeIndex> + ExactSizeIterator + '_ {
124        self.incoming.get(node.index()).iter().copied()
125    }
126
127    #[must_use]
128    pub fn outgoing_neighbors(
129        &self,
130        node: NodeIndex,
131    ) -> impl DoubleEndedIterator<Item = NodeIndex> + ExactSizeIterator + '_ {
132        self.outgoing_edges(node)
133            .map(|edge| self.endpoints[edge.index()].target())
134    }
135
136    #[must_use]
137    pub fn incoming_neighbors(
138        &self,
139        node: NodeIndex,
140    ) -> impl DoubleEndedIterator<Item = NodeIndex> + ExactSizeIterator + '_ {
141        self.incoming_edges(node)
142            .map(|edge| self.endpoints[edge.index()].source())
143    }
144
145    #[must_use]
146    pub fn out_degree(&self, node: NodeIndex) -> Option<usize> {
147        self.contains_node(node)
148            .then(|| self.outgoing.get(node.index()).len())
149    }
150
151    #[must_use]
152    pub fn in_degree(&self, node: NodeIndex) -> Option<usize> {
153        self.contains_node(node)
154            .then(|| self.incoming.get(node.index()).len())
155    }
156
157    pub(crate) fn traversal_parts(&self) -> (&[EdgeEndpoints], &Csr, &Csr) {
158        (&self.endpoints, &self.outgoing, &self.incoming)
159    }
160}
161
162impl GraphView for Topology {
163    type Node = NodeIndex;
164    type Edge = EdgeIndex;
165
166    fn node_count(&self) -> usize {
167        self.node_count()
168    }
169
170    fn edge_count(&self) -> usize {
171        self.edge_count()
172    }
173
174    fn contains_node(&self, node: NodeIndex) -> bool {
175        self.contains_node(node)
176    }
177
178    fn contains_edge(&self, edge: EdgeIndex) -> bool {
179        self.contains_edge(edge)
180    }
181
182    fn node_indices(&self) -> impl Iterator<Item = Self::Node> + '_ {
183        (0..self.node_count).map(NodeIndex::new)
184    }
185
186    fn edge_indices(&self) -> impl Iterator<Item = Self::Edge> + '_ {
187        (0..u32::try_from(self.edge_count()).expect("edge count was checked")).map(EdgeIndex::new)
188    }
189
190    fn edge_endpoints(&self, edge: EdgeIndex) -> Option<EdgeEndpoints> {
191        self.edge_endpoints(edge)
192    }
193
194    fn edge_references(&self) -> impl Iterator<Item = (EdgeIndex, EdgeEndpoints)> + '_ {
195        self.edge_indices().zip(self.endpoints.iter().copied())
196    }
197
198    fn outgoing_edges(&self, node: NodeIndex) -> impl Iterator<Item = EdgeIndex> + '_ {
199        self.outgoing_edges(node)
200    }
201
202    fn incoming_edges(&self, node: NodeIndex) -> impl Iterator<Item = EdgeIndex> + '_ {
203        self.incoming_edges(node)
204    }
205}
206
207impl IndexGraphView for Topology {
208    fn node_bound(&self) -> usize {
209        self.node_count()
210    }
211
212    fn edge_bound(&self) -> usize {
213        self.edge_count()
214    }
215
216    fn node_slot(node: Self::Node) -> usize {
217        node.index()
218    }
219
220    fn edge_slot(edge: Self::Edge) -> usize {
221        edge.index()
222    }
223}
224
225#[derive(Deserialize)]
226struct TopologyWire {
227    node_count: u32,
228    endpoints: Vec<EdgeEndpoints>,
229}
230
231impl<'de> Deserialize<'de> for Topology {
232    fn deserialize<D>(deserializer: D) -> core::result::Result<Self, D::Error>
233    where
234        D: Deserializer<'de>,
235    {
236        let wire = TopologyWire::deserialize(deserializer)?;
237        Self::try_from_edges(wire.node_count as usize, wire.endpoints).map_err(D::Error::custom)
238    }
239}
240
241fn compact_node(index: usize) -> Result<NodeIndex> {
242    u32::try_from(index)
243        .map(NodeIndex::new)
244        .map_err(|_| GraphError::IndexCapacityExceeded {
245            category: "node index",
246            count: index,
247        })
248}
weavatrix_graph/topology/core.rs

weavatrix_graph/topology/
core.rs
