weavatrix_graph/payload/stable/
acyclic.rs

1use super::StablePayloadGraph;
2use crate::{
3    Direction, EdgeEndpoints, GraphError, GraphView, IndexGraphView, Result, StableEdgeKey,
4    StableNodeKey, has_cycle, reachable, reachable_filtered,
5};
6
7/// A stable mutable payload graph that rejects cycle-creating mutations.
8#[derive(Debug, Clone, Default)]
9pub struct AcyclicPayloadGraph<NodePayload, EdgePayload> {
10    graph: StablePayloadGraph<NodePayload, EdgePayload>,
11}
12
13impl<NodePayload, EdgePayload> AcyclicPayloadGraph<NodePayload, EdgePayload> {
14    #[must_use]
15    pub const fn new() -> Self {
16        Self {
17            graph: StablePayloadGraph::new(),
18        }
19    }
20
21    /// Wraps an existing graph after validating the DAG invariant.
22    ///
23    /// # Errors
24    ///
25    /// Returns an error if the input contains a directed cycle.
26    pub fn try_from_graph(graph: StablePayloadGraph<NodePayload, EdgePayload>) -> Result<Self> {
27        if has_cycle(&graph) {
28            Err(GraphError::CycleWouldBeCreated)
29        } else {
30            Ok(Self { graph })
31        }
32    }
33
34    /// Adds an arbitrary node payload.
35    ///
36    /// # Errors
37    ///
38    /// Returns an error when stable index capacity is exhausted.
39    pub fn add_node(&mut self, payload: NodePayload) -> Result<StableNodeKey> {
40        self.graph.add_node(payload)
41    }
42
43    /// Adds an edge only when the graph remains acyclic.
44    ///
45    /// # Errors
46    ///
47    /// Returns an error for stale endpoints, exhausted capacity, or a cycle.
48    pub fn add_edge(
49        &mut self,
50        source: StableNodeKey,
51        target: StableNodeKey,
52        payload: EdgePayload,
53    ) -> Result<StableEdgeKey> {
54        self.graph.require_node(source)?;
55        self.graph.require_node(target)?;
56        if source == target || reachable(&self.graph, target, source) {
57            return Err(GraphError::CycleWouldBeCreated);
58        }
59        self.graph.add_edge(source, target, payload)
60    }
61
62    /// Retargets an edge only when the graph remains acyclic.
63    ///
64    /// # Errors
65    ///
66    /// Returns an error for stale endpoints or a cycle.
67    pub fn set_edge_endpoints(
68        &mut self,
69        edge: StableEdgeKey,
70        source: StableNodeKey,
71        target: StableNodeKey,
72    ) -> Result<bool> {
73        self.graph.require_node(source)?;
74        self.graph.require_node(target)?;
75        if source == target
76            || reachable_filtered(
77                &self.graph,
78                target,
79                source,
80                Direction::Outgoing,
81                |candidate| candidate != edge,
82            )
83        {
84            return Err(GraphError::CycleWouldBeCreated);
85        }
86        self.graph.set_edge_endpoints(edge, source, target)
87    }
88
89    pub fn remove_node(&mut self, key: StableNodeKey) -> Option<NodePayload> {
90        self.graph.remove_node(key)
91    }
92
93    pub fn remove_edge(&mut self, key: StableEdgeKey) -> Option<EdgePayload> {
94        self.graph.remove_edge(key)
95    }
96
97    #[must_use]
98    pub fn node(&self, key: StableNodeKey) -> Option<&NodePayload> {
99        self.graph.node(key)
100    }
101
102    #[must_use]
103    pub fn node_mut(&mut self, key: StableNodeKey) -> Option<&mut NodePayload> {
104        self.graph.node_mut(key)
105    }
106
107    #[must_use]
108    pub fn edge(&self, key: StableEdgeKey) -> Option<&EdgePayload> {
109        self.graph.edge(key)
110    }
111
112    #[must_use]
113    pub fn edge_mut(&mut self, key: StableEdgeKey) -> Option<&mut EdgePayload> {
114        self.graph.edge_mut(key)
115    }
116
117    #[must_use]
118    pub const fn graph(&self) -> &StablePayloadGraph<NodePayload, EdgePayload> {
119        &self.graph
120    }
121
122    #[must_use]
123    pub fn into_inner(self) -> StablePayloadGraph<NodePayload, EdgePayload> {
124        self.graph
125    }
126}
127
128impl<NodePayload, EdgePayload> GraphView for AcyclicPayloadGraph<NodePayload, EdgePayload> {
129    type Node = StableNodeKey;
130    type Edge = StableEdgeKey;
131
132    fn node_count(&self) -> usize {
133        self.graph.node_count()
134    }
135
136    fn edge_count(&self) -> usize {
137        self.graph.edge_count()
138    }
139
140    fn contains_node(&self, node: Self::Node) -> bool {
141        self.graph.contains_node(node)
142    }
143
144    fn contains_edge(&self, edge: Self::Edge) -> bool {
145        self.graph.contains_edge(edge)
146    }
147
148    fn node_indices(&self) -> impl Iterator<Item = Self::Node> + '_ {
149        self.graph.node_indices()
150    }
151
152    fn edge_indices(&self) -> impl Iterator<Item = Self::Edge> + '_ {
153        self.graph.edge_indices()
154    }
155
156    fn edge_endpoints(&self, edge: Self::Edge) -> Option<EdgeEndpoints<Self::Node>> {
157        self.graph.edge_endpoints(edge)
158    }
159
160    fn outgoing_edges(&self, node: Self::Node) -> impl Iterator<Item = Self::Edge> + '_ {
161        self.graph.outgoing_edges(node)
162    }
163
164    fn incoming_edges(&self, node: Self::Node) -> impl Iterator<Item = Self::Edge> + '_ {
165        self.graph.incoming_edges(node)
166    }
167}
168
169impl<NodePayload, EdgePayload> IndexGraphView for AcyclicPayloadGraph<NodePayload, EdgePayload> {
170    fn node_bound(&self) -> usize {
171        self.graph.node_bound()
172    }
173
174    fn edge_bound(&self) -> usize {
175        self.graph.edge_bound()
176    }
177
178    fn node_slot(node: Self::Node) -> usize {
179        node.index()
180    }
181
182    fn edge_slot(edge: Self::Edge) -> usize {
183        edge.index()
184    }
185}
weavatrix_graph/payload/stable/acyclic.rs

weavatrix_graph/payload/stable/
acyclic.rs
