Crate bounded_graph

Expand description

A bounded graph implementation that enforces edge count constraints on nodes.

This crate provides a wrapper around petgraph::Graph and petgraph::stable_graph::StableGraph that ensures nodes cannot exceed their defined edge limits when adding connections. All edge addition operations check the bounds before modifying the graph.

§Features

Flexible constraint system: Define custom edge constraints via the BoundedNode trait
Simple edge bounds: Use EdgeBounds + SimpleEdgeBounds for basic numeric limits
Convenience types: Use FixedEdgeCount or SymmetricFixedEdgeCount for quick node creation with fixed limits
Petgraph compatible: Implements most petgraph traits for seamless integration
Acyclic graphs: Specialized BoundedAcyclicGraph variants that combines edge bounds enforcement from this crate with acyclicity enforcement built into petgraph
Type-safe error handling: Returns BoundedGraphError or BoundedAcyclicGraphError instead of panicking

§Quick Start Example

SymmetricFixedEdgeCount provides a simple way to create nodes with the same maximum number of incoming and outgoing edges:

use bounded_graph::{BoundedGraph, SymmetricFixedEdgeCount};

// Create a graph where each node can have at most 2 edges (both incoming and outgoing)
let mut graph = BoundedGraph::<SymmetricFixedEdgeCount<2>, ()>::new();
let n1 = graph.add_node(SymmetricFixedEdgeCount::empty());
let n2 = graph.add_node(SymmetricFixedEdgeCount::empty());
let n3 = graph.add_node(SymmetricFixedEdgeCount::empty());

// These succeed
assert!(graph.add_edge(n1, n2, ()).is_ok());
assert!(graph.add_edge(n1, n3, ()).is_ok());

// This fails - n1 already has 2 outgoing edges
let n4 = graph.add_node(SymmetricFixedEdgeCount::empty());
assert!(graph.add_edge(n1, n4, ()).is_err());

§Asymmetric Edge Limits

FixedEdgeCount supports different limits for incoming and outgoing edges:

use bounded_graph::{BoundedGraph, FixedEdgeCount};

// Create nodes with 2 max incoming, 5 max outgoing edges
let mut graph = BoundedGraph::<FixedEdgeCount<2, 5>, ()>::new();
let hub = graph.add_node(FixedEdgeCount::empty());
let spoke1 = graph.add_node(FixedEdgeCount::empty());
let spoke2 = graph.add_node(FixedEdgeCount::empty());

// Hub can send to many spokes
assert!(graph.add_edge(hub, spoke1, ()).is_ok());
assert!(graph.add_edge(hub, spoke2, ()).is_ok());
// ... up to 5 outgoing edges

§Custom Edge Bounds

For more control, implement EdgeBounds directly:

use bounded_graph::{BoundedGraph, EdgeBounds, SimpleEdgeBounds};
use petgraph::graph::DefaultIx;

#[derive(Default)]
struct TwiceLimitedNode {
    max_in: usize,
    max_out: usize,
}

impl EdgeBounds for TwiceLimitedNode {
    fn max_incoming_edges(&self) -> DefaultIx {
        2 * self.max_in as DefaultIx
    }

    fn max_outgoing_edges(&self) -> DefaultIx {
        2 * self.max_out as DefaultIx
    }
}

impl SimpleEdgeBounds for TwiceLimitedNode {}

let mut graph = BoundedGraph::<TwiceLimitedNode, ()>::new();
let n1 = graph.add_node(TwiceLimitedNode { max_in: 2, max_out: 2 });
let n2 = graph.add_node(TwiceLimitedNode { max_in: 2, max_out: 2 });

// This will succeed
assert!(graph.add_edge(n1, n2, ()).is_ok());

For complete control with custom logic, implement BoundedNode directly:

use bounded_graph::{BoundedGraph, BoundedNode};
use petgraph::Direction;

#[derive(Clone, PartialEq)]
enum Color { Red, Blue, Green }

struct ColoredNode {
    color: Color,
}

impl BoundedNode for ColoredNode {
    fn can_add_edge(&self, _dir: Direction, _count: usize, other: &Self) -> bool {
        // Only allow edges between nodes of the same color
        self.color == other.color
    }
}

let mut graph = BoundedGraph::<ColoredNode, ()>::new();
let red1 = graph.add_node(ColoredNode { color: Color::Red });
let red2 = graph.add_node(ColoredNode { color: Color::Red });
let blue = graph.add_node(ColoredNode { color: Color::Blue });

// Same color - succeeds
assert!(graph.add_edge(red1, red2, ()).is_ok());
// Different colors - fails
assert!(graph.add_edge(red1, blue, ()).is_err());

Structs§

BoundedAcyclicGraph: A bounded graph that also enforces acyclicity (DAG property).
BoundedGraph: A graph wrapper that enforces edge count constraints on nodes.
EdgeIndex: Edge identifier.
FixedEdgeCount: A simple node type with fixed edge count limits.
NodeIndex: Node identifier.

Enums§

BoundedAcyclicGraphError: Error type for bounded acyclic graph operations.
BoundedGraphError: Error type for bounded graph operations.
Directed: Marker type for a directed graph.
Direction: Edge direction.
Undirected: Marker type for an undirected graph.

Traits§

BoundedNode: Trait for nodes that can enforce edge count constraints.
EdgeBounds: Trait for nodes with simple numeric edge count bounds.
ImmutableEdgeBounds: Marker trait indicating that a node’s edge restrictions cannot be mutated after creation.
SimpleEdgeBounds: Marker trait indicating that a node uses simple edge count logic.

Type Aliases§

BoundedAcyclicDiGraph: A directed bounded acyclic graph using Graph with default index type.
BoundedAcyclicStableDiGraph: A directed bounded acyclic graph using StableGraph with default index type.
BoundedDiGraph: A directed bounded graph using Graph with default index type.
BoundedStableDiGraph: A directed bounded graph using StableGraph with default index type.
BoundedStableUnGraph: An undirected bounded graph using StableGraph with default index type.
BoundedUnGraph: An undirected bounded graph using Graph with default index type.
DefaultIx: The default integer type for graph indices. u32 is the default to reduce the size of the graph’s data and improve performance in the common case.
SymmetricFixedEdgeCount: A simplified node type with symmetric edge count limits.