# Software Requirements Specification (SRS) for next_graph
* **Version:** 5.0
* **Date:** 2025-06-30
* **Status:** Finalized for Implementation
{{TOC}}
## 1 Introduction
### 1.1 Purpose
This document specifies the complete requirements for `next_graph`, a high-performance, `std`-only graph data structure library. It is intended to serve as the foundational graph representation for the DeepCausality project, providing a robust, memory-efficient, and evolution-ready replacement for existing dependencies.
### 1.2 Project Scope
`next_graph` will provide a set of Rust structs and traits for creating, dynamically evolving, and analyzing hypergraphs. The library will be a self-contained crate with zero external dependencies by default. Its scope covers the full lifecycle of graph data, from initial creation and staged evolution to high-performance, immutable analysis. This document also includes a detailed **Functional Parity Analysis (Appendix A)** to serve as a foundation for migrating from the previous `UltraGraph` trait system.
### 1.3 Problem Statement
The DeepCausality project has evolved to model **dynamic, emergent causality**, where graphs are not static but co-evolve in response to new information. This paradigm invalidates any graph architecture that requires fixed sizing or incurs prohibitive costs for structural changes. A new graph library is required that is memory-efficient (`O(V+E)`), performant, and architected to support a "grow as you go" lifecycle.
## 2 Description
### 2.1 Product Philosophy
* **Performance and Memory Efficiency:** Leveraging appropriate data structures for each state.
* **Reliability and Stability:** A strict **zero external dependency** policy by default.
* **Safety:** A panic-free public API using Rust's type system for robust error handling.
* **Adaptability:** Direct architectural support for the dynamic evolution of graph structures.
### 2.2 Architectural Design: The Evolutionary Cycle
The library is built around a two-state model to manage the trade-off between mutability and performance:
1. **`DynamicGraph<N, W>` (The "Evolve" State):** A representation optimized for easy and efficient mutations (`add_node`, `add_edge`).
2. **`CsmGraph<N, W>` (The "Analyze" State):** A static, immutable representation optimized for maximum traversal performance and safe parallel processing.
3. **State Transitions:** The library provides two key lifecycle operations: `.freeze()` and `.unfreeze()`, enabling controlled transitions between the two states.
## 3 Functional Requirements: Trait-Based API Specification
The library's API shall be defined by the following set of traits.
### 3.1 Trait: `GraphView` (The Inspector)
This trait defines the universal, read-only API implemented by both `DynamicGraph` and `CsmGraph`.
```rust
pub trait GraphView<N, W> {
// State Inspection
fn is_frozen(&self) -> bool;
// Node Inspection
fn contains_node(&self, index: usize) -> bool;
fn get_node(&self, index: usize) -> Option<&N>;
fn number_nodes(&self) -> usize;
// Edge Inspection
fn contains_edge(&self, a: usize, b: usize) -> bool;
fn number_edges(&self) -> usize;
// Root Node Inspection
fn contains_root_node(&self) -> bool;
fn get_root_node(&self) -> Option<&N>;
fn get_root_index(&self) -> Option<usize>;
}
```
### 3.2 Trait: `GraphMut` (The Builder)
This trait defines all mutable operations and shall only be implemented by `DynamicGraph`.
```rust
pub trait GraphMut<N, W>: GraphView<N, W> {
// Node Mutation
fn add_node(&mut self, payload: N) -> usize;
fn update_node(&mut self, index: usize, payload: N) -> Result<(), UltraGraphError>;
// Edge Mutation
fn add_edge(&mut self, a: usize, b: usize, weight: W) -> Result<(), UltraGraphError>;
fn remove_edge(&mut self, a: usize, b: usize) -> Result<(), UltraGraphError>;
// Root Node Mutation
fn add_root_node(&mut self, payload: N) -> usize;
// Graph-wide Mutation
fn clear(&mut self);
}
```
### 3.3 Trait: `GraphAlgorithms` (The Analyst)
This trait defines high-performance analytics algorithms and shall only be implemented by `CsmGraph`.
```rust
/// Defines a suite of high-performance, read-only analytical algorithms.
///
/// This trait is intended for implementation on static, optimized graph structures
/// like `next_graph::CsmGraph` to validate their structure and properties.
pub trait GraphAlgorithms<N, W>: GraphView<N, W> {
// --- Traversal ---
/// Returns a non-allocating iterator over the direct successors (outgoing edges) of node `a`.
///
/// This method provides a direct, high-performance view into the graph's internal
/// structure without any intermediate memory allocations.
///
/// # Returns
/// A `Result` containing an iterator that yields the `usize` indices of the neighbor nodes.
fn outbound_edges(&self, a: usize) -> Result<impl Iterator<Item = usize>, UltraGraphError>;
/// Returns a non-allocating iterator over the direct predecessors (incoming edges) of node `a`.
fn inbound_edges(&self, a: usize) -> Result<impl Iterator<Item = usize>, UltraGraphError>;
// --- Structural Validation Algorithms ---
/// Finds a single cycle in the graph and returns the path of nodes that form it.
///
/// This is the most powerful cycle detection method, as it not only confirms the
/// presence of a cycle but also identifies the specific nodes involved. This is
/// invaluable for debugging dynamically generated graphs.
///
/// # Returns
/// `Some(Vec<usize>)` containing the sequence of node indices that form a cycle
/// (e.g., `[0, 1, 0]`). Returns `None` if the graph is a DAG.
fn find_cycle(&self) -> Option<Vec<usize>>;
/// Checks if the graph contains any directed cycles.
///
/// This method should be implemented as a simple call to `self.find_cycle().is_some()`.
fn has_cycle(&self) -> bool;
/// Computes a topological sort of the graph, if it is a Directed Acyclic Graph (DAG).
/// Returns `None` if the graph contains a cycle.
fn topological_sort(&self) -> Option<Vec<usize>>;
// --- Pathfinding and Reachability Algorithms ---
/// Checks if a path of any length exists from a start to a stop index.
fn is_reachable(&self, start_index: usize, stop_index: usize) -> bool;
/// Returns the length of the shortest path (in number of nodes) from a start to a stop index.
fn shortest_path_len(&self, start_index: usize, stop_index: usize) -> Option<usize>;
/// Finds the complete shortest path from a start to a stop index.
fn shortest_path(&self, start_index: usize, stop_index: usize) -> Option<Vec<usize>>;
}
```
A reader familiar with the original UltraGraph trait system will note a significant and deliberate change in the return types for the outbound_edges and inbound_edges methods. The original API returned Result<IntoIter<usize>, ...>, while the new API returns Result<impl Iterator<Item = usize>, ...>.
On the surface, this may seem like a minor technical detail. In reality, this change is fundamental to the performance philosophy of next_graph and represents one of the most important low-level improvements in this redesign.
The decision to redesign the trait system already requires a significant, one-time migration effort. Retaining the old signature for slightly easier migration would be a false economy, permanently embedding a performance bottleneck into the new system. Therefore, we have chosen to re-design UltrGraph for optimal performance.
The Technical Difference: "Photocopying" vs. "A Window"
To grok the difference, consider this analogy:
A) The Old Way (Result<IntoIter<usize>, ...>): The "Photocopy" Method
This signature forces the graph to perform a memory allocation. To return this type, the implementation must first find all the neighbor indices, create a new temporary Vec or VecDeque on the heap, copy all the indices into this new container, and only then return an iterator over that new copy. For an algorithm that calls outbound_edges thousands of times in a tight loop (like a Breadth-First Search), this results in thousands of unnecessary heap allocations and memory copies. This "photocopying" of data is expensive, increases memory pressure, and is hostile to the CPU cache.
B) The New Way (Result<impl Iterator<Item = usize>, ...>): The "Window" Method
This signature enables a zero-cost abstraction. The CsmGraph, with its internal CSR structure, stores all neighbors for a given node in a contiguous block of memory. This signature allows the method to return a special iterator type (a slice iterator) that is simply a "window" or a direct, read-only view into that existing block of memory. There are no new memory allocations and no data copies. The caller gets a direct, temporary handle to the original data.
By choosing the "Window" method, we gain three critical advantages:
* Massive Speed Increase: We eliminate thousands of costly memory allocations in core graph algorithms.
* Reduced Memory Pressure: The program's memory usage is lower and more stable, reducing the workload on the system's memory manager.
* Enhanced Cache Locality: Iterating directly over the original, contiguous memory slice is cache-friendly, leading to significant real-world speedups that go beyond what a simple complexity analysis can show.
In short, this change ensures that traversal—the most fundamental operation in any graph library—is as fast as physically possible. It is a deliberate, strategic decision to prioritize long-term performance and architectural purity.
### 3.4 Trait Module: `evolution` (The Lifecycle)
This module defines the traits for the core evolutionary lifecycle of the graph.
```rust
pub mod evolution {
use crate::{DynamicGraph, CsmGraph};
pub trait Freezable<N, W> {
fn freeze(self) -> CsmGraph<N, W>;
}
pub trait Unfreezable<N, W> {
fn unfreeze(self) -> DynamicGraph<N, W>;
}
}
```
## 4 Implementation Details
This section provides specific implementation guidance for the core components of the `next_graph` library. It is designed to give the implementing engineer a clear blueprint based on the architectural decisions and performance optimizations discussed.
### 4.1 `CsmGraph` Core Data Structure
The `CsmGraph<N, W>` struct shall be a direct programmatic implementation of the **bipartite graph representation** model, inspired by the NWHypergraph paper. It will use two mutually indexed Compressed Sparse Row (CSR) structures to enable efficient bidirectional traversal.
The struct shall be defined as follows:
```rust
pub struct CsmGraph<N, W> {
// Node payloads, indexed directly by `usize`.
nodes: Vec<N>,
// CSR structure for forward traversal (successors).
forward_edges: (Vec<usize>, Vec<(usize, W)>),
// CSR structure for backward traversal (predecessors).
backward_edges: (Vec<usize>, Vec<(usize, W)>),
// Index of the designated root node.
root_index: Option<usize>,
}
```
* **CSR Structure:** Both `forward_edges` and `backward_edges` are tuples `(offsets, adjacencies)` where:
* `offsets`: A `Vec<usize>` of length `V + 1`. The entry `offsets[i]` stores the starting index in the `adjacencies` vector for the edges related to node `i`.
* `adjacencies`: A `Vec<(usize, W)>` containing a contiguous list of all edges. The edges for node `i` are located in the slice `adjacencies[offsets[i]..offsets[i+1]]`.
* **`forward_edges` (for `outbound_edges`):** This structure maps a source node `i` to its list of successors (targets).
* **`backward_edges` (for `inbound_edges`):** An identical CSR structure, but representing the **transposed graph**. Here, it maps a target node `i` to its list of predecessors (sources).
### 4.2 `DynamicGraph` Core Data Structure
The `DynamicGraph<N, W>` struct shall use a classic **Adjacency List** representation, optimized for frequent and cheap mutations.
The struct shall be defined as follows:
```rust
pub struct DynamicGraph<N, W> {
// Node payloads, indexed directly by `usize`.
// The use of `Option` allows for efficient O(1) node removal ("tombstoning")
// without invalidating other node indices.
nodes: Vec<Option<N>>,
// Adjacency list: A vector where each index corresponds to a source node,
// and the value is a list of its outgoing edges.
edges: Vec<Vec<(usize, W)>>,
// Index of the designated root node.
root_index: Option<usize>,
}
```
* **Mutation Performance:** This structure ensures that `add_node` and `add_edge` are amortized `O(1)` operations.
* **Node Removal (`remove_node`):** This operation shall be implemented via "tombstoning." It will replace the element at `nodes[index]` with `None`, an `O(1)` operation. All edge lists connected to the removed node must also be cleared. The `.freeze()` operation will be responsible for compacting the `nodes` vector and re-indexing edges.
* **Performance Trade-off:** Traversal on this structure is less cache-friendly than on `CsmGraph`, as each inner `Vec` for edges is a separate heap allocation. This is an acceptable trade-off for a structure optimized for building and evolution.
### 4.3 Root Node Handling
* **Storage:** The root node shall be tracked by a simple `root_index: Option<usize>` field present in both `CsmGraph` and `DynamicGraph`.
* **Mutation:** The `GraphMut::add_root_node` method will perform an `add_node` operation and then set the `root_index` field to the newly returned `usize` ID.
* **Transitions:** The value of `root_index` must be correctly preserved during `freeze` and `unfreeze` operations.
### 4.4 Error Handling System
The library shall implement a robust and high-performance error handling system with zero external dependencies. The design prioritizes performance by ensuring that error creation and propagation have minimal to zero overhead.
#### 4.4.1 Requirement: Lightweight Error Type
To eliminate heap allocations, the library's error type shall be a C-like enum that implements the Copy trait. To maximize its utility for debugging and logging, relevant variants shall include the usize indices that caused the error. This is a zero-cost abstraction in practice, as usize is a Copy type.
The error type shall be defined as follows:
```rust
use std::fmt;
/// A lightweight, copyable, stack-allocated error type for the next_graph library
/// that provides context about the failure.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum GraphError {
/// An operation was attempted on a node index that does not exist or has been removed.
NodeNotFound(usize),
/// An edge could not be created, typically between two nodes.
EdgeCreationError { source: usize, target: usize },
/// An operation was attempted on an edge that does not exist.
EdgeNotFoundError { source: usize, target: usize },
/// The operation could not be completed because the graph contains a cycle.
GraphContainsCycle,
}
impl fmt::Display for GraphError {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
match self {
Self::NodeNotFound(index) => {
write!(f, "Node with index {} not found; it may be out of bounds or have been removed.", index)
}
Self::EdgeCreationError { source, target } => {
write!(f, "Edge from {} to {} could not be created; a node may not exist or the edge already exists.", source, target)
}
Self::EdgeNotFoundError { source, target } => {
write!(f, "Edge from {} to {} not found.", source, target)
}
Self::GraphContainsCycle => {
write!(f, "Operation failed because the graph contains a cycle.")
}
}
}
}
// This makes GraphError a fully-fledged error type compatible with the Rust ecosystem.
impl std::error::Error for GraphError {}
```
*(Note: Renamed `NodeOutOfBounds` to `NodeNotFound` to cover the "tombstone" case.)*
#### 4.4.2 Requirement: Panic-Free Public API
All public methods in the library's traits that can fail due to invalid input, state, or other logical errors must not panic. Instead, they must return `std::result::Result<T, GraphError>` or `std::option::Option<T>`.
### 4.5 Bulk Data Ingestion API: Optimizing for Bulk Data
#### 4.5.1 Rationale and Performance Bottleneck
The standard `GraphMut` trait provides an iterative API (`add_node`, `add_edge`) that is ideal for building a graph dynamically or when the graph structure is not known in advance. However, each call to `add_edge` must perform validation checks (e.g., ensuring node indices are within bounds).
In many data-intensive applications, the entire graph dataset (all nodes and all edges) is already available in memory, often as the result of a database query or file parse. In these scenarios, iterating and calling `add_edge` millions of times introduces significant, redundant overhead from the repeated validation checks.
To address this, the library must provide a high-performance "fast path" constructor that allows for the efficient bulk ingestion of pre-validated data.
#### 4.5.2 Requirement: The `from_parts` Constructor
The `DynamicGraph<N, W>` struct shall provide an optimized constructor, `from_parts`, that builds the graph directly from its constituent collections. This method is designed to be the most performant way to construct a graph when the data is already prepared.
The constructor shall be defined as follows:
```rust
// In `impl<N, W> DynamicGraph<N, W>`
/// Creates a `DynamicGraph` directly from its constituent parts.
///
/// This is the most performant way to construct a graph from an existing, validated
/// dataset, as it bypasses the per-call overhead of methods like `add_edge`.
///
/// # Preconditions
/// The caller is responsible for ensuring the integrity of the data. Specifically:
/// - The length of the `edges` vector must be exactly equal to the length of the `nodes` vector.
/// - Every `usize` target index within the `edges` lists must be a valid index into the `nodes` vector
/// (i.e., less than `nodes.len()`).
///
/// # Panics
/// This method will panic in debug builds if `nodes.len() != edges.len()`. It may
/// cause out-of-bounds panics later if the edge index precondition is violated by the caller.
pub fn from_parts(nodes: Vec<Option<N>>, edges: Vec<Vec<(usize, W)>>) -> Self {
// A non-negotiable sanity check. This prevents gross structural mismatches.
assert_eq!(
nodes.len(),
edges.len(),
"The number of node payloads must equal the number of adjacency lists."
);
Self {
nodes,
edges,
root_index: None, // Root can be set via the GraphMut trait after construction.
}
}
```
#### 4.5.3 API Contract and Responsibilities
* **Zero-Overhead by Default:** The `from_parts` constructor shall perform the absolute minimum validation necessary (`assert_eq!`) and will primarily focus on moving the provided `Vec`s directly into the `DynamicGraph` struct fields. This ensures maximum performance.
* **Caller Responsibility:** It is the responsibility of the calling code to ensure that the provided `edges` data is valid and that all indices point to valid nodes. This is a deliberate trade-off that places the cost of validation on the user in exchange for a significant performance gain.
* **Documentation:** The method's documentation must clearly state the preconditions and the fact that it will panic if they are violated, making the API contract unambiguous.
#### 4.5.4 Impact and "All-In" Philosophy
This "fast path" constructor is a core component of the "all-in" performance philosophy. It acknowledges that users often have different needs: some require the safety of an iterative builder, while others need the raw speed of bulk loading. By providing both, `next_graph` allows users to choose the right tool for their specific performance and safety trade-offs, ensuring that the library is never the bottleneck in a data processing pipeline.
#### **4.6 Optimized `freeze` Transition Algorithm
##### 4.6.1 Rationale and Performance Bottleneck
The `freeze` operation is responsible for converting the mutation-friendly `DynamicGraph` (adjacency list) into the analytics-optimized `CsmGraph` (Compressed Sparse Row). A naive implementation of this process would be multi-pass and involve significant intermediate memory allocations:
1. **Pass 1:** Build the `forward_edges` CSR structure.
2. **Pass 2:** Build a temporary, intermediate `Vec<Vec<(usize, W)>>` for the transposed graph (for `backward_edges`). This is an `O(V + E)` allocation.
3. **Pass 3:** Build the `backward_edges` CSR structure from the temporary transposed graph.
The creation and subsequent destruction of the temporary transposed graph in Pass 2 introduces unnecessary memory pressure and processing overhead, especially for large graphs. To adhere to the "all-in" performance philosophy, this intermediate allocation must be eliminated.
##### 4.6.2 Requirement: Single-Pass `freeze` Algorithm
The `evolution::Freezable::freeze` method on `DynamicGraph` shall be implemented using a highly optimized, two-pass algorithm that constructs both the `forward_edges` and `backward_edges` CSR structures simultaneously, without creating any large intermediate collections.
The algorithm shall proceed as follows:
Algorithm Sketch for Optimal `.freeze()`:
1. **First Pass (Counting and Compacting):**
* Initialize `out_degrees: Vec<usize>` and `in_degrees: Vec<usize>`, both of size `V`, to all zeros.
* Create a new, compacted `nodes: Vec<N>` and a `remapping_table: Vec<usize>` to handle "tombstoned" (removed) nodes from the `DynamicGraph`.
* Iterate through the `DynamicGraph.nodes`. If a node `at old_index` is `Some(payload)`, move the payload to the new `nodes` vector and record the mapping: `remapping_table[old_index] = new_index`.
* Iterate through the `DynamicGraph.edges`. For each edge `(old_source, old_target)`:
* Use the `remapping_table` to find the `new_source` and `new_target` indices.
* Increment `out_degrees[new_source]` and `in_degrees[new_target]`.
2. Offset Calculation (Cumulative Sum):
* Calculate the final `offsets` vectors for both `forward_edges` and `backward_edges` by performing a standard prefix sum (cumulative sum) on the `out_degrees` and `in_degrees` vectors, respectively. This determines the exact starting position for each node's adjacency list in the final contiguous arrays.
3. Second Pass (Placement):
* Create `fwd_adj: Vec<(usize, W)>` and `back_adj: Vec<(usize, W)>`, pre-sized to their final capacity (`total_edges`).
* Create temporary copies of the `forward_offsets` and `backward_offsets` vectors to serve as write-head counters.
* Iterate through the `DynamicGraph.edges` a final time. For each edge `(old_source, old_target)` with weight `w`:
* Remap to `new_source` and `new_target`.
* **Forward Placement:** Use the `new_source` counter to find the correct insertion index in `fwd_adj`. Place `(new_target, w)` at that index. Increment the `new_source` counter.
* **Backward Placement:** Use the `new_target` counter to find the correct insertion index in `back_adj`. Place `(new_source, w)` at that index. Increment the `new_target` counter.
##### 4.6.3 Impact and Performance Guarantees
This algorithm provides several critical benefits:
* **Reduced Memory Footprint:** It avoids the `O(V + E)` intermediate allocation for the transposed graph, cutting the peak memory usage of the `freeze` operation significantly.
* **Improved Cache Efficiency:** By working with flat `Vec`s and predictable access patterns, it is more CPU cache-friendly than building and traversing nested `Vec<Vec<...>>` structures.
* **Guaranteed Complexity:** The entire operation remains strictly `O(V + E)` in time and space, with a much lower constant factor for memory usage.
This implementation ensures that the core transition logic of the library is as efficient as possible, directly supporting the goal of a "brief" and predictable "stop the world" phase, even for very large graphs.
#### 4.7 Adaptive Edge Containment Check (`contains_edge`)
##### 4.7.1 Requirement: Adaptive Algorithm for `contains_edge`
The `GraphView::contains_edge(a, b)` method, when implemented on `CsmGraph`, shall use a hybrid, adaptive algorithm to provide optimal performance across all possible node degrees. The method will dynamically choose between a linear scan and a binary search based on the degree of the source node `a`.
##### 4.7.2 Prerequisite: Sorted Adjacency Lists
To enable the use of binary search, this design mandates a new requirement for the `.freeze()` operation:
* During the `freeze` transition, after populating the adjacency list for each node, the implementation **must** sort that slice of the `adjacencies` vector. The sorting key shall be the target node index.
* Example: `slice.sort_unstable_by_key(|(target_node_index, _weight)| *target_node_index)`.
This one-time `O(E log k)` cost (where `k` is the average degree) during the "stop the world" phase enables consistently optimal `O(log degree)` lookups for the entire lifecycle of the frozen `CsmGraph`.
##### 4.7.3 Implementation Details of the Adaptive Method
The implementation shall follow this logic:
1. **Define a Threshold:** A compile-time constant shall be defined to represent the tipping point where binary search becomes more performant than a linear scan. A conservative and well-regarded starting point is 64.
```rust
const BINARY_SEARCH_THRESHOLD: usize = 64;
```
2. **Implement the Hybrid Logic:**
```rust
// In the implementation of `CsmGraph::contains_edge(a, b)`
// 1. Get the degree of node `a`. This is a cheap O(1) operation.
let degree = self.forward_edges.0[a + 1] - self.forward_edges.0[a];
// 2. Get the slice of neighbors.
let start = self.forward_edges.0[a];
let end = self.forward_edges.0[a + 1];
let neighbors_slice = &self.forward_edges.1[start..end];
// 3. Choose the algorithm adaptively.
if degree < BINARY_SEARCH_THRESHOLD {
// For small lists, a linear scan is faster due to cache locality.
neighbors_slice.iter().any(|(target, _)| *target == b)
} else {
// For larger lists, binary search is asymptotically faster.
// This relies on the slice being pre-sorted during `.freeze()`.
neighbors_slice.binary_search_by_key(&b, |(target, _)| *target).is_ok()
}
```
##### 4.7.4 Performance Rationale and "All-In" Philosophy
This adaptive strategy is the definitive "all-in" solution for `contains_edge`. It does not make assumptions about the data's shape. Instead, it inspects the shape at runtime (with a near-zero cost `O(1)` check) and selects the provably optimal algorithm for that specific situation.
* It provides the raw speed and cache-friendliness of a **linear scan** for the overwhelmingly common case of low-degree nodes.
* It provides the robust, logarithmic complexity of a **binary search** for the rare but possible case of high-degree hub nodes, preventing unexpected performance degradation.
This ensures that the `contains_edge` method is performant, scalable, and resilient, regardless of how the graph evolves in the future. It is a one-time investment in complexity that pays a permanent dividend in performance and robustness.
#### 4.8 DFS-Based Cycle Detection and Topological Sort
##### 4.8.1 Rationale: Providing Actionable Cycle Information
A simple boolean check for the existence of a cycle (`has_cycle`) is insufficient for a system that debugs dynamically generated graphs. To provide maximum utility, the library must be able to identify the specific nodes that form a cycle. A standard Depth-First Search (DFS) traversal with node coloring is the most direct and efficient algorithm for finding the exact path of a cycle (a "back edge" in the traversal tree).
Furthermore, the same DFS traversal can be used to produce a topological sort, unifying the implementation of all structural validation methods. This approach is superior to using Kahn's algorithm for `topological_sort` and a separate algorithm for cycle detection.
##### 4.8.2 Requirement: Unifying `find_cycle`, `has_cycle`, and `topological_sort`
The `GraphAlgorithms` methods `find_cycle`, `has_cycle`, and `topological_sort` shall all be implemented based on a single, shared DFS traversal helper function to ensure consistency and efficiency.
##### 4.8.3 Implementation Details of the DFS Traversal
The internal DFS helper function will be the core of the implementation.
**Data Structures:**
* **`colors: Vec<Color>`:** A vector of size `V` to track the state of each node. The `Color` enum shall be defined as:\
```rust
#[derive(Clone, Copy, PartialEq)]
enum Color { White, Gray, Black }
```
* **`White`**: The node has not been visited yet.
* **`Gray`**: The node is currently in the recursion stack (i.e., we are visiting it and its descendants).
* **`Black`**: We have finished visiting the node and all of its descendants.
* **`predecessors: Vec<Option<usize>>`:** A vector of size `V` used during the DFS to trace back the path of a found cycle.
* **`sorted_list: Vec<usize>`:** A vector that will store the topologically sorted nodes in reverse order of their finishing times.
**Algorithm Sketch for the internal `dfs_visit` function:**
```rust
fn dfs_visit(
u: usize,
colors: &mut [Color],
predecessors: &mut [Option<usize>],
sorted_list: &mut Vec<usize>
) -> Option<Vec<usize>> // Returns Some(cycle_path) if a cycle is found
{
colors[u] = Color::Gray;
for v in self.outbound_edges(u).unwrap() {
predecessors[v] = Some(u);
if colors[v] == Color::Gray {
// CYCLE DETECTED! We've found a back edge to a 'gray' node.
// Reconstruct the path from `predecessors` starting from `u` back to `v`.
// Example path: [v, ..., predecessor[u], u, v]
// Return Some(cycle_path).
return Some(reconstruct_cycle(v, u, predecessors));
}
if colors[v] == Color.White {
if let Some(cycle) = self.dfs_visit(v, colors, predecessors, sorted_list) {
// Propagate the found cycle up the call stack.
return Some(cycle);
}
}
}
colors[u] = Color::Black;
sorted_list.push(u); // Add `u` to the list after all its children are processed.
None // No cycle found in this branch.
}
```
##### 4.8.4 Implementing the Public Trait Methods
* **`find_cycle(&self) -> Option<Vec<usize>>`**
1. Initialize `colors` to `White`, `predecessors` to `None`, and `sorted_list` as empty.
2. Iterate through all nodes from `0` to `V-1`.
3. If `colors[i]` is `White`, call the internal `dfs_visit(i, ...)` function.
4. If `dfs_visit` ever returns `Some(cycle_path)`, immediately return that result.
5. If the loop completes without finding a cycle, return `None`.
* **`has_cycle(&self) -> bool`**
* This method shall be implemented as a simple call to `self.find_cycle().is_some()`. This provides the boolean check with zero code duplication.
* **`topological_sort(&self) -> Option<Vec<usize>>`**
1. Initialize `colors` to `White` and `sorted_list` as empty. (The `predecessors` vector is not strictly needed if we only want the sort).
2. Iterate through all nodes `i`. If `colors[i]` is `White`, call a DFS visit function. **Crucially, this DFS must also detect cycles.**
3. If at any point a cycle is detected, the function must immediately abort and return `None`.
4. If the entire traversal completes without finding a cycle, the `sorted_list` will contain all nodes in reverse topological order.
5. Reverse `sorted_list` and return `Some(sorted_list)`.
This unified DFS-based approach ensures that all three structural validation methods are consistent, efficient, and provide the richest possible diagnostic information for analyzing dynamically generated causal graphs.
## 5 Core Algorithm Implementation Drafts
### 5.1 Shortest Path (`shortest_path_len`, `shortest_path`)
* **Algorithm:** Breadth-First Search (BFS).
* **Data Structures (`std::collections`):**
* `queue: VecDeque<usize>` to store nodes to visit.
* `visited: Vec<bool>` of size `V` to avoid redundant processing.
* `predecessor: Vec<Option<usize>>` of size `V` to reconstruct the path for `shortest_path`.
* **Logic:**
1. Initialize queue, `visited`, and `predecessor` arrays.
2. Push `start_index` to queue and mark as visited.
3. While queue is not empty, dequeue `current_node`.
4. If `current_node` is `stop_index`, the path is found. For `shortest_path`, trace back using the `predecessor` array. For `shortest_path_len`, return the current search depth.
5. For each neighbor of `current_node` (via `outbound_edges`): if not visited, mark as visited, set its predecessor to `current_node`, and enqueue it.
### 5.2 Topological Sort & Cycle Detection (`topological_sort`, `has_cycle`)
* **Algorithm:** Kahn's Algorithm.
* **Data Structures:**
* `queue: VecDeque<usize>` for nodes with an in-degree of zero.
* `in_degrees: Vec<usize>` of size `V`.
* `sorted_list: Vec<usize>` to store the result.
* **Logic:**
1. **Initialization:** Populate `in_degrees` for every node by iterating through the graph and using `inbound_edges` to find the count of predecessors for each node.
2. **Queue Setup:** Add all nodes with an initial in-degree of 0 to the `queue`.
3. **Processing Loop:** While `queue` is not empty:
a. Dequeue `node` and push it to `sorted_list`.
b. For each neighbor of `node` (via `outbound_edges`): decrement its count in `in_degrees`. If a neighbor's in-degree becomes 0, add it to the `queue`.
4. **Result:**
* If `sorted_list.len() == self.number_nodes()`, the sort was successful. Return `Some(sorted_list)`.
* If `sorted_list.len() < self.number_nodes()`, a cycle was detected. Return `None`.
5. The `has_cycle` method shall be implemented as `self.topological_sort().is_none()`.
## 6 Non-Functional Requirements
* **NFR-P-1 (Performance):** Time complexities must adhere to the specified bounds.
* **NFR-M-1 (Memory):** Memory footprint shall be `O(V + E)`.
* **NFR-R-1 (Reliability):** `CsmGraph` must be `Sync + Send`.
* **NFR-C-1 (Compilation):** The default crate shall have zero external dependencies.
## 7 Optional Features
### 7.1 Feature: `"parallel"`
* **FR-F-1:** The crate shall define a feature named `"parallel"`.
* **FR-F-2:** Enabling this feature shall activate an optional dependency on the `rayon` crate.
* **FR-F-3:** An extension trait, `ParallelGraphAlgorithms`, shall be provided to add parallel versions of analytical methods to `CsmGraph`.
## 8 Implementation Risk Assessment
Risk ID Description of Risk Impact Likelihood Mitigation Strategy
* R-1 Off-by-One Errors in CSR Logic High Medium Implement extensive unit tests with known small graphs where the expected offsets and edges vectors can be calculated by hand. Review all indexing logic ([i], [i+1]) carefully.
* R-2 Incorrect Transposed Graph Construction High Medium The inbound_edges and some algorithms rely on the correctness of the backward CSR graph. Add specific tests that add an edge (u, v) and then confirm v is a predecessor of u via this method.
* R-3 Performance of freeze/unfreeze is Sub-Optimal Medium Low The proposed O(V + E) algorithms are standard. Benchmark the transition operations on large graphs to verify they meet performance expectations. Avoid algorithms with non-linear complexity.
* R-4 Inefficient Memory Use During Transitions Medium High The transition process will temporarily require ~2x the memory of a single graph. This is a known architectural trade-off. This behavior must be clearly documented for the user.
## 9 Closing Thoughts
The transition from a SRS blueprint to a living, breathing library is where the real challenges lie. Here are four final pieces of advice for the implementation phase:
The Index is Sacred. The entire performance model of CsmGraph relies on the integrity of its usize indices. The most likely source of bugs will be in the freeze operation, specifically in the logic that handles the re-mapping of indices after compacting "tombstoned" nodes. Test this transition logic with ruthless intensity. Use test cases with no removals, removals from the middle, removals from the end, and multiple removals. An off-by-one error here can cause silent data corruption that is incredibly difficult to debug later.
Document the "Why," Not Just the "What." The SRS is excellent, but the final code needs developer-facing documentation (///). When you implement the adaptive contains_edge method, for example, add a comment explaining why the BINARY_SEARCH_THRESHOLD exists. When you implement the zero-cost error enum, explain why it's better than a String-based error. This internal documentation will be invaluable for long-term maintenance and for anyone who joins the project years from now.
Benchmark From Day One. Performance is a primary goal. Don't wait until the end to see if the library is fast. Use the criterion crate early in the development process. Create simple benchmarks for freeze, unfreeze, outbound_edges, and contains_edge as soon as they are implemented. This will allow you to prove that your optimizations are effective and will prevent future changes from accidentally causing a performance regression.
Embrace the Two States. The DynamicGraph/CsmGraph split is the core of this design. Resist the temptation to add analytical algorithms to DynamicGraph or mutable operations to CsmGraph. The power of this architecture comes from respecting the boundary. Treat the .freeze() operation as a deliberate, meaningful event: the moment when a chaotic, evolving system locks into a state of order, ready for rigorous, high-speed inspection.
## 10 References
1. **Inspirational Paper:** Liu, X. T., Firoz, J., Gebremedhin, A. H., & Lumsdaine, A. (2022). *NWHy: A Framework for Hypergraph Analytics: Representations, Data structures, and Algorithms*.
2. **Inspirational C++ Repository:** The source code for the NWHypergraph project.
* **URL:** `https://github.com/pnnl/NWHypergraph`
---
## Appendix A: Functional Parity and Migration Guide Foundation
### A.1 Introduction
This appendix demonstrates that the redesigned `next_graph` trait system provides complete functional parity with the original `UltraGraph` traits. It serves as a definitive mapping to guide the migration of existing code from the old API to the new, architecturally improved API. The core change is the distribution of methods into three focused traits: `GraphView`, `GraphMut`, and `GraphAlgorithms`.
### A.2 Method Mapping Table
| Old Trait | Old Method Signature | New Trait | New Counterpart / Method | Implemented By | Migration Notes & Status |
| :--- | :--- | :--- | :--- | :--- | :--- |
| `GraphLike` | `add_node(value: T) -> usize` | `GraphMut` | `add_node(payload: N) -> usize` | `DynamicGraph` | **Direct Mapping** |
| `GraphLike` | `contains_node(index: usize) -> bool` | `GraphView` | `contains_node(index: usize) -> bool` | Both | **Direct Mapping** |
| `GraphLike` | `get_node(index: usize) -> Option<&T>` | `GraphView` | `get_node(index: usize) -> Option<&N>` | Both | **Direct Mapping** |
| `GraphLike` | `remove_node(index: usize)` | `GraphMut` | `(No direct method)` | `DynamicGraph` | **Re-architected.** Direct removal is inefficient on `CsmGraph`. This is now a deliberate `unfreeze` -> modify -> `freeze` lifecycle event. A direct method can be added to `GraphMut` with documented performance caveats. |
| `GraphLike` | `update_node(index: usize, value: T)` | `GraphMut` | `update_node(index: usize, payload: N)` | `DynamicGraph` | **Direct Mapping** |
| `GraphLike` | `add_edge(a: usize, b: usize)` | `GraphMut` | `add_edge(a, b, weight: W)` | `DynamicGraph` | **Enhanced.** Call with `()` as the weight. The new generic method is more powerful. |
| `GraphLike` | `add_edge_with_weight(a, b, weight: u64)` | `GraphMut` | `add_edge(a, b, weight: W)` | `DynamicGraph` | **Superseded.** The new generic method directly covers this use case. |
| `GraphLike` | `contains_edge(a: usize, b: usize) -> bool` | `GraphView` | `contains_edge(a: usize, b: usize) -> bool` | Both | **Direct Mapping** |
| `GraphLike` | `remove_edge(a: usize, b: usize)` | `GraphMut` | `remove_edge(a: usize, b: usize)` | `DynamicGraph` | **Re-architected.** Correctly scoped to the mutable `DynamicGraph` state where it is efficient. |
| `GraphAlgorithms` | `shortest_path(start, stop)` | `GraphAlgorithms` | `shortest_path(start, stop)` | `CsmGraph` | **Direct Mapping.** Correctly scoped to the static analytics state. |
| `GraphAlgorithms` | `outgoing_edges(a: usize)` | `GraphAlgorithms` | `outbound_edges(a: usize)` | `CsmGraph` | **Enhanced.** Renamed for clarity and designed to return a more performant, non-allocating iterator. |
| `GraphRoot` | `add_root_node(value: T) -> usize` | `GraphMut` | `add_root_node(payload: N) -> usize` | `DynamicGraph` | **Direct Mapping.** |
| `GraphRoot` | `contains_root_node() -> bool` | `GraphView` | `contains_root_node() -> bool` | Both | **Direct Mapping.** |
| `GraphRoot` | `get_root_node() -> Option<&T>` | `GraphView` | `get_root_node() -> Option<&N>` | Both | **Direct Mapping.** |
| `GraphRoot` | `get_root_index() -> Option<usize>` | `GraphView` | `get_root_index() -> Option<usize>` | Both | **Direct Mapping.** |
| `GraphRoot` | `get_last_index() -> Result<usize, Err>` | `GraphView` | `(No direct method)` | Both | **Covered.** Trivial to implement as `self.number_nodes().checked_sub(1)`. |
| `GraphStorage` | `size() -> usize` | `GraphView` | *(Default method)* | Both | **Covered.** Can be a default method on `GraphView` returning `self.number_nodes() + self.number_edges()`. |
| `GraphStorage` | `is_empty() -> bool` | `GraphView` | *(Default method)* | Both | **Covered.** Can be a default method on `GraphView` returning `self.number_nodes() == 0`. |
| `GraphStorage` | `number_nodes() -> usize` | `GraphView` | `number_nodes() -> usize` | Both | **Direct Mapping.** |
| `GraphStorage` | `number_edges() -> usize` | `GraphView` | `number_edges() -> usize` | Both | **Direct Mapping.** |
| `GraphStorage` | `get_all_nodes() -> Vec<&T>` | `GraphView` | *(No direct method)* | Both | **Covered, with performance warning.** This expensive `O(V)` allocation is discouraged and can be implemented as a helper function outside the core trait if needed. |
| `GraphStorage` | `get_all_edges() -> Vec<(usize, usize)>` | `GraphView` | *(No direct method)* | Both | **Covered, with performance warning.** This expensive `O(E)` allocation is discouraged and can be implemented as a helper function if needed. |
| `GraphStorage` | `clear()` | `GraphMut` | `clear()` | `DynamicGraph` | **Direct Mapping.** Correctly scoped to the mutable state. |
## Summary of Key Changes
The redesigned trait system not only provides functional parity but introduces significant architectural improvements:
Clear Separation of Concerns: The single biggest improvement. By separating read-only (GraphView), mutable (GraphMut), and analytical (GraphAlgorithms) operations, the API is now self-documenting. It is immediately obvious which operations are "cheap" vs. "expensive" and which state (DynamicGraph vs. CsmGraph) is required.
Enhanced Generics: The new traits are fully generic over both node payload N and edge weight W. This replaces the separate add_edge and add_edge_with_weight methods with a single, more powerful add_edge that handles both weighted and unweighted cases with zero cost.
Superior Performance by Design: Methods like outbound_edges are now designed to return non-allocating iterators directly from the CSR data structure, which is a major performance win over the original design that required collecting results into a Vec.
Architectural Alignment: The remove_node and remove_edge methods, which were conceptually at odds with a high-performance static graph, are now correctly placed within the GraphMut trait, signaling that they belong exclusively to the dynamic, evolutionary state of the graph.
This redesign provides a complete and superior replacement for the old trait system, creating a foundation that is robust, performant, and perfectly aligned with the dynamic nature of DeepCausality.