weavatrix_graph/undirected/
core.rs

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

weavatrix_graph/undirected/
core.rs
