Trait ojo_graph::Graph

pub trait Graph {
    type Node: Copy + Eq + Hash;
    type Edge: Copy + Eq + Edge<Self::Node>;
    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>;

    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,
    { ... }
}

Associated Types

type Node: Copy + Eq + Hash

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

Loading content...

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>

Loading content...

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>

Important traits for Dfs<'a, G>

impl<'a, G: Graph + ?Sized> Iterator for Dfs<'a, G> type Item = Visit<G::Node>;

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

Important traits for Dfs<'a, G>

impl<'a, G: Graph + ?Sized> Iterator for Dfs<'a, G> type Item = Visit<G::Node>;

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.

Loading content...

Implementors

impl<'a, G: ?Sized> Graph for Doubled<'a, G> where
    G: Graph, 

type Node = G::Node

type Edge = G::Edge

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

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

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

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>

Important traits for Dfs<'a, G>

impl<'a, G: Graph + ?Sized> Iterator for Dfs<'a, G> type Item = Visit<G::Node>;

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

Important traits for Dfs<'a, G>

impl<'a, G: Graph + ?Sized> Iterator for Dfs<'a, G> type Item = Visit<G::Node>;

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, 

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

type Node = G::Node

type Edge = G::Edge

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

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

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

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>

Important traits for Dfs<'a, G>

impl<'a, G: Graph + ?Sized> Iterator for Dfs<'a, G> type Item = Visit<G::Node>;

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

Important traits for Dfs<'a, G>

impl<'a, G: Graph + ?Sized> Iterator for Dfs<'a, G> type Item = Visit<G::Node>;

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, 

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

type Node = G::Node

type Edge = G::Edge

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

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

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

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>

Important traits for Dfs<'a, G>

impl<'a, G: Graph + ?Sized> Iterator for Dfs<'a, G> type Item = Visit<G::Node>;

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

Important traits for Dfs<'a, G>

impl<'a, G: Graph + ?Sized> Iterator for Dfs<'a, G> type Item = Visit<G::Node>;

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, 

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

type Node = usize

type Edge = usize

fn nodes<'a>(&'a self) -> Box<dyn Iterator<Item = usize>>

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

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

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>

Important traits for Dfs<'a, G>

impl<'a, G: Graph + ?Sized> Iterator for Dfs<'a, G> type Item = Visit<G::Node>;

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

Important traits for Dfs<'a, G>

impl<'a, G: Graph + ?Sized> Iterator for Dfs<'a, G> type Item = Visit<G::Node>;

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, 

Loading content...