weavatrix_graph/graph/
core.rs

1use super::bulk;
2use crate::{
3    Edge, EdgeEndpoints, EdgeIndex, GraphView, IndexGraphView, Node, NodeId, NodeIndex, Result,
4    Topology,
5};
6use serde::{Deserialize, Deserializer, Serialize, de::Error as _};
7
8/// Backward-compatible name for a compact topology node index.
9pub type GraphNodeIndex = NodeIndex;
10
11#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
12pub struct Graph {
13    nodes: Vec<Node>,
14    edges: Vec<Edge>,
15    #[serde(skip)]
16    topology: Topology,
17}
18
19impl Graph {
20    pub(super) const fn from_indexed_parts(
21        nodes: Vec<Node>,
22        edges: Vec<Edge>,
23        topology: Topology,
24    ) -> Self {
25        Self {
26            nodes,
27            edges,
28            topology,
29        }
30    }
31
32    pub(crate) fn from_validated_sorted_parts(nodes: Vec<Node>, edges: Vec<Edge>) -> Result<Self> {
33        let topology = super::index::index_canonical_edges(&nodes, &edges)?;
34        Ok(Self::from_indexed_parts(nodes, edges, topology))
35    }
36
37    /// Creates a validated graph and canonicalizes its ordering.
38    ///
39    /// # Errors
40    ///
41    /// Returns an error for conflicting nodes, dangling edges, empty extractor
42    /// identities, or invalid source spans.
43    pub fn try_from_parts(
44        nodes: impl IntoIterator<Item = Node>,
45        edges: impl IntoIterator<Item = Edge>,
46    ) -> Result<Self> {
47        bulk::canonical(nodes, edges)
48    }
49
50    /// Builds a canonical graph without re-sorting already sorted nodes.
51    ///
52    /// Unsorted nodes safely fall back to [`Self::try_from_parts`]. Edges may
53    /// arrive in any order and are still validated, sorted, and deduplicated.
54    ///
55    /// # Errors
56    ///
57    /// Returns the same validation errors as [`Self::try_from_parts`].
58    pub fn try_from_sorted_nodes(
59        nodes: Vec<Node>,
60        edges: impl IntoIterator<Item = Edge>,
61    ) -> Result<Self> {
62        bulk::from_sorted_nodes(nodes, edges)
63    }
64
65    /// Builds faster when nodes and edges are already in canonical order.
66    ///
67    /// Unordered input safely falls back to [`Self::try_from_parts`].
68    ///
69    /// # Errors
70    ///
71    /// Returns the same validation errors as [`Self::try_from_parts`].
72    pub fn try_from_sorted_parts(nodes: Vec<Node>, edges: Vec<Edge>) -> Result<Self> {
73        bulk::from_sorted_parts(nodes, edges)
74    }
75
76    #[must_use]
77    pub fn nodes(&self) -> &[Node] {
78        &self.nodes
79    }
80
81    #[must_use]
82    pub fn edges(&self) -> &[Edge] {
83        &self.edges
84    }
85
86    #[must_use]
87    pub const fn topology(&self) -> &Topology {
88        &self.topology
89    }
90
91    #[must_use]
92    pub fn node(&self, id: &str) -> Option<&Node> {
93        self.node_index(id).and_then(|index| self.node_at(index))
94    }
95
96    pub fn outgoing<'graph>(&'graph self, id: &NodeId) -> impl Iterator<Item = &'graph Edge> {
97        self.node_index(id.as_str())
98            .into_iter()
99            .flat_map(|index| self.topology.outgoing_edges(index))
100            .map(|edge| &self.edges[edge.index()])
101    }
102
103    pub fn incoming<'graph>(&'graph self, id: &NodeId) -> impl Iterator<Item = &'graph Edge> {
104        self.node_index(id.as_str())
105            .into_iter()
106            .flat_map(|index| self.topology.incoming_edges(index))
107            .map(|edge| &self.edges[edge.index()])
108    }
109
110    #[must_use]
111    pub fn edge_at(&self, index: EdgeIndex) -> Option<&Edge> {
112        self.edges.get(index.index())
113    }
114
115    #[must_use]
116    pub fn node_index(&self, id: &str) -> Option<GraphNodeIndex> {
117        self.nodes
118            .binary_search_by(|node| node.id.as_str().cmp(id))
119            .ok()
120            .and_then(|index| u32::try_from(index).ok())
121            .map(NodeIndex::new)
122    }
123
124    #[must_use]
125    pub fn node_at(&self, index: GraphNodeIndex) -> Option<&Node> {
126        self.nodes.get(index.index())
127    }
128
129    pub fn outgoing_at(&self, index: GraphNodeIndex) -> impl Iterator<Item = &Edge> {
130        self.topology
131            .outgoing_edges(index)
132            .map(|edge| &self.edges[edge.index()])
133    }
134
135    pub fn incoming_at(&self, index: GraphNodeIndex) -> impl Iterator<Item = &Edge> {
136        self.topology
137            .incoming_edges(index)
138            .map(|edge| &self.edges[edge.index()])
139    }
140
141    pub fn outgoing_neighbors_at(
142        &self,
143        index: GraphNodeIndex,
144    ) -> impl Iterator<Item = GraphNodeIndex> + '_ {
145        self.topology.outgoing_neighbors(index)
146    }
147
148    pub fn incoming_neighbors_at(
149        &self,
150        index: GraphNodeIndex,
151    ) -> impl Iterator<Item = GraphNodeIndex> + '_ {
152        self.topology.incoming_neighbors(index)
153    }
154
155    #[must_use]
156    pub fn out_degree(&self, index: GraphNodeIndex) -> Option<usize> {
157        self.topology.out_degree(index)
158    }
159
160    #[must_use]
161    pub fn in_degree(&self, index: GraphNodeIndex) -> Option<usize> {
162        self.topology.in_degree(index)
163    }
164
165    #[must_use]
166    pub const fn node_count(&self) -> usize {
167        self.nodes.len()
168    }
169
170    #[must_use]
171    pub const fn edge_count(&self) -> usize {
172        self.edges.len()
173    }
174
175    #[must_use]
176    pub const fn is_empty(&self) -> bool {
177        self.nodes.is_empty() && self.edges.is_empty()
178    }
179
180    #[must_use]
181    pub fn into_parts(self) -> (Vec<Node>, Vec<Edge>) {
182        (self.nodes, self.edges)
183    }
184}
185
186impl GraphView for Graph {
187    type Node = NodeIndex;
188    type Edge = EdgeIndex;
189
190    fn node_count(&self) -> usize {
191        self.node_count()
192    }
193
194    fn edge_count(&self) -> usize {
195        self.edge_count()
196    }
197
198    fn contains_node(&self, node: NodeIndex) -> bool {
199        self.node_at(node).is_some()
200    }
201
202    fn contains_edge(&self, edge: EdgeIndex) -> bool {
203        self.edge_at(edge).is_some()
204    }
205
206    fn node_indices(&self) -> impl Iterator<Item = Self::Node> + '_ {
207        self.topology.node_indices()
208    }
209
210    fn edge_indices(&self) -> impl Iterator<Item = Self::Edge> + '_ {
211        self.topology.edge_indices()
212    }
213
214    fn edge_endpoints(&self, edge: EdgeIndex) -> Option<EdgeEndpoints> {
215        self.topology.edge_endpoints(edge)
216    }
217
218    fn outgoing_edges(
219        &self,
220        node: NodeIndex,
221    ) -> impl DoubleEndedIterator<Item = EdgeIndex> + ExactSizeIterator + '_ {
222        self.topology.outgoing_edges(node)
223    }
224
225    fn incoming_edges(
226        &self,
227        node: NodeIndex,
228    ) -> impl DoubleEndedIterator<Item = EdgeIndex> + ExactSizeIterator + '_ {
229        self.topology.incoming_edges(node)
230    }
231}
232
233impl IndexGraphView for Graph {
234    fn node_bound(&self) -> usize {
235        self.topology.node_bound()
236    }
237
238    fn edge_bound(&self) -> usize {
239        self.topology.edge_bound()
240    }
241
242    fn node_slot(node: Self::Node) -> usize {
243        node.index()
244    }
245
246    fn edge_slot(edge: Self::Edge) -> usize {
247        edge.index()
248    }
249}
250
251#[derive(Deserialize)]
252struct GraphWire {
253    nodes: Vec<Node>,
254    edges: Vec<Edge>,
255}
256
257impl<'de> Deserialize<'de> for Graph {
258    fn deserialize<D>(deserializer: D) -> std::result::Result<Self, D::Error>
259    where
260        D: Deserializer<'de>,
261    {
262        let wire = GraphWire::deserialize(deserializer)?;
263        Self::try_from_parts(wire.nodes, wire.edges).map_err(D::Error::custom)
264    }
265}
weavatrix_graph/graph/core.rs

weavatrix_graph/graph/
core.rs
