Struct Graph

pub struct Graph<N: Clone, E: Clone> {
    nodes: OrdMap<N, OrdMap<N, E>>,
}

Fields

nodes: OrdMap<N, OrdMap<N, E>>

Implementations

impl<N: Eq + Ord + Clone, E: Default + Clone> Graph<N, E>

pub fn new() -> Graph<N, E>

pub fn add(&mut self, node: N)

pub fn link(&mut self, node: N, child: N) -> &mut E

pub fn reversed(&self) -> Graph<N, E>

Returns the graph obtained by reversing all edges.

pub fn contains<Q>(&self, k: &Q) -> bool

where N: Borrow<Q>, Q: Ord + Eq + ?Sized,

pub fn edge(&self, from: &N, to: &N) -> Option<&E>

pub fn edges(&self, from: &N) -> impl Iterator<Item = (&N, &E)>

pub fn sort(&self) -> Vec<N>

A topological sort of the Graph

fn sort_inner_visit(&self, node: &N, dst: &mut Vec<N>, marks: &mut BTreeSet<N>)

pub fn iter(&self) -> impl Iterator<Item = &N>

pub fn len(&self) -> usize

pub fn is_path_from_to<'a>(&'a self, from: &'a N, to: &'a N) -> bool

Checks if there is a path from from to to.

pub fn path_to_bottom<'a>(&'a self, pkg: &'a N) -> Vec<(&'a N, Option<&'a E>)>

Resolves one of the paths from the given dependent package down to a leaf.

The path return will be the shortest path, or more accurately one of the paths with the shortest length.

Each element contains a node along with an edge except the first one. The representation would look like:

(Node0,) -> (Node1, Edge01) -> (Node2, Edge12)…

pub fn path_to_top<'a>(&'a self, pkg: &'a N) -> Vec<(&'a N, Option<&'a E>)>

Resolves one of the paths from the given dependent package up to the root.

The path return will be the shortest path, or more accurately one of the paths with the shortest length.

Each element contains a node along with an edge except the first one. The representation would look like:

(Node0,) -> (Node1, Edge01) -> (Node2, Edge12)…

impl<'s, N: Eq + Ord + Clone + 's, E: Default + Clone + 's> Graph<N, E>

fn path_to<'a, F, I>( &'s self, pkg: &'a N, fn_edge: F, ) -> Vec<(&'a N, Option<&'a E>)>

where I: Iterator<Item = (&'a N, &'a E)>, F: Fn(&'s Self, &'a N) -> I, 'a: 's,

impl<N: Eq + Ord + Clone, E: Clone> Graph<N, E>

fn print_for_test(&self)

Prints the graph for constructing unit tests.

For purposes of graph traversal algorithms the edge values do not matter, and the only value of the node we care about is the order it gets compared in. This constructs a graph with the same topology but with integer keys and unit edges.

Trait Implementations

impl<N: Eq + Ord + Clone, E: Clone> Clone for Graph<N, E>

fn clone(&self) -> Graph<N, E>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<N: Display + Eq + Ord + Clone, E: Clone> Debug for Graph<N, E>

fn fmt(&self, fmt: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<N: Eq + Ord + Clone, E: Default + Clone> Default for Graph<N, E>

fn default() -> Graph<N, E>

Returns the “default value” for a type.

impl<N: Eq + Ord + Clone, E: Eq + Clone> PartialEq for Graph<N, E>

fn eq(&self, other: &Graph<N, E>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<N: Eq + Ord + Clone, E: Eq + Clone> Eq for Graph<N, E>

Layout

Note: Most layout information is completely unstable and may even differ between compilations. The only exception is types with certain repr(...) attributes. Please see the Rust Reference's “Type Layout” chapter for details on type layout guarantees.

Size: 16 bytes