Struct DiGraph

pub struct DiGraph<N, E> { /* private fields */ }

A weighted, directed graph.

See also: Graph.

Example

use rust_dsa::DiGraph;

// First, we create a new graph.
let mut graph = DiGraph::new();

// Then we can add nodes.
graph.insert_node('a');
graph.insert_node('b');
graph.insert_node('c');

assert_eq!(graph.len(), 3);
assert!(graph.contains_node(&'a'));
assert!(graph.contains_node(&'b'));
assert!(graph.contains_node(&'c'));

// And edges between those nodes.
graph.insert_edge(&'a', &'b', 5);
graph.insert_edge(&'a', &'c', 1);
graph.insert_edge(&'c', &'b', 4);

assert_eq!(graph.get_edge(&'a', &'b'), Some(&5));
assert_eq!(graph.get_edge(&'a', &'c'), Some(&1));
assert_eq!(graph.get_edge(&'c', &'b'), Some(&4));

// Edges and nodes can be inserted together.
graph.insert_edge_by_value('a', 'z', -1);

// Edges can be removed.
graph.remove_edge(&'a', &'z');

assert!(!graph.contains_edge(&'a', &'z'));

// Nodes too.
graph.remove_node(&'z');

assert!(!graph.contains_node(&'z'));

// We can iterate over a node's neighbors.
for (neighbor, weight) in graph.neighbors_of(&'a') {
    // Prints "b (5)" and "c (1)" in an arbitrary order.
    println!("{neighbor} ({weight})");
}

// We can also iterate over all edges in the graph.
for (from, to, weight) in graph.edges() {
    // Prints "a -> b (5)", "a -> c (1)" and "c -> b (4)"
    // in an arbitrary order.
    println!("{from} -> {to} ({weight})");
}

// And iterate over all nodes
for node in graph {
    // Prints "a", "b" and "c" in an arbitrary order.
    println!("{node}");
}

Implementations

impl<N, E> DiGraph<N, E>

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

Creates an empty graph.

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

where N: Hash + Eq,

Inserts a node into the graph.

Example

use rust_dsa::DiGraph;

let mut graph: DiGraph<_, ()> = DiGraph::new();
graph.insert_node(1);

assert!(graph.contains_node(&1));

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

where N: Hash + Eq,

Inserts an edge into the graph.

Returns the old weight if the graph already contained the edge.

Panics

Panics if from or to is not in the graph.

Example

use rust_dsa::DiGraph;

let mut graph: DiGraph<_, _> = [true, false].into_iter().collect();
graph.insert_edge(&true, &false, 1);

assert!(graph.contains_edge(&true, &false));

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

where N: Hash + Eq,

Inserts an edge into the graph. The nodes are inserted if they are not already present in the graph.

Returns the old weight if the graph already contained the edge.

Example

use rust_dsa::DiGraph;

let mut graph = DiGraph::new();

graph.insert_edge_by_value('a', 'b', 1);

assert_eq!(graph.get_edge(&'a', &'b'), Some(&1));
assert!(graph.contains_node(&'a'));
assert!(graph.contains_node(&'b'));

pub fn remove_node(&mut self, node: &N) -> bool

where N: Hash + Eq,

Removes a node from the graph. Returns true if the node was present in the graph.

Example

use rust_dsa::DiGraph;

let foo = "foo".to_string();
let bar = "bar".to_string();

let mut graph = DiGraph::from([(foo.clone(), bar, 2)]);

assert!(graph.contains_node(&foo));

graph.remove_node(&foo);

assert!(!graph.contains_node(&foo));

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

where N: Hash + Eq,

Removes an edge from the graph. Returns the weight if the edge was present in the graph.

Example

use rust_dsa::DiGraph;

let mut graph = DiGraph::from([(1, 2, true), (1, 3, false)]);

assert!(graph.contains_edge(&1, &2));

assert_eq!(graph.remove_edge(&1, &2), Some(true));

assert!(!graph.contains_edge(&1, &2));

assert_eq!(graph.remove_edge(&1, &2), None);

pub fn contains_node(&self, node: &N) -> bool

where N: Hash + Eq,

Returns true if the graph contains node.

Example

use rust_dsa::DiGraph;

let mut graph: DiGraph<_, f64> = DiGraph::new();

graph.insert_node(1);

assert!(graph.contains_node(&1));
assert!(!graph.contains_node(&2));

pub fn contains_edge(&self, from: &N, to: &N) -> bool

where N: Hash + Eq,

Returns true if the graph contains an edge between from and to.

Example

use rust_dsa::DiGraph;

let graph = DiGraph::from([
    ('a', 'b', 1),
    ('b', 'c', 2),
    ('b', 'd', 3),
]);

assert!(graph.contains_edge(&'b', &'c'));
assert!(!graph.contains_edge(&'c', &'d'));

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

where N: Hash + Eq,

Returns a reference to the edge’s weight if the graph contains an edge between from and to.

Example

use rust_dsa::DiGraph;

let graph = DiGraph::from([
    ('a', 'b', 1),
    ('b', 'c', 2),
    ('b', 'd', 3),
]);

assert_eq!(graph.get_edge(&'b', &'c'), Some(&2));
assert_eq!(graph.get_edge(&'c', &'d'), None);

pub fn len(&self) -> usize

Returns the number of nodes in the graph.

Example

use rust_dsa::DiGraph;

let graph: DiGraph<_, ()> = (0..42).collect();

assert_eq!(graph.len(), 42);

pub fn is_empty(&self) -> bool

Returns true if the graph is empty.

Example

use rust_dsa::DiGraph;

let mut graph: DiGraph<_, bool> = "abc".chars().collect();

assert!(!graph.is_empty());

graph.clear();

assert!(graph.is_empty());

pub fn clear(&mut self)

Clears the graph.

Example

use rust_dsa::DiGraph;

let mut graph: DiGraph<_, u8> = "abc".chars().collect();

assert!(!graph.is_empty());

graph.clear();

assert!(graph.is_empty());

pub fn neighbors_of(&self, node: &N) -> Neighbors<'_, N, E>

where N: Hash + Eq,

Returns an iterator that visits all of node’s neighbors.

Panics

Panics if node is not present in the graph.

Example

use rust_dsa::DiGraph;
use std::collections::HashSet;

let graph = DiGraph::from([
    (1, 2, 'a'),
    (1, 3, 'b'),
    (1, 4, 'c'),
    (4, 3, 'd'),
    (3, 2, 'a'),
]);

let neighbors: HashSet<_> = graph.neighbors_of(&1).collect();

assert_eq!(
    HashSet::from([(&2, &'a'), (&3, &'b'), (&4, &'c')]),
    neighbors,
);

pub fn count_neighbors_of(&self, node: &N) -> usize

where N: Hash + Eq,

Returns the number of neighbors node has.

Panics

Panics if node is not present in the graph.

Example

use rust_dsa::DiGraph;

let graph = DiGraph::from([
    (1, 2, 'a'),
    (1, 3, 'b'),
    (1, 4, 'c'),
    (4, 3, 'd'),
    (3, 2, 'a'),
]);

assert_eq!(graph.count_neighbors_of(&1), 3);

pub fn edges(&self) -> Edges<'_, N, E>

Returns an iterator visiting the graph’s edges in an arbitrary order.

Example

use rust_dsa::DiGraph;

let mut graph = DiGraph::new();
graph.insert_edge_by_value(1, 3, 'a');
graph.insert_edge_by_value(3, 2, 'b');

for (from, to, weight) in graph.edges() {
    // Prints "1 -> 3 (a)" and "3 -> 2 (b)" in an arbitrary order
    println!("{from} -> {to} ({weight})");
}

pub fn count_edges(&self) -> usize

Returns the number of edges in the graph.

Example

use rust_dsa::DiGraph;

let graph = DiGraph::from([(1, 2, ()), (2, 3, ()), (2, 1, ())]);

assert_eq!(graph.count_edges(), 3);

pub fn iter(&self) -> Iter<'_, N>

Returns an iterator over the nodes in the graph.

Trait Implementations

impl<N, E> Clone for DiGraph<N, E>

where N: Clone + Hash + Eq, E: Clone,

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<N, E> Default for DiGraph<N, E>

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

Returns the “default value” for a type.

impl<N, E, const M: usize> From<[(N, N, E); M]> for DiGraph<N, E>

where N: Hash + Eq,

fn from(edges: [(N, N, E); M]) -> DiGraph<N, E>

Creates a graph from an edge list.

impl<N, E> FromIterator<N> for DiGraph<N, E>

where N: Hash + Eq,

fn from_iter<I: IntoIterator<Item = N>>(iter: I) -> DiGraph<N, E>

Creates a graph with the elements of the iterator. The graph does not contain any edges.

impl<'a, N, E> IntoIterator for &'a DiGraph<N, E>

fn into_iter(self) -> Self::IntoIter

Creates an iterator over the nodes in the graph.

type IntoIter = Iter<'a, N>

Which kind of iterator are we turning this into?

type Item = &'a N

The type of the elements being iterated over.

impl<N, E> IntoIterator for DiGraph<N, E>

fn into_iter(self) -> Self::IntoIter

Creates an iterator over the nodes in the graph.

type IntoIter = IntoIter<N>

Which kind of iterator are we turning this into?

type Item = N

The type of the elements being iterated over.

impl<N, E> PartialEq for DiGraph<N, E>

where N: Eq + Hash, E: PartialEq,

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

Returns true if the two graphs are equal.

Example

use rust_dsa::DiGraph;

let graph: DiGraph<_, _> = [1, 2, 3].into_iter().collect();

let mut a = graph.clone();
a.insert_edge(&1, &2, 'a');
a.insert_edge(&3, &2, 'b');
a.insert_edge(&2, &1, 'c');
a.remove_edge(&1, &2);

let mut b = graph.clone();
b.insert_edge(&3, &2, 'b');
b.insert_edge(&2, &1, 'c');

assert!(a == b);

let mut c = graph.clone();
c.insert_edge(&1, &2, 'a');
c.insert_edge(&3, &2, 'b');
c.insert_edge(&2, &1, 'c');

assert!(a != c);
assert!(b != c);

let mut d = graph.clone();
d.insert_edge(&1, &2, 'a');
d.insert_edge(&3, &2, 'b');
d.insert_edge(&2, &1, 'z');

assert!(c != d);

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, E> Eq for DiGraph<N, E>

where N: Eq + Hash, E: Eq,