Trait Graph

pub trait Graph {
    type Node: Copy + Eq + Hash;
    type Edge: Copy + Eq + Edge<Self::Node>;

    // Required methods
    fn nodes<'a>(&'a self) -> Box<dyn Iterator<Item = Self::Node> + 'a>;
    fn out_edges<'a>(
        &'a self,
        u: &Self::Node,
    ) -> Box<dyn Iterator<Item = Self::Edge> + 'a>;
    fn in_edges<'a>(
        &'a self,
        u: &Self::Node,
    ) -> Box<dyn Iterator<Item = Self::Edge> + 'a>;

    // Provided methods
    fn out_neighbors<'a>(
        &'a self,
        u: &Self::Node,
    ) -> Map<Box<dyn Iterator<Item = Self::Edge> + 'a>, fn(Self::Edge) -> Self::Node> { ... }
    fn in_neighbors<'a>(
        &'a self,
        u: &Self::Node,
    ) -> Map<Box<dyn Iterator<Item = Self::Edge> + 'a>, fn(Self::Edge) -> Self::Node> { ... }
    fn dfs<'a>(&'a self) -> Dfs<'a, Self>  { ... }
    fn dfs_from<'a>(&'a self, root: &Self::Node) -> Dfs<'a, Self>  { ... }
    fn has_path(&self, u: &Self::Node, v: &Self::Node) -> bool { ... }
    fn tarjan(&self) -> Partition<Self> { ... }
    fn weak_components(&self) -> Partition<Self> { ... }
    fn doubled<'a>(&'a self) -> Doubled<'a, Self> { ... }
    fn node_filtered<'a, F>(&'a self, predicate: F) -> NodeFiltered<'a, Self, F>
       where F: Fn(&Self::Node) -> bool { ... }
    fn edge_filtered<'a, F>(&'a self, predicate: F) -> EdgeFiltered<'a, Self, F>
       where F: Fn(&Self::Node, &Self::Edge) -> bool { ... }
    fn top_sort<'a>(&'a self) -> Option<Vec<Self::Node>> { ... }
    fn linear_order<'a>(&'a self) -> Option<Vec<Self::Node>> { ... }
    fn neighbor_set<'a, I: Iterator<Item = &'a Self::Node>>(
        &self,
        set: I,
    ) -> HashSet<Self::Node>
       where Self::Node: 'a { ... }
}

Required Associated Types

type Node: Copy + Eq + Hash

type Edge: Copy + Eq + Edge<Self::Node>

Required Methods

fn nodes<'a>(&'a self) -> Box<dyn Iterator<Item = Self::Node> + 'a>

fn out_edges<'a>( &'a self, u: &Self::Node, ) -> Box<dyn Iterator<Item = Self::Edge> + 'a>

fn in_edges<'a>( &'a self, u: &Self::Node, ) -> Box<dyn Iterator<Item = Self::Edge> + 'a>

Provided Methods

fn out_neighbors<'a>( &'a self, u: &Self::Node, ) -> Map<Box<dyn Iterator<Item = Self::Edge> + 'a>, fn(Self::Edge) -> Self::Node>

fn in_neighbors<'a>( &'a self, u: &Self::Node, ) -> Map<Box<dyn Iterator<Item = Self::Edge> + 'a>, fn(Self::Edge) -> Self::Node>

fn dfs<'a>(&'a self) -> Dfs<'a, Self>

fn dfs_from<'a>(&'a self, root: &Self::Node) -> Dfs<'a, Self>

fn has_path(&self, u: &Self::Node, v: &Self::Node) -> bool

fn tarjan(&self) -> Partition<Self>

fn weak_components(&self) -> Partition<Self>

fn doubled<'a>(&'a self) -> Doubled<'a, Self>

Returns the graph that has edges in both directions for every edge that this graph has in one direction.

fn node_filtered<'a, F>(&'a self, predicate: F) -> NodeFiltered<'a, Self, F>

where F: Fn(&Self::Node) -> bool,

Returns the subgraph of this graph that is induced by the set of nodes for which predicate returns true.

fn edge_filtered<'a, F>(&'a self, predicate: F) -> EdgeFiltered<'a, Self, F>

where F: Fn(&Self::Node, &Self::Edge) -> bool,

Returns the subgraph of this graph containing all the edges for which the predicate returns true.

fn top_sort<'a>(&'a self) -> Option<Vec<Self::Node>>

If this graph is acyclic, returns a topological sort of the vertices. Otherwise, returns None.

fn linear_order<'a>(&'a self) -> Option<Vec<Self::Node>>

fn neighbor_set<'a, I: Iterator<Item = &'a Self::Node>>( &self, set: I, ) -> HashSet<Self::Node>

where Self::Node: 'a,

Returns the set of all nodes that are adjacent (either an in-neighbor or an out-neighbor) to something in set.

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<'a, G> Graph for Doubled<'a, G>

where G: Graph + ?Sized,

type Node = <G as Graph>::Node

type Edge = <G as Graph>::Edge

impl<'a, G, F> Graph for EdgeFiltered<'a, G, F>

where G: Graph + ?Sized, F: Fn(&G::Node, &G::Edge) -> bool + 'a,

type Node = <G as Graph>::Node

type Edge = <G as Graph>::Edge

impl<'a, G, F> Graph for NodeFiltered<'a, G, F>

where G: Graph + ?Sized, F: Fn(&G::Node) -> bool + 'a,

type Node = <G as Graph>::Node

type Edge = <G as Graph>::Edge

impl<G: Graph + ?Sized> Graph for Partition<G>

type Node = usize

type Edge = usize