Trait GraphEngine

pub trait GraphEngine: Sized {
    type NeighborIterator<'a>: DoubleEndedIterator<Item = usize>
       where Self: 'a;
    type BridgeIterator<'a>: DoubleEndedIterator<Item = IndeterminateEdge>
       where Self: 'a;
    type NodeTraverser<'a>: DoubleEndedIterator<Item = usize>
       where Self: 'a;
    type EdgeTraverser<'a>: DoubleEndedIterator<Item = usize>
       where Self: 'a;
    type BridgeTraverser<'a>: DoubleEndedIterator<Item = IndeterminateEdge>
       where Self: 'a;

    // Required methods
    fn graph_kind(&self) -> GraphKind;
    fn get_node(&self, node: usize) -> Result<usize, GraphError>;
    fn all_nodes<'a>(&'a self) -> Self::NodeTraverser<'a>;
    fn all_neighbors<'a>(&'a self, node: usize) -> Self::NeighborIterator<'a>;
    fn get_edge(&self, edge: usize) -> Result<usize, GraphError>;
    fn all_edges<'a>(&'a self) -> Self::EdgeTraverser<'a>;
    fn get_bridge(&self, edge: usize) -> Result<IndeterminateEdge, GraphError>;
    fn get_bridges<'a>(
        &'a self,
        from: usize,
        goto: usize,
    ) -> Self::BridgeIterator<'a>;
    fn all_bridges<'a>(&'a self) -> Self::BridgeTraverser<'a>;

    // Provided methods
    fn count_nodes<'a>(&'a self) -> usize { ... }
    fn all_outgoing<'a>(&'a self, node: usize) -> Self::NeighborIterator<'a> { ... }
    fn all_incoming<'a>(&'a self, node: usize) -> Self::NeighborIterator<'a> { ... }
    fn count_degree<'a>(&'a self, node: usize) -> NodeDegree { ... }
    fn count_edges<'a>(&'a self) -> usize { ... }
    fn size_hint(&self) -> usize { ... }
}

Represent a graph storage, with a set of nodes and edges.

Examples

use graph_theory::GraphEngine;

Required Associated Types

type NeighborIterator<'a>: DoubleEndedIterator<Item = usize> where Self: 'a

According to a given vertex, find all neighbor nodes. See more in Self::all_neighbors, Self::all_incoming, Self::all_outgoing.

type BridgeIterator<'a>: DoubleEndedIterator<Item = IndeterminateEdge> where Self: 'a

An iterator over the edges.

type NodeTraverser<'a>: DoubleEndedIterator<Item = usize> where Self: 'a

Traverse all nodes in the graph, note that this traversal is neither BFS nor DFS, but the most friendly traversal to the data structure. See more in Self::all_nodes.

type EdgeTraverser<'a>: DoubleEndedIterator<Item = usize> where Self: 'a

An iterator over the edges.

type BridgeTraverser<'a>: DoubleEndedIterator<Item = IndeterminateEdge> where Self: 'a

An iterator over the edges.

Required Methods

fn graph_kind(&self) -> GraphKind

Check the graph kind, it can be directed or undirected.

Examples

use graph_theory::{graph_engines::CompleteGraph, GraphEngine};
assert_eq!(CompleteGraph::one_way(5).get_node(5), true);
assert_eq!(CompleteGraph::one_way(5).get_node(6), false);

fn get_node(&self, node: usize) -> Result<usize, GraphError>

Check if the node exists, return the node id if exists.

Examples

use graph_theory::{graph_engines::CompleteGraph, GraphEngine};
assert_eq!(CompleteGraph::one_way(5).get_node(5), true);
assert_eq!(CompleteGraph::one_way(5).get_node(6), false);

fn all_nodes<'a>(&'a self) -> Self::NodeTraverser<'a>

Traverse all nodes in the entire graph in the most friendly way to the data structure, and the order of this traversal is arbitrary.

Examples

use graph_theory::{graph_engines::CompleteGraph, GraphEngine};
let mut graph = CompleteGraph::one_way(5);
assert_eq!(graph.all_nodes().count(), 20)

fn all_neighbors<'a>(&'a self, node: usize) -> Self::NeighborIterator<'a>

Given a vertex, return all adjacent nodes.

Return None if the node does not exist.

Examples

use graph_theory::{graph_engines::UnGraphAND, GraphEngine};
let graph = UnGraphAND::default();
assert_eq!(graph.all_neighbors(5).count(), 5);

fn get_edge(&self, edge: usize) -> Result<usize, GraphError>

Check if the edge exists, return the node id if exists.

At most one element will be returned, even if there are multiple edges with the same starting point and ending point.

If you need to return all eligible edges, use Self::get_bridges.

Examples

use graph_theory::{graph_engines::CompleteGraph, GraphEngine};
assert_eq!(CompleteGraph::one_way(5).get_node(5), true);
assert_eq!(CompleteGraph::one_way(5).get_node(6), false);

fn all_edges<'a>(&'a self) -> Self::EdgeTraverser<'a>

Traverse all edges in the entire graph in the most friendly way to the data structure, the order of traversal is arbitrary.

use graph_theory::{graph_engines::CompleteGraph, GraphEngine};
let mut graph = CompleteGraph::one_way(5);
assert_eq!(graph.all_nodes().count(), 20)

fn get_bridge(&self, edge: usize) -> Result<IndeterminateEdge, GraphError>

fn get_bridges<'a>( &'a self, from: usize, goto: usize, ) -> Self::BridgeIterator<'a>

Give all edges matching the start and end points

Examples

use graph_theory::{graph_engines::CompleteGraph, GraphEngine};
assert_eq!(CompleteGraph::one_way(5).get_node(5), true);
assert_eq!(CompleteGraph::one_way(5).get_node(6), false);

fn all_bridges<'a>(&'a self) -> Self::BridgeTraverser<'a>

Get the edges of the graph.

use graph_theory::{graph_engines::CompleteGraph, GraphEngine};
let mut graph = CompleteGraph::one_way(5);
assert_eq!(graph.all_nodes().count(), 20)

Provided Methods

fn count_nodes<'a>(&'a self) -> usize

Count the number of nodes in the graph.

Examples

use graph_theory::{graph_engines::CompleteGraph, GraphEngine};
assert_eq!(CompleteGraph::one_way(5).count_nodes(), 5);

fn all_outgoing<'a>(&'a self, node: usize) -> Self::NeighborIterator<'a>

Given a vertex as the starting point, return the ids corresponding to all ending points.

In an undirected graph, it is equivalent to calling Self::all_neighbors.

Examples

use graph_theory::{graph_engines::UnGraphAND, GraphEngine};
let graph = UnGraphAND::default();
assert_eq!(graph.all_outgoing(5).count(), 5);

fn all_incoming<'a>(&'a self, node: usize) -> Self::NeighborIterator<'a>

Given a vertex as the ending point, return the ids corresponding to all starting points.

In an undirected graph, it is equivalent to calling Self::all_neighbors.

Examples

use graph_theory::{graph_engines::UnGraphAND, GraphEngine};
let graph = UnGraphAND::default();
assert_eq!(graph.all_incoming(5).count(), 5);

fn count_degree<'a>(&'a self, node: usize) -> NodeDegree

Check if the node exists, return the node id if exists.

Return None if the node does not exist.

Examples

use graph_theory::{graph_engines::CompleteGraph, GraphEngine};
assert_eq!(CompleteGraph::one_way(5).count_nodes(), 5);

fn count_edges<'a>(&'a self) -> usize

Count the number of edges in the graph.

Examples

assert_eq!(CycleGraph::one_way(5).count_edges(), 5);
assert_eq!(CycleGraph::two_way(5).count_edges(), 10);
assert_eq!(StarGraph::one_way(5).count_edges(), 5);
assert_eq!(StarGraph::two_way(5).count_edges(), 10);
assert_eq!(CompleteGraph::one_way(5).count_edges(), 5);
assert_eq!(CompleteGraph::one_way(5).count_edges(), 10);

fn size_hint(&self) -> usize

Query the total space occupied by the structure, return 0 if failed to query

Note that this volume contains garbage data, call [GraphEngine::shrink] at the right time to perform garbage collection.

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 GraphEngine for PlaceholderGraph

type NeighborIterator<'a> = PlaceholderNodeIterator<'a>

type BridgeIterator<'a> = PlaceholderEdgeIterator<'a>

type NodeTraverser<'a> = PlaceholderNodeIterator<'a>

type EdgeTraverser<'a> = PlaceholderNodeIterator<'a>

type BridgeTraverser<'a> = PlaceholderEdgeIterator<'a>