weavatrix_graph/graph/
core.rs

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

weavatrix_graph/graph/
core.rs
