bounded_graph

bounded_graph

A thin newtype wrapper for 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:

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:

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:

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:

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:

pub struct BoundedGraph<N, E, G = Graph<N, E, Directed, DefaultIx>>

By default, it uses petgraph's Graph, 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:

use bounded_graph::{BoundedGraph, FixedEdgeCount};

// Explicitly using Graph (same as default)
let mut graph = BoundedGraph::<FixedEdgeCount<3>, ()>::new();

Using StableGraph with type aliases:

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:

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?)

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

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:

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 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:

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:

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 tests for detailed demonstrations.

Optional Features

serde-1

Enable serialization support via serde:

[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:

cargo test --all-features

To run only serde-related tests:

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:

"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!