## `bounded_graph`
_A thin newtype wrapper for [`petgraph`](https://github.com/petgraph/petgraph) to assist in the creation of graphs with restrictions on their edges_
This crate is a simple wrapper around petgraph's `Graph` and `StableGraph` types. It exists to make it simpler to enforce restrictions at the time of edge creation, to ensure that the graph is never in a state with an "invalid" edge between two nodes.
---
In order to do so, your Node type should implement the following trait:
```rust
pub trait BoundedNode<Ix: IndexType = DefaultIx> {
fn can_add_edge(&self, dir: Direction, existing_edge_count: usize, other_node: &Self) -> bool;
}
```
Alternatively, for the common and simple situation of a Node with an associated limit on incoming and outgoing edges, one can alternatively implement the following traits:
```rust
pub trait EdgeBounds<Ix: IndexType = DefaultIx> {
fn max_incoming_edges(&self) -> Ix;
fn max_outgoing_edges(&self) -> Ix;
}
pub trait SimpleEdgeBounds {}
```
Implementing both `EdgeBounds` and the marker trait `SimpleEdgeBounds` will automatically provide a `BoundedNode` implementation that checks edge counts without considering properties of the other node
## Convenience Types
For most use cases, you don't need to implement these traits manually. This crate provides two convenient node types:
### `FixedEdgeCount<MAX_IN, MAX_OUT, T>`
A generic node type with compile-time fixed edge limits using const generics:
- `MAX_IN` - Maximum number of incoming edges
- `MAX_OUT` - Maximum number of outgoing edges (defaults to `MAX_IN` for symmetric limits)
- `T` - User data type (defaults to `()`)
**Examples:**
```rust
use bounded_graph::{BoundedGraph, FixedEdgeCount};
// Asymmetric limits: 2 incoming, 5 outgoing
let mut graph = BoundedGraph::<FixedEdgeCount<2, 5>, ()>::new();
let hub = graph.add_node(FixedEdgeCount::empty());
let spoke = graph.add_node(FixedEdgeCount::empty());
graph.add_edge(hub, spoke, ()).unwrap();
// With custom data
let mut graph = BoundedGraph::<FixedEdgeCount<3, 3, String>, ()>::new();
let node = graph.add_node(FixedEdgeCount::new("my_node".to_string()));
```
### `SymmetricFixedEdgeCount<MAX, T>`
A type alias for `FixedEdgeCount` where incoming and outgoing limits are the same:
```rust
use bounded_graph::{BoundedGraph, SymmetricFixedEdgeCount};
// Node with max 3 edges in each direction
let mut graph = BoundedGraph::<SymmetricFixedEdgeCount<3>, ()>::new();
let n1 = graph.add_node(SymmetricFixedEdgeCount::empty());
let n2 = graph.add_node(SymmetricFixedEdgeCount::empty());
graph.add_edge(n1, n2, ()).unwrap();
```
These types automatically implement `BoundedNode`, `EdgeBounds`, `SimpleEdgeBounds`, and `ImmutableEdgeBounds`, providing a complete solution for common edge-limiting scenarios without boilerplate.
---
## Graph Type Selection
`BoundedGraph` is generic over the underlying petgraph implementation via the `G` type parameter:
```rust
pub struct BoundedGraph<N, E, G = Graph<N, E, Directed, DefaultIx>>
```
By default, it uses petgraph's [`Graph`](https://docs.rs/petgraph/latest/petgraph/graph/struct.Graph.html), but you can explicitly choose between different graph types depending on your needs.
### Type Aliases
For convenience, the library provides type aliases for common configurations:
**Using `Graph` (compact, faster, but node/edge indices may change):**
- `BoundedDiGraph<N, E>` - Directed graph
- `BoundedUnGraph<N, E>` - Undirected graph
**Using `StableGraph` (stable indices that remain valid after removals):**
- `BoundedStableDiGraph<N, E>` - Directed stable graph
- `BoundedStableUnGraph<N, E>` - Undirected stable graph
### Choosing Between Graph Types
**Use `Graph` (default)** when:
- You don't need to remove nodes or edges during graph lifetime
- You want maximum performance and minimal memory usage
- Index stability after removal isn't required
- Note: In `Graph`, removing a node or edge swaps it with the last element, potentially changing indices
**Use `StableGraph`** when:
- You need to remove nodes or edges and keep other indices valid
- You're building long-lived graphs with dynamic structure
- You need stable node/edge references across modifications
- Note: `StableGraph` keeps indices stable across removals at the cost of slightly higher memory usage
### Examples
Using the default `Graph`:
```rust
use bounded_graph::{BoundedGraph, FixedEdgeCount};
// Explicitly using Graph (same as default)
let mut graph = BoundedGraph::<FixedEdgeCount<3>, ()>::new();
```
Using `StableGraph` with type aliases:
```rust
use bounded_graph::{BoundedStableDiGraph, FixedEdgeCount};
let mut graph = BoundedStableDiGraph::<FixedEdgeCount<3>, ()>::new();
let n1 = graph.add_node(FixedEdgeCount::empty());
let n2 = graph.add_node(FixedEdgeCount::empty());
let n3 = graph.add_node(FixedEdgeCount::empty());
// n1's index remains valid even after removing n2
graph.remove_node(n2);
assert!(graph.node_weight(n1).is_some());
```
Using explicit type parameters for undirected graphs:
```rust
use bounded_graph::BoundedUnGraph;
use bounded_graph::FixedEdgeCount;
// Undirected graph - edges work in both directions
let mut graph = BoundedUnGraph::<FixedEdgeCount<3>, ()>::new();
let n1 = graph.add_node(FixedEdgeCount::empty());
let n2 = graph.add_node(FixedEdgeCount::empty());
// In undirected graphs, this edge connects both ways
graph.add_edge(n1, n2, ()).unwrap();
```
---
`BoundedGraph` implements `Deref` and `AsRef<G>`, allowing you to access all methods and traits of the underlying graph directly (though adding and updating edges is now a failable operation). You can obtain a reference to the underlying graph by calling `as_ref()` or through automatic deref coercion.
## Acyclic Graphs
For scenarios where you need both edge capacity constraints **and** cycle prevention (directed acyclic graphs / DAGs), the library provides `BoundedAcyclicGraph`, which wraps petgraph's `Acyclic` wrapper along with `BoundedGraph`.
### BoundedAcyclicGraph
`BoundedAcyclicGraph` combines two types of constraints:
1. **Capacity constraints** - Node edge limits enforced by `BoundedNode`
2. **Acyclicity constraints** - Prevents cycles using petgraph's dynamic topological ordering
When adding an edge, both constraints are checked:
- First, the node capacity constraints are validated
- Then, the acyclicity constraint is checked (would this edge create a cycle?)
```rust
use bounded_graph::{BoundedAcyclicDiGraph, FixedEdgeCount, BoundedAcyclicGraphError};
// Create a bounded acyclic graph (DAG)
let mut graph = BoundedAcyclicDiGraph::<FixedEdgeCount<2>, &str>::new();
let a = graph.add_node(FixedEdgeCount::empty());
let b = graph.add_node(FixedEdgeCount::empty());
let c = graph.add_node(FixedEdgeCount::empty());
// Valid edges that don't create cycles
graph.add_edge(a, b, "a->b").unwrap();
graph.add_edge(b, c, "b->c").unwrap();
// This would create a cycle: C -> A -> B -> C
match graph.add_edge(c, a, "would-cycle") {
Err(BoundedAcyclicGraphError::WouldCreateCycle) => {
println!("Cycle prevented!");
}
_ => panic!("Expected cycle error"),
}
// Iterate in topological order (parents before children)
for node_idx in graph.topological_iter() {
println!("Node: {:?}", node_idx);
}
```
### Type Aliases
Similar to `BoundedGraph`, convenient type aliases are provided:
- `BoundedAcyclicDiGraph<N, E>` - Using `Graph`
- `BoundedAcyclicStableDiGraph<N, E>` - Using `StableGraph`
### Error Handling
`BoundedAcyclicGraph` uses `BoundedAcyclicGraphError<Ix>` which wraps either:
- `Bounded(BoundedGraphError)` - Node capacity constraint violation
- `Acyclic(AcyclicEdgeError<NodeIndex<Ix>>)` - Acyclic constraint violation from petgraph
The `Acyclic` variant preserves the full error information from petgraph's cycle detection, which can be:
- `Cycle(Cycle<NodeIndex<Ix>>)` - Adding the edge would create a cycle (includes cycle information)
- `SelfLoop` - The edge would create a self-loop
- `InvalidEdge` - Could not add edge to underlying graph
```rust
use bounded_graph::{BoundedAcyclicGraphError, BoundedGraphError};
use petgraph::acyclic::AcyclicEdgeError;
// Automatic conversion from BoundedGraphError
let error: BoundedAcyclicGraphError = BoundedGraphError::SourceNodeFull.into();
// This creates: BoundedAcyclicGraphError::Bounded(BoundedGraphError::SourceNodeFull)
// Pattern matching on errors
match graph.add_edge(a, b, ()) {
Ok(edge) => println!("Added edge: {:?}", edge),
Err(BoundedAcyclicGraphError::Bounded(err)) => {
println!("Capacity error: {}", err);
}
Err(BoundedAcyclicGraphError::Acyclic(AcyclicEdgeError::Cycle(cycle))) => {
println!("Would create cycle involving {} nodes", cycle.len());
}
Err(BoundedAcyclicGraphError::Acyclic(AcyclicEdgeError::SelfLoop)) => {
println!("Self-loops not allowed");
}
Err(BoundedAcyclicGraphError::Acyclic(AcyclicEdgeError::InvalidEdge)) => {
println!("Could not add edge to graph");
}
}
```
### Topological Operations
`BoundedAcyclicGraph` provides access to petgraph's topological ordering features:
```rust
use bounded_graph::BoundedAcyclicDiGraph;
use bounded_graph::FixedEdgeCount;
let mut graph = BoundedAcyclicDiGraph::<FixedEdgeCount<5>, ()>::new();
let a = graph.add_node(FixedEdgeCount::empty());
let b = graph.add_node(FixedEdgeCount::empty());
graph.add_edge(a, b, ()).unwrap();
// Iterate nodes in topological order
for node in graph.topological_iter() {
println!("{:?}", node);
}
// Get the topological position of a node
let pos = graph.get_position(a);
// Get the node at a specific topological position
if let Some(node) = graph.at_position(pos.unwrap()) {
println!("Node at position: {:?}", node);
}
```
### Known Limitations
**Node and Edge Removal:** The petgraph `Acyclic` wrapper does not expose methods for removing nodes or edges. Therefore:
- `remove_node()` and `remove_edge()` methods are provided but always return `None`
- This is documented as a known limitation of the underlying `Acyclic` wrapper
- If you need removal operations, use `BoundedGraph` directly (without acyclic constraint)
See the [acyclic tests](src/tests/acyclic_tests.rs) for comprehensive usage examples.
---
## Mutation Safety
To prevent edge-limiting guarantees from being violated through mutation, `BoundedGraph` only implements petgraph's `DataMapMut` trait (which provides mutable access to node weights) for node types that implement the `ImmutableEdgeBounds` marker trait.
### Safe Node Types
Node types with **immutable** edge bounds (e.g., using const generics like `FixedEdgeCount<2>`) can safely implement `ImmutableEdgeBounds` and gain mutable access:
```rust
use bounded_graph::{BoundedGraph, FixedEdgeCount};
use petgraph::data::DataMapMut;
let mut graph = BoundedGraph::<FixedEdgeCount<2, String>, ()>::new();
let n = graph.add_node(FixedEdgeCount::new("Hello".to_string()));
// This works because FixedEdgeCount implements ImmutableEdgeBounds
DataMapMut::node_weight_mut(&mut graph, n).unwrap().data = "World".to_string();
```
### Unsafe Node Types
Node types where edge bounds are stored in mutable fields **cannot** implement `ImmutableEdgeBounds` and will not have `DataMapMut` access:
```rust
struct UnsafeNode {
max_edges: usize, // Mutable!
}
// This correctly DOES NOT compile:
// DataMapMut::node_weight_mut(&mut graph, n);
// Error: UnsafeNode doesn't implement ImmutableEdgeBounds
```
This design ensures that edge limiting guarantees cannot be violated after graph construction. See the [mutation_safety.rs](src/tests/mutation_safety.rs) tests for detailed demonstrations.
---
## Optional Features
### `serde-1`
Enable serialization support via serde:
```toml
[dependencies]
bounded_graph = { version = "0.3", features = ["serde-1"] }
```
This derives `Serialize` and `Deserialize` for `BoundedGraph`, `FixedEdgeCount`, and `BoundedGraphError`.
---
## Development
### Running Tests
To run all tests including those for optional features:
```bash
cargo test --all-features
```
To run only serde-related tests:
```bash
cargo test --features serde-1
```
### IDE Support
For the best development experience, configure rust-analyzer to check code with all features enabled, ensuring IntelliSense works for feature-gated code. Add to your IDE's Rust language server configuration:
```json
"rust-analyzer.cargo.features": "all"
```
---
## Current Limitations
* **Build trait** - The `Build` trait's `update_edge` method has an infallible signature (returns `EdgeId` instead of `Result`), which is incompatible with bounded constraint checking. Instead, `BoundedGraph` provides its own `update_edge` method that returns `Result<EdgeIndex, BoundedGraphError>` for proper error handling.
Please let me know if anything else is missing or incorrect!