1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
/*
* SPDX-License-Identifier: MIT
* Copyright (c) 2023 - 2026. The DeepCausality Authors and Contributors. All Rights Reserved.
*/
use crate::errors::{CausalGraphIndexError, CausalityGraphError};
use crate::traits::causable_graph::CausalGraph;
use ultragraph::{PathfindingGraphAlgorithms, TopologicalGraphAlgorithms};
pub trait CausableGraph<T>
where
T: Clone,
{
fn is_frozen(&self) -> bool;
/// Ensures the graph is in the immutable, performance-optimized `Static` state.
///
/// If the graph is already frozen, this operation is a no-op. Otherwise, it
/// converts the graph from a `Dynamic` state in-place. This is an O(V + E)
/// operation if a state change occurs.
fn freeze(&mut self);
/// Ensures the graph is in the mutable, `Dynamic` state.
///
/// If the graph is already dynamic, this operation is a no-op. Otherwise, it
/// converts the graph from a `Static` state in-place. This is an O(V + E)
/// operation if a state change occurs and requires node and edge data to be `Clone`.
fn unfreeze(&mut self);
/// Freezes the graph for reasoning **only if it is acyclic** (a directed acyclic graph).
///
/// This is the opt-in, DAG-enforcing counterpart to [`freeze`](Self::freeze). Where
/// `freeze` transitions the graph to its static reasoning form *unconditionally* and
/// therefore accepts cyclic structures, `freeze_dag` additionally verifies that the
/// graph contains no directed cycle, providing a structural guarantee for callers that
/// require one.
///
/// Cycle detection requires the static representation, so this method freezes first and
/// then checks. On success the graph is left frozen and ready for reasoning; on failure
/// it is rolled back to the dynamic state, so a graph is never left presented as a
/// frozen, cyclic graph.
///
/// # Returns
///
/// * `Ok(())` if the graph is acyclic. The graph is left frozen.
/// * `Err(CausalityGraphError)` if the graph contains a directed cycle. The graph is left unfrozen.
fn freeze_dag(&mut self) -> Result<(), CausalityGraphError> {
// `has_cycle` is only available on the static (frozen) representation, so freeze first.
self.freeze();
// After freezing, the static cycle check (Kahn's algorithm) is total: it returns
// `Ok(false)` for a DAG and `Ok(true)` for a cycle, and cannot report "not frozen".
// The `unwrap_or(true)` default for the (here unreachable) error variant keeps the
// contract simple — `Ok` always means "frozen DAG" — by never certifying a graph we
// could not verify.
if self.get_graph().has_cycle().unwrap_or(true) {
// Roll back so the graph is not left in a frozen, cyclic state.
self.unfreeze();
return Err(CausalityGraphError(
"Graph contains a directed cycle and cannot be frozen as a DAG".to_string(),
));
}
Ok(())
}
/// Returns a reference to the underlying `CausalGraph`.
///
/// This method is primarily used to enable default implementations for
/// other traits like `CausableGraphExplaining` and `CausableGraphReasoning`,
/// allowing them to operate directly on the graph structure.
fn get_graph(&self) -> &CausalGraph<T>;
/// Adds a special "root" causaloid to the graph.
///
/// The root node serves as the starting point for causal reasoning and traversals.
/// There can typically only be one root node in the graph.
///
/// # Arguments
///
/// * `value` - The causaloid of type `T` to be added as the root.
///
/// # Returns
///
/// The `usize` index of the newly added root node.
fn add_root_causaloid(&mut self, value: T) -> Result<usize, CausalityGraphError>;
/// Checks if a root causaloid has been set in the graph.
///
/// # Returns
///
/// * `true` if a root node exists, `false` otherwise.
fn contains_root_causaloid(&self) -> bool;
/// Retrieves an immutable reference to the root causaloid, if it exists.
///
/// # Returns
///
/// * `Some(&T)` containing a reference to the root causaloid if it's present.
/// * `None` if no root node has been added to the graph.
fn get_root_causaloid(&self) -> Option<&T>;
/// Retrieves the index of the root causaloid, if it exists.
///
/// # Returns
///
/// * `Some(usize)` containing the index of the root node if it's present.
/// * `None` if no root node has been added to the graph.
fn get_root_index(&self) -> Option<usize>;
/// Gets the index of the last causaloid added to the graph.
///
/// This is useful for understanding the current size or for linking
/// to a newly added node.
///
/// # Returns
///
/// * `Ok(usize)` containing the index of the last node.
/// * `Err(CausalityGraphError)` if the graph is empty and has no nodes.
fn get_last_index(&self) -> Result<usize, CausalityGraphError>;
// Nodes
/// Adds a new causaloid (node) to the graph.
///
/// # Arguments
///
/// * `value` - The causaloid of type `T` to be added to the graph.
///
/// # Returns
///
/// The `usize` index of the newly added causaloid.
fn add_causaloid(&mut self, value: T) -> Result<usize, CausalityGraphError>;
/// Checks if a causaloid exists at a specific index in the graph.
///
/// # Arguments
///
/// * `index` - The `usize` index to check for the existence of a causaloid.
///
/// # Returns
///
/// * `true` if a causaloid is present at the given index.
/// * `false` if the index is out of bounds or no causaloid is at that index.
fn contains_causaloid(&self, index: usize) -> bool;
/// Retrieves an immutable reference to a causaloid at a given index.
///
/// # Arguments
///
/// * `index` - The `usize` index of the causaloid to retrieve.
///
/// # Returns
///
/// * `Some(&T)` containing a reference to the causaloid if it exists at the specified index.
/// * `None` if the index is out of bounds.
fn get_causaloid(&self, index: usize) -> Option<&T>;
/// Removes a causaloid from the graph at the specified index.
///
/// Note: Removing a causaloid will also remove all edges connected to it.
///
/// # Arguments
///
/// * `index` - The `usize` index of the causaloid to remove.
///
/// # Returns
///
/// * `Ok(())` if the causaloid was successfully removed.
/// * `Err(CausalGraphIndexError)` if the provided `index` is invalid or out of bounds.
fn remove_causaloid(&mut self, index: usize) -> Result<(), CausalGraphIndexError>;
// Edges
/// Adds a directed edge between two causaloids in the graph.
///
/// This creates a causal link from the causaloid at index `a` to the one at index `b`.
///
/// # Arguments
///
/// * `a` - The `usize` index of the source causaloid (the cause).
/// * `b` - The `usize` index of the target causaloid (the effect).
///
/// # Returns
///
/// * `Ok(())` if the edge was successfully added.
/// * `Err(CausalGraphIndexError)` if either `a` or `b` is an invalid index.
fn add_edge(&mut self, a: usize, b: usize) -> Result<(), CausalGraphIndexError>;
/// Adds a weighted directed edge between two causaloids.
///
/// The weight can represent the strength, probability, or intensity of the causal relationship.
///
/// # Arguments
///
/// * `a` - The `usize` index of the source causaloid.
/// * `b` - The `usize` index of the target causaloid.
/// * `weight` - The `u64` weight of the edge.
///
/// # Returns
///
/// * `Ok(())` if the weighted edge was successfully added.
/// * `Err(CausalGraphIndexError)` if either `a` or `b` is an invalid index.
fn add_edg_with_weight(
&mut self,
a: usize,
b: usize,
weight: u64,
) -> Result<(), CausalGraphIndexError>;
/// Checks if a directed edge exists from causaloid `a` to causaloid `b`.
///
/// # Arguments
///
/// * `a` - The `usize` index of the source causaloid.
/// * `b` - The `usize` index of the target causaloid.
///
/// # Returns
///
/// * `true` if a directed edge from `a` to `b` exists.
/// * `false` if no such edge exists or if either index is invalid.
fn contains_edge(&self, a: usize, b: usize) -> bool;
/// Removes a directed edge between two causaloids.
///
/// If multiple edges exist between `a` and `b`, this will remove one of them.
///
/// # Arguments
///
/// * `a` - The `usize` index of the source causaloid.
/// * `b` - The `usize` index of the target causaloid.
///
/// # Returns
///
/// * `Ok(())` if the edge was successfully removed.
/// * `Err(CausalGraphIndexError)` if the edge does not exist or if either index is invalid.
fn remove_edge(&mut self, a: usize, b: usize) -> Result<(), CausalGraphIndexError>;
/// Returns the total number of causaloids (nodes) in the graph.
///
/// # Returns
///
/// A `usize` representing the total count of nodes in the graph.
fn size(&self) -> usize;
/// Checks if the graph contains no causaloids.
///
/// # Returns
///
/// * `true` if the graph has no nodes.
/// * `false` if the graph has one or more nodes.
fn is_empty(&self) -> bool;
/// Removes all causaloids and edges from the graph.
///
/// After calling this method, the graph will be empty.
fn clear(&mut self);
/// Returns the total number of edges in the graph.
///
/// # Returns
///
/// A `usize` representing the total count of edges.
fn number_edges(&self) -> usize;
/// Returns the total number of causaloids (nodes) in the graph.
///
/// # Returns
///
/// A `usize` representing the total count of nodes.
fn number_nodes(&self) -> usize;
/// Default implementation for shortest path algorithm.
///
/// Finds the shortest path between two node indices in the graph.
///
/// start_index: The start node index
/// stop_index: The target node index
///
/// Returns:
/// - Ok(`Vec<usize>`): The node indices of the shortest path
/// - Err(CausalityGraphError): If no path exists
///
/// Checks if start and stop nodes are identical and early returns error.
/// Otherwise calls shortest_path() on the underlying CausalGraph.
///
fn get_shortest_path(
&self,
start_index: usize,
stop_index: usize,
) -> Result<Vec<usize>, CausalityGraphError> {
if start_index == stop_index {
return Err(CausalityGraphError(
"Start and Stop node identical: No shortest path possible".into(),
));
}
match self.get_graph().shortest_path(start_index, stop_index) {
Ok(path) => match path {
Some(path) => Ok(path),
None => Err(CausalityGraphError("No path found".to_string())),
},
Err(e) => Err(CausalityGraphError(format!("{e}"))),
}
}
}