yagraphc::graph::traits

Trait Traversable

Source 
pub trait Traversable<T, W>
where
    T: Clone + Copy + Eq + Hash + PartialEq,
    W: Clone + Copy,
{
    // Required methods
    fn edges(&self, n: &T) -> EdgeIterType<'_, T, W> ⓘ;
    fn edge_weight(&self, from: T, to: T) -> Result<W, NodeNotFound>;
    fn in_edges(&self, n: &T) -> EdgeIterType<'_, T, W> ⓘ;
    fn nodes(&self) -> NodeIter<'_, T> ⓘ;

    // Provided methods
    fn bfs(&self, from: T) -> BfsIter<'_, T, W> ⓘ
       where Self: Sized { ... }
    fn dfs(&self, from: T) -> DfsIter<'_, T, W> ⓘ
       where Self: Sized { ... }
    fn dfs_post_order(&self, from: T) -> PostOrderDfsIter<T> ⓘ
       where Self: Sized { ... }
    fn find_path(&self, from: T, to: T) -> Option<Vec<T>>
       where Self: Sized { ... }
    fn find_path_filter_edges<G>(
        &self,
        from: T,
        to: T,
        predicate: G,
    ) -> Option<Vec<T>>
       where Self: Sized,
             G: Fn(T, T) -> bool { ... }
    fn connected_components(&self) -> Vec<Vec<T>>
       where Self: Sized { ... }
}

Required Methods§

Source

fn edges(&self, n: &T) -> EdgeIterType<'_, T, W> ⓘ

Iterates over edges of the node as the target nodes and the edge weight.

If the graph is undirected, should return the nodes that are connected to it by an edge.

If the graph is directed, should return the outbound nodes.

§Examples
use yagraphc::graph::{UnGraph, DiGraph};
use yagraphc::graph::traits::{GraphBuilding, Traversable};

let mut graph = UnGraph::default();

graph.add_edge(1, 2, ());
graph.add_edge(2, 3, ());

let edges = graph.edges(&2);

assert_eq!(edges.count(), 2);

let mut graph = DiGraph::default();

graph.add_edge(1, 2, ());
graph.add_edge(2, 3, ());

let edges = graph.edges(&2);

assert_eq!(edges.count(), 1);
Source

fn edge_weight(&self, from: T, to: T) -> Result<W, NodeNotFound>

Source

fn in_edges(&self, n: &T) -> EdgeIterType<'_, T, W> ⓘ

Iterates over inbound-edges of the node as the target nodes and the edge weight.

If the graph is undirected, should return the nodes that are connected to it by an edge. Thus, it is equivalent to edges in that case.

If the graph is directed, should return the inbound nodes.

§Examples
use yagraphc::graph::{UnGraph, DiGraph};
use yagraphc::graph::traits::{GraphBuilding, Traversable};

let mut graph = UnGraph::default();

graph.add_edge(1, 2, ());
graph.add_edge(2, 3, ());
graph.add_edge(4, 2, ());

let edges = graph.in_edges(&2);

assert_eq!(edges.count(), 3);

let mut graph = DiGraph::default();

graph.add_edge(1, 2, ());
graph.add_edge(2, 3, ());
graph.add_edge(4, 2, ());

let edges = graph.in_edges(&2);

assert_eq!(edges.count(), 2);
Source

fn nodes(&self) -> NodeIter<'_, T> ⓘ

Returns an iterator over all nodes.

§Examples
use yagraphc::graph::UnGraph;
use yagraphc::graph::traits::{GraphBuilding, Traversable};

let mut graph = UnGraph::default();

graph.add_edge(1, 2, ());
graph.add_edge(2, 3, ());

graph.add_node(4);

assert_eq!(graph.nodes().count(), 4);

graph.add_node(2);
assert_eq!(graph.nodes().count(), 4);

Provided Methods§

Source

fn bfs(&self, from: T) -> BfsIter<'_, T, W> ⓘ
where Self: Sized,

Returns an iterator of nodes in breadth-first order.

Iterator includes the depth at which the nodes were found. Nodes at the same depth might be randomly shuffled.

§Examples
use yagraphc::graph::UnGraph;
use yagraphc::graph::traits::{GraphBuilding, Traversable};

let mut graph = UnGraph::new();

graph.add_edge(1, 2, ());
graph.add_edge(1, 3, ());
graph.add_edge(2, 4, ());
graph.add_edge(2, 5, ());

let bfs = graph.bfs(1);

let depths = bfs.map(|(_, depth)| depth).collect::<Vec<_>>();

assert_eq!(depths, vec![0, 1, 1, 2, 2]);
Source

fn dfs(&self, from: T) -> DfsIter<'_, T, W> ⓘ
where Self: Sized,

Returns an iterator of nodes in depth-first order, in pre-order.

Iterator includes the depth at which the nodes were found. Order is not deterministic.

§Examples
use yagraphc::graph::UnGraph;
use yagraphc::graph::traits::{GraphBuilding, Traversable};

let mut graph = UnGraph::new();

graph.add_edge(1, 2, ());
graph.add_edge(2, 3, ());
graph.add_edge(3, 4, ());
graph.add_edge(1, 5, ());
graph.add_edge(5, 6, ());

let dfs = graph.dfs(1);

let depths = dfs.map(|(node, _)| node).collect::<Vec<_>>();

assert!(matches!(depths[..], [1, 2, 3, 4, 5, 6] | [1, 5, 6, 2, 3, 4]));
Source

fn dfs_post_order(&self, from: T) -> PostOrderDfsIter<T> ⓘ
where Self: Sized,

Returns an iterator of nodes in depth-first order, in post-order.

Iterator includes the depth at which the nodes were found. Order is not deterministic.

Currently implemented recursively. To be changed to a non-recursive implemented at some point.

§Examples
use yagraphc::graph::UnGraph;
use yagraphc::graph::traits::{GraphBuilding, Traversable};

let mut graph = UnGraph::new();

graph.add_edge(1, 2, ());
graph.add_edge(2, 3, ());
graph.add_edge(3, 4, ());
graph.add_edge(1, 5, ());
graph.add_edge(5, 6, ());

let dfs = graph.dfs_post_order(1);

let depths = dfs.map(|(node, _)| node).collect::<Vec<_>>();

assert!(matches!(depths[..], [6, 5, 4, 3, 2, 1] | [4, 3, 2, 6, 5, 1]));
Source

fn find_path(&self, from: T, to: T) -> Option<Vec<T>>
where Self: Sized,

Finds path from from to to using BFS.

Returns None if there is no path.

§Examples
use yagraphc::graph::UnGraph;
use yagraphc::graph::traits::{GraphBuilding, Traversable};

let mut graph = UnGraph::new();

graph.add_edge(1, 2, ());
graph.add_edge(2, 3, ());
graph.add_edge(3, 4, ());
graph.add_edge(1, 5, ());
graph.add_edge(5, 6, ());

let path = graph.find_path(1, 4);

assert_eq!(path, Some(vec![1, 2, 3, 4]));
Source

fn find_path_filter_edges<G>( &self, from: T, to: T, predicate: G, ) -> Option<Vec<T>>
where Self: Sized, G: Fn(T, T) -> bool,

Finds path from from to to using BFS while filtering edges.

Returns None if there is no path.

For an undirected graph, strive to make predicate(x,y) == predicate(y,x). As of now, the order is related to the exploration direction of bfs, but it is advisable not to rely on direction concepts on undirected graphs.

§Examples
use yagraphc::graph::UnGraph;
use yagraphc::graph::traits::{GraphBuilding, Traversable};
let mut graph = UnGraph::default();
graph.add_edge(1, 2, ());
graph.add_edge(2, 3, ());
graph.add_edge(3, 4, ());
graph.add_edge(4, 5, ());
graph.add_edge(1, 7, ());
graph.add_edge(7, 5, ());
let path = graph.find_path(1, 5).unwrap();
assert_eq!(path, vec![1, 7, 5]);
let path = graph
    .find_path_filter_edges(1, 5, |x, y| (x, y) != (1, 7))
    .unwrap();
assert_eq!(path, vec![1, 2, 3, 4, 5]);
Source

fn connected_components(&self) -> Vec<Vec<T>>
where Self: Sized,

Returns a list of connected components of the graph.

If being used in a directed graph, those are the strongly connected components, computed using Kosaraju’s algorithm.

§Examples
use yagraphc::graph::{UnGraph, DiGraph};
use yagraphc::graph::traits::{GraphBuilding, Traversable};

let mut graph = UnGraph::new();

graph.add_edge(1, 2, ());
graph.add_edge(2, 3, ());

graph.add_edge(4, 5, ());
graph.add_edge(5, 6, ());
graph.add_edge(6, 4, ());

let components = graph.connected_components();

assert_eq!(components.len(), 2);

let mut graph = DiGraph::new();

graph.add_edge(1, 2, ());
graph.add_edge(2, 3, ());

graph.add_edge(4, 5, ());
graph.add_edge(5, 6, ());
graph.add_edge(6, 4, ());

let components = graph.connected_components();

assert_eq!(components.len(), 4);

Implementors§

Source§

impl<T, W> Traversable<T, W> for DiGraph<T, W>
where T: Clone + Copy + Eq + Hash + PartialEq, W: Clone + Copy,

Source§

impl<T, W> Traversable<T, W> for DiGraphVecEdges<T, W>
where T: Clone + Copy + Eq + Hash + PartialEq, W: Clone + Copy,

Source§

impl<T, W> Traversable<T, W> for UnGraph<T, W>
where T: Clone + Copy + Hash + Eq + PartialEq, W: Clone + Copy,

Source§

impl<T, W> Traversable<T, W> for UnGraphVecEdges<T, W>
where T: Clone + Copy + Hash + Eq + PartialEq, W: Clone + Copy,