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 edges = edges.into_iter();
77        let mut endpoints = Vec::with_capacity(edges.size_hint().0);
78        for (source, target) in edges {
79            endpoints.push(EdgeEndpoints::new(
80                compact_node(source)?,
81                compact_node(target)?,
82            ));
83        }
84        Self::try_from_edges(node_count, endpoints)
85    }
86
87    #[must_use]
88    pub const fn node_count(&self) -> usize {
89        self.node_count as usize
90    }
91
92    #[must_use]
93    pub const fn edge_count(&self) -> usize {
94        self.endpoints.len()
95    }
96
97    #[must_use]
98    pub fn contains_node(&self, node: NodeIndex) -> bool {
99        node.index() < self.node_count()
100    }
101
102    #[must_use]
103    pub fn contains_edge(&self, edge: EdgeIndex) -> bool {
104        edge.index() < self.edge_count()
105    }
106
107    #[must_use]
108    pub fn edge_endpoints(&self, edge: EdgeIndex) -> Option<EdgeEndpoints> {
109        self.endpoints.get(edge.index()).copied()
110    }
111
112    #[must_use]
113    pub fn outgoing_edges(
114        &self,
115        node: NodeIndex,
116    ) -> impl DoubleEndedIterator<Item = EdgeIndex> + ExactSizeIterator + '_ {
117        self.outgoing.get(node.index()).iter().copied()
118    }
119
120    #[must_use]
121    pub fn incoming_edges(
122        &self,
123        node: NodeIndex,
124    ) -> impl DoubleEndedIterator<Item = EdgeIndex> + ExactSizeIterator + '_ {
125        self.incoming.get(node.index()).iter().copied()
126    }
127
128    #[must_use]
129    pub fn outgoing_neighbors(
130        &self,
131        node: NodeIndex,
132    ) -> impl DoubleEndedIterator<Item = NodeIndex> + ExactSizeIterator + '_ {
133        self.outgoing_edges(node)
134            .map(|edge| self.endpoints[edge.index()].target())
135    }
136
137    #[must_use]
138    pub fn incoming_neighbors(
139        &self,
140        node: NodeIndex,
141    ) -> impl DoubleEndedIterator<Item = NodeIndex> + ExactSizeIterator + '_ {
142        self.incoming_edges(node)
143            .map(|edge| self.endpoints[edge.index()].source())
144    }
145
146    #[must_use]
147    pub fn out_degree(&self, node: NodeIndex) -> Option<usize> {
148        self.contains_node(node)
149            .then(|| self.outgoing.get(node.index()).len())
150    }
151
152    #[must_use]
153    pub fn in_degree(&self, node: NodeIndex) -> Option<usize> {
154        self.contains_node(node)
155            .then(|| self.incoming.get(node.index()).len())
156    }
157
158    pub(crate) fn traversal_parts(&self) -> (&[EdgeEndpoints], &Csr, &Csr) {
159        (&self.endpoints, &self.outgoing, &self.incoming)
160    }
161}
162
163impl GraphView for Topology {
164    type Node = NodeIndex;
165    type Edge = EdgeIndex;
166
167    fn node_count(&self) -> usize {
168        self.node_count()
169    }
170
171    fn edge_count(&self) -> usize {
172        self.edge_count()
173    }
174
175    fn contains_node(&self, node: NodeIndex) -> bool {
176        self.contains_node(node)
177    }
178
179    fn contains_edge(&self, edge: EdgeIndex) -> bool {
180        self.contains_edge(edge)
181    }
182
183    fn node_indices(&self) -> impl Iterator<Item = Self::Node> + '_ {
184        (0..self.node_count).map(NodeIndex::new)
185    }
186
187    fn edge_indices(&self) -> impl Iterator<Item = Self::Edge> + '_ {
188        let edge_count = u32::try_from(self.edge_count()).unwrap_or(u32::MAX);
189        (0..edge_count).map(EdgeIndex::new)
190    }
191
192    fn edge_endpoints(&self, edge: EdgeIndex) -> Option<EdgeEndpoints> {
193        self.edge_endpoints(edge)
194    }
195
196    fn edge_references(&self) -> impl Iterator<Item = (EdgeIndex, EdgeEndpoints)> + '_ {
197        self.edge_indices().zip(self.endpoints.iter().copied())
198    }
199
200    fn outgoing_edges(&self, node: NodeIndex) -> impl Iterator<Item = EdgeIndex> + '_ {
201        self.outgoing_edges(node)
202    }
203
204    fn incoming_edges(&self, node: NodeIndex) -> impl Iterator<Item = EdgeIndex> + '_ {
205        self.incoming_edges(node)
206    }
207}
208
209impl IndexGraphView for Topology {
210    fn node_bound(&self) -> usize {
211        self.node_count()
212    }
213
214    fn edge_bound(&self) -> usize {
215        self.edge_count()
216    }
217
218    fn node_slot(node: Self::Node) -> usize {
219        node.index()
220    }
221
222    fn edge_slot(edge: Self::Edge) -> usize {
223        edge.index()
224    }
225}
226
227#[derive(Deserialize)]
228struct TopologyWire {
229    node_count: u32,
230    endpoints: Vec<EdgeEndpoints>,
231}
232
233impl<'de> Deserialize<'de> for Topology {
234    fn deserialize<D>(deserializer: D) -> core::result::Result<Self, D::Error>
235    where
236        D: Deserializer<'de>,
237    {
238        let wire = TopologyWire::deserialize(deserializer)?;
239        Self::try_from_edges(wire.node_count as usize, wire.endpoints).map_err(D::Error::custom)
240    }
241}
242
243fn compact_node(index: usize) -> Result<NodeIndex> {
244    u32::try_from(index)
245        .map(NodeIndex::new)
246        .map_err(|_| GraphError::IndexCapacityExceeded {
247            category: "node index",
248            count: index,
249        })
250}
weavatrix_graph/topology/core.rs

weavatrix_graph/topology/
core.rs
