Trait Graph

pub trait Graph<NodeWeight, EdgeWeight> {
    type NodeRef: Copy + Eq + Hash + Ord + Debug;
    type EdgeRef: Copy + Eq + Hash + Ord + Debug;
    type AdjacentEdgesIterator<'a>: Iterator<Item = Self::EdgeRef>
       where Self: 'a;
    type IncomingEdgesIterator<'a>: Iterator<Item = Self::EdgeRef>
       where Self: 'a;
    type OutgoingEdgesIterator<'a>: Iterator<Item = Self::EdgeRef>
       where Self: 'a;
    type NodeWeightsIterator<'a>: Iterator<Item = &'a NodeWeight>
       where Self: 'a,
             NodeWeight: 'a;
    type EdgeWeightsIterator<'a>: Iterator<Item = &'a EdgeWeight>
       where Self: 'a,
             EdgeWeight: 'a;
    type NodesIterator<'a>: Iterator<Item = Self::NodeRef>
       where Self: 'a;
    type EdgesIterator<'a>: Iterator<Item = Self::EdgeRef>
       where Self: 'a;

    // Required methods
    fn is_directed(&self) -> bool;
    fn is_directed_edge(&self, edge: Self::EdgeRef) -> bool;
    fn adjacent_edges(
        &self,
        node: Self::NodeRef,
    ) -> Self::AdjacentEdgesIterator<'_>;
    fn incoming_edges(
        &self,
        node: Self::NodeRef,
    ) -> Self::IncomingEdgesIterator<'_>;
    fn outgoing_edges(
        &self,
        node: Self::NodeRef,
    ) -> Self::OutgoingEdgesIterator<'_>;
    fn adjacent_nodes(
        &self,
        edge: Self::EdgeRef,
    ) -> (Self::NodeRef, Self::NodeRef);
    fn node_weight(&self, node: Self::NodeRef) -> &NodeWeight;
    fn edge_weight(&self, edge: Self::EdgeRef) -> &EdgeWeight;
    fn node_weights(&self) -> Self::NodeWeightsIterator<'_>;
    fn edge_weights(&self) -> Self::EdgeWeightsIterator<'_>;
    fn nodes(&self) -> Self::NodesIterator<'_>;
    fn edges(&self) -> Self::EdgesIterator<'_>;
    fn count_nodes(&self) -> usize;
    fn count_edges(&self) -> usize;

    // Provided method
    fn is_empty_graph(&self) -> bool { ... }
}

Graph is a generic trait specifying the functionality that must be implemented by Graph storage backends used for Querying.

Required Associated Types

type NodeRef: Copy + Eq + Hash + Ord + Debug

NodeRef is the associated type for node references.

It implements the Ord trait (compare references), Eq + Hash (allows insertion of Node Weights and their references into a Table), Copy (allows use of references in function parameters), and Debug (simplifies debugging).

type EdgeRef: Copy + Eq + Hash + Ord + Debug

EdgeRef is the associated type for edge references.

It implements the same traits as NodeRef.

type AdjacentEdgesIterator<'a>: Iterator<Item = Self::EdgeRef> where Self: 'a

type IncomingEdgesIterator<'a>: Iterator<Item = Self::EdgeRef> where Self: 'a

type OutgoingEdgesIterator<'a>: Iterator<Item = Self::EdgeRef> where Self: 'a

type NodeWeightsIterator<'a>: Iterator<Item = &'a NodeWeight> where Self: 'a, NodeWeight: 'a

type EdgeWeightsIterator<'a>: Iterator<Item = &'a EdgeWeight> where Self: 'a, EdgeWeight: 'a

type NodesIterator<'a>: Iterator<Item = Self::NodeRef> where Self: 'a

type EdgesIterator<'a>: Iterator<Item = Self::EdgeRef> where Self: 'a

Required Methods

fn is_directed(&self) -> bool

Checks if the edges of this graph are directed.

fn is_directed_edge(&self, edge: Self::EdgeRef) -> bool

Checks if the given edge is directed.

fn adjacent_edges(&self, node: Self::NodeRef) -> Self::AdjacentEdgesIterator<'_>

Gets a readonly handle of all adjacent edges of a node.

For directed graphs, this includes all incoming and outgoing edges.

fn incoming_edges(&self, node: Self::NodeRef) -> Self::IncomingEdgesIterator<'_>

Gets a readonly handle of all incoming edges of a node.

For undirected graphs this is equivalent to calling adjacent_edges.

fn outgoing_edges(&self, node: Self::NodeRef) -> Self::OutgoingEdgesIterator<'_>

Gets a readonly handle of all outgoing edges of a node.

For undirected graphs this is equivalent to calling adjacent_edges.

fn adjacent_nodes(&self, edge: Self::EdgeRef) -> (Self::NodeRef, Self::NodeRef)

Gets a readonly handle of the nodes an edge connects.

If the edge is directed, the first node is its source, and the second node its destination.

fn node_weight(&self, node: Self::NodeRef) -> &NodeWeight

Retrieve weight from a node reference.

fn edge_weight(&self, edge: Self::EdgeRef) -> &EdgeWeight

Retrieve weight from an edge reference.

fn node_weights(&self) -> Self::NodeWeightsIterator<'_>

Returns an Iterator over all node weights.

fn edge_weights(&self) -> Self::EdgeWeightsIterator<'_>

Returns an Iterator over all edge weights.

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

Returns an Iterator over all nodes by their references.

fn edges(&self) -> Self::EdgesIterator<'_>

Returns an Iterator over all edges by their references.

fn count_nodes(&self) -> usize

Returns the number of nodes in this graph.

fn count_edges(&self) -> usize

Returns the number of edges in this graph.

Provided Methods

fn is_empty_graph(&self) -> bool

Tests if the given graph 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.

Implementations on Foreign Types

impl<NodeWeight, EdgeWeight, Direction, IndexType> Graph<NodeWeight, EdgeWeight> for Graph<NodeWeight, EdgeWeight, Direction, IndexType>

where IndexType: IndexType, Direction: EdgeType,

Example implementation for in memory graphs stored using the petgraph library.

Both undirected and directed graphs are supported.

Node and Edge indices are by default 32-bit unsigned integers. Valid indices are {0, …, n - 1} and {0, …, m - 1}, where n is the number of nodes, and m the number of edges stored in this graph implementation.

type NodeRef = NodeIndex<IndexType>

type EdgeRef = EdgeIndex<IndexType>

type AdjacentEdgesIterator<'a> = impl Iterator<Item = <Graph<NodeWeight, EdgeWeight, Direction, IndexType> as Graph<NodeWeight, EdgeWeight>>::EdgeRef> + 'a where Self: 'a

type IncomingEdgesIterator<'a> = impl Iterator<Item = <Graph<NodeWeight, EdgeWeight, Direction, IndexType> as Graph<NodeWeight, EdgeWeight>>::EdgeRef> + 'a where Self: 'a

type OutgoingEdgesIterator<'a> = impl Iterator<Item = <Graph<NodeWeight, EdgeWeight, Direction, IndexType> as Graph<NodeWeight, EdgeWeight>>::EdgeRef> + 'a where Self: 'a

type NodesIterator<'a> = impl Iterator<Item = <Graph<NodeWeight, EdgeWeight, Direction, IndexType> as Graph<NodeWeight, EdgeWeight>>::NodeRef> + 'a where Self: 'a

type EdgesIterator<'a> = impl Iterator<Item = <Graph<NodeWeight, EdgeWeight, Direction, IndexType> as Graph<NodeWeight, EdgeWeight>>::EdgeRef> + 'a where Self: 'a

type NodeWeightsIterator<'a> = impl Iterator<Item = &'a NodeWeight> + 'a where Self: 'a, NodeWeight: 'a

type EdgeWeightsIterator<'a> = impl Iterator<Item = &'a EdgeWeight> + 'a where Self: 'a, EdgeWeight: 'a

fn is_directed(&self) -> bool

fn is_directed_edge(&self, edge: Self::EdgeRef) -> bool

fn adjacent_edges(&self, node: Self::NodeRef) -> Self::AdjacentEdgesIterator<'_>

fn incoming_edges(&self, node: Self::NodeRef) -> Self::IncomingEdgesIterator<'_>

fn outgoing_edges(&self, node: Self::NodeRef) -> Self::OutgoingEdgesIterator<'_>

fn adjacent_nodes(&self, edge: Self::EdgeRef) -> (Self::NodeRef, Self::NodeRef)

fn node_weight(&self, node: Self::NodeRef) -> &NodeWeight

fn edge_weight(&self, edge: Self::EdgeRef) -> &EdgeWeight

fn node_weights(&self) -> Self::NodeWeightsIterator<'_>

fn edge_weights(&self) -> Self::EdgeWeightsIterator<'_>

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

fn edges(&self) -> Self::EdgesIterator<'_>

fn count_edges(&self) -> usize

fn count_nodes(&self) -> usize

Implementors

impl<'g, BaseNodeWeight, BaseEdgeWeight, NodeWeight, EdgeWeight, Graph: Graph<BaseNodeWeight, BaseEdgeWeight>> Graph<NodeWeight, EdgeWeight> for FilterMap<'g, BaseNodeWeight, BaseEdgeWeight, NodeWeight, EdgeWeight, Graph>

type NodeRef = <Graph as Graph<BaseNodeWeight, BaseEdgeWeight>>::NodeRef

type EdgeRef = <Graph as Graph<BaseNodeWeight, BaseEdgeWeight>>::EdgeRef

type AdjacentEdgesIterator<'a> = impl Iterator<Item = <Graph as Graph<BaseNodeWeight, BaseEdgeWeight>>::EdgeRef> + 'a where Self: 'a

type IncomingEdgesIterator<'a> = impl Iterator<Item = <Graph as Graph<BaseNodeWeight, BaseEdgeWeight>>::EdgeRef> + 'a where Self: 'a

type OutgoingEdgesIterator<'a> = impl Iterator<Item = <Graph as Graph<BaseNodeWeight, BaseEdgeWeight>>::EdgeRef> + 'a where Self: 'a

type NodeWeightsIterator<'a> = impl Iterator<Item = &'a NodeWeight> where Self: 'a, NodeWeight: 'a

type EdgeWeightsIterator<'a> = impl Iterator<Item = &'a EdgeWeight> where Self: 'a, EdgeWeight: 'a

type NodesIterator<'a> = impl Iterator<Item = <Graph as Graph<BaseNodeWeight, BaseEdgeWeight>>::NodeRef> + 'a where Self: 'a

type EdgesIterator<'a> = impl Iterator<Item = <Graph as Graph<BaseNodeWeight, BaseEdgeWeight>>::EdgeRef> + 'a where Self: 'a