weavatrix_graph/undirected/
core.rs

1use super::{IndexUndirectedGraphView, UndirectedGraphView};
2use crate::Vec;
3use crate::topology::csr::Csr;
4use crate::{EdgeEndpoints, EdgeIndex, GraphError, NodeIndex, Result};
5use serde::{Deserialize, Deserializer, Serialize, de::Error as _};
6
7#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
8pub struct UndirectedTopology {
9    node_count: u32,
10    endpoints: Vec<EdgeEndpoints>,
11    #[serde(skip)]
12    incidence: Csr,
13}
14
15impl UndirectedTopology {
16    /// Builds an undirected topology with compact incidence CSR.
17    ///
18    /// Self-loops occupy one incidence entry and report degree two.
19    ///
20    /// # Errors
21    ///
22    /// Returns an error for capacity overflow or an endpoint outside the graph.
23    pub fn try_from_edges(
24        node_count: usize,
25        edges: impl IntoIterator<Item = EdgeEndpoints>,
26    ) -> Result<Self> {
27        let compact_node_count =
28            u32::try_from(node_count).map_err(|_| GraphError::IndexCapacityExceeded {
29                category: "nodes",
30                count: node_count,
31            })?;
32        let endpoints = edges.into_iter().collect::<Vec<_>>();
33        u32::try_from(endpoints.len()).map_err(|_| GraphError::IndexCapacityExceeded {
34            category: "edges",
35            count: endpoints.len(),
36        })?;
37        let incidence = Csr::try_build_undirected(node_count, &endpoints)?;
38        Ok(Self {
39            node_count: compact_node_count,
40            endpoints,
41            incidence,
42        })
43    }
44
45    #[must_use]
46    pub const fn node_count(&self) -> usize {
47        self.node_count as usize
48    }
49
50    #[must_use]
51    pub const fn edge_count(&self) -> usize {
52        self.endpoints.len()
53    }
54
55    #[must_use]
56    pub fn contains_node(&self, node: NodeIndex) -> bool {
57        node.index() < self.node_count()
58    }
59
60    #[must_use]
61    pub fn contains_edge(&self, edge: EdgeIndex) -> bool {
62        edge.index() < self.edge_count()
63    }
64
65    #[must_use]
66    pub fn edge_endpoints(&self, edge: EdgeIndex) -> Option<EdgeEndpoints> {
67        self.endpoints.get(edge.index()).copied()
68    }
69
70    #[must_use]
71    pub fn incident_edges(
72        &self,
73        node: NodeIndex,
74    ) -> impl DoubleEndedIterator<Item = EdgeIndex> + ExactSizeIterator + '_ {
75        self.incidence.get(node.index()).iter().copied()
76    }
77
78    #[must_use]
79    pub fn incident_edge_at(&self, node: NodeIndex, offset: usize) -> Option<EdgeIndex> {
80        self.incidence.get(node.index()).get(offset).copied()
81    }
82
83    #[must_use]
84    pub fn neighbors(
85        &self,
86        node: NodeIndex,
87    ) -> impl DoubleEndedIterator<Item = NodeIndex> + ExactSizeIterator + '_ {
88        self.incident_edges(node).map(move |edge| {
89            let endpoints = self.endpoints[edge.index()];
90            if endpoints.source() == node {
91                endpoints.target()
92            } else {
93                endpoints.source()
94            }
95        })
96    }
97
98    #[must_use]
99    pub fn degree(&self, node: NodeIndex) -> Option<usize> {
100        self.contains_node(node).then(|| {
101            self.incident_edges(node)
102                .map(|edge| {
103                    let endpoints = self.endpoints[edge.index()];
104                    usize::from(endpoints.source() == node && endpoints.target() == node)
105                })
106                .sum::<usize>()
107                + self.incident_edges(node).len()
108        })
109    }
110}
111
112impl UndirectedGraphView for UndirectedTopology {
113    type Node = NodeIndex;
114    type Edge = EdgeIndex;
115
116    fn node_count(&self) -> usize {
117        self.node_count()
118    }
119
120    fn edge_count(&self) -> usize {
121        self.edge_count()
122    }
123
124    fn contains_node(&self, node: NodeIndex) -> bool {
125        self.contains_node(node)
126    }
127
128    fn contains_edge(&self, edge: EdgeIndex) -> bool {
129        self.contains_edge(edge)
130    }
131
132    fn node_indices(&self) -> impl Iterator<Item = NodeIndex> + '_ {
133        (0..self.node_count).map(NodeIndex::new)
134    }
135
136    fn edge_indices(&self) -> impl Iterator<Item = EdgeIndex> + '_ {
137        let edge_count = u32::try_from(self.edge_count()).unwrap_or(u32::MAX);
138        (0..edge_count).map(EdgeIndex::new)
139    }
140
141    fn edge_endpoints(&self, edge: EdgeIndex) -> Option<EdgeEndpoints> {
142        self.edge_endpoints(edge)
143    }
144
145    fn incident_edges(
146        &self,
147        node: NodeIndex,
148    ) -> impl DoubleEndedIterator<Item = EdgeIndex> + ExactSizeIterator + '_ {
149        self.incident_edges(node)
150    }
151}
152
153impl IndexUndirectedGraphView for UndirectedTopology {
154    fn node_bound(&self) -> usize {
155        self.node_count()
156    }
157
158    fn edge_bound(&self) -> usize {
159        self.edge_count()
160    }
161
162    fn node_slot(node: NodeIndex) -> usize {
163        node.index()
164    }
165
166    fn edge_slot(edge: EdgeIndex) -> usize {
167        edge.index()
168    }
169
170    fn incident_edge_at(&self, node: NodeIndex, offset: usize) -> Option<EdgeIndex> {
171        self.incident_edge_at(node, offset)
172    }
173}
174
175#[derive(Deserialize)]
176struct UndirectedWire {
177    node_count: u32,
178    endpoints: Vec<EdgeEndpoints>,
179}
180
181impl<'de> Deserialize<'de> for UndirectedTopology {
182    fn deserialize<D>(deserializer: D) -> core::result::Result<Self, D::Error>
183    where
184        D: Deserializer<'de>,
185    {
186        let wire = UndirectedWire::deserialize(deserializer)?;
187        Self::try_from_edges(wire.node_count as usize, wire.endpoints).map_err(D::Error::custom)
188    }
189}
weavatrix_graph/undirected/core.rs

weavatrix_graph/undirected/
core.rs
