Trait Graph 

pub trait Graph {
    type NodeData;
    type Weight;
    type NodeIter<'a>: Iterator<Item = NodeId>
       where Self: 'a;
    type NeighborIter<'a>: Iterator<Item = (NodeId, &'a Self::Weight)>
       where Self: 'a;

    // Required methods
    fn add_node(&mut self, data: Self::NodeData) -> NodeId;
    fn add_edge(
        &mut self,
        from: NodeId,
        to: NodeId,
        weight: Self::Weight,
    ) -> Result<(), GraphError>;
    fn remove_node(&mut self, id: NodeId) -> Option<Self::NodeData>;
    fn node_count(&self) -> usize;
    fn edge_count(&self) -> usize;
    fn contains_node(&self, id: NodeId) -> bool;
    fn contains_edge(&self, from: NodeId, to: NodeId) -> bool;
    fn degree(&self, id: NodeId) -> usize;
    fn nodes(&self) -> Self::NodeIter<'_>;
    fn neighbors(&self, id: NodeId) -> Self::NeighborIter<'_>;

    // Provided methods
    fn all_edges(&self) -> Vec<Edge<Self::Weight>>
       where Self::Weight: Clone { ... }
    fn is_empty(&self) -> bool { ... }
}

The central graph abstraction that every algorithm in graph-rs operates on.

N is the node-data type and W is the edge-weight type.

Implementors provide two associated iterator types — NodeIter<'a> and NeighborIter<'a> — that borrow from &self. These are Generic Associated Types (GATs, stable since Rust 1.65): associated types that are themselves generic over a lifetime, enabling zero-allocation iterators that reference graph internals directly.

Implementing Graph

use graph_core::{Graph, NodeId, Edge};

struct MyGraph { /* ... */ }

impl Graph for MyGraph {
    type NodeData = String;
    type Weight   = f64;
    // ... (see AdjacencyList for a complete example)
}

Required Associated Types

type NodeData

Data stored at each node (e.g. String, (), coordinates).

type Weight

Edge-weight type (e.g. f64, u32, ()).

type NodeIter<'a>: Iterator<Item = NodeId> where Self: 'a

Iterator over all NodeIds in the graph.

type NeighborIter<'a>: Iterator<Item = (NodeId, &'a Self::Weight)> where Self: 'a

Iterator over (neighbour_id, &weight) pairs for one node.

Required Methods

fn add_node(&mut self, data: Self::NodeData) -> NodeId

Adds a node with the given data and returns its NodeId.

fn add_edge( &mut self, from: NodeId, to: NodeId, weight: Self::Weight, ) -> Result<(), GraphError>

Adds a directed edge from from to to with weight.

Errors

Returns GraphError if either node does not exist.

fn remove_node(&mut self, id: NodeId) -> Option<Self::NodeData>

Removes the node at id and all edges incident to it.

Returns the node data if found, or None if the node did not exist.

fn node_count(&self) -> usize

Returns the number of nodes.

fn edge_count(&self) -> usize

Returns the number of directed edges.

fn contains_node(&self, id: NodeId) -> bool

Returns true if the graph contains a node with this id.

fn contains_edge(&self, from: NodeId, to: NodeId) -> bool

Returns true if there is a directed edge from from to to.

fn degree(&self, id: NodeId) -> usize

Returns the out-degree of node id (number of outgoing edges).

Panics

Panics if id does not exist in the graph.

fn nodes(&self) -> Self::NodeIter<'_>

Returns an iterator over all NodeIds in the graph.

fn neighbors(&self, id: NodeId) -> Self::NeighborIter<'_>

Returns an iterator over (neighbour_id, &weight) for all outgoing edges of id.

Panics

Panics if id does not exist in the graph.

Provided Methods

fn all_edges(&self) -> Vec<Edge<Self::Weight>>

where Self::Weight: Clone,

Returns all edges in the graph as Edge<W> values.

Default implementation iterates over all nodes and their neighbours. Implementations may override this for efficiency.

fn is_empty(&self) -> bool

Returns true if the graph has no nodes.

Examples

use graph_core::{AdjacencyList, Graph};

let g: AdjacencyList<()> = AdjacencyList::directed();
assert!(g.is_empty());

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors

impl<N, W> Graph for AdjacencyList<N, W>

where W: Clone,

type NodeData = N

type Weight = W

type NodeIter<'a> = NodeIter where AdjacencyList<N, W>: 'a

type NeighborIter<'a> = NeighborIter<'a, W> where AdjacencyList<N, W>: 'a

impl<N, W> Graph for AdjacencyMatrix<N, W>

where W: Clone,

type NodeData = N

type Weight = W

type NodeIter<'a> = NodeIter where AdjacencyMatrix<N, W>: 'a

type NeighborIter<'a> = NeighborIter<'a, W> where AdjacencyMatrix<N, W>: 'a