Struct Graph

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

A weighted graph.

See also: DiGraph.

Example

use rust_dsa::Graph;

// First, we create a new graph.
let mut graph = Graph::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 at the same time.
graph.insert_edge_by_value('a', 'z', -1);

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

// 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)" or "b -> a (5)", "a -> c (1)" or "c -> a (1)"
    // and "c -> b (4)" or "b -> c (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> Graph<N, E>

pub fn new() -> Graph<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::Graph;

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

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

pub fn insert_edge(&mut self, u: &N, v: &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 u or v is not in the graph.

Example

use rust_dsa::Graph;

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

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

pub fn insert_edge_by_value(&mut self, u: N, v: 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::Graph;

let mut graph = Graph::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::Graph;

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

let mut graph: Graph<_, i32> = Graph::new();
graph.insert_node(foo.clone());
graph.insert_node(bar);

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

graph.remove_node(&foo);

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

pub fn remove_edge(&mut self, u: &N, v: &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::Graph;

let mut graph = Graph::from([(1, 2, 'a'), (1, 3, 'b')]);

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

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

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::Graph;

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

graph.insert_node(1);

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

pub fn contains_edge(&self, u: &N, v: &N) -> bool

where N: Hash + Eq,

Returns true if the graph contains an edge between u and v.

Example

use rust_dsa::Graph;

let graph = Graph::from([
    ('a', 'b', true),
    ('b', 'c', true),
    ('b', 'd', true),
]);

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

pub fn get_edge(&self, u: &N, v: &N) -> Option<&E>

where N: Hash + Eq,

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

Example

use rust_dsa::Graph;

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

assert_eq!(graph.get_edge(&'c', &'b'), 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::Graph;

let graph: Graph<_, u8> = (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::Graph;

let mut graph: Graph<_, i32> = "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::Graph;

let mut graph: Graph<_, i32> = "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::Graph;
use std::collections::HashSet;

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

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::Graph;

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

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

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

where N: Hash + Eq,

Returns an interator visiting each of the graph’s edges in an arbitrary order.

The direction of the edge is also arbitrary.

Example

use rust_dsa::Graph;

let mut graph = Graph::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)" or "3 -> 1 (a)" and "3 -> 2 (b)" or "2 -> 3 (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::Graph;

let mut graph = Graph::from([
    (1, 2, ()),
    (2, 3, ()),
    (2, 1, ()),
    (3, 4, ())
]);
graph.remove_edge(&3, &4);

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

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

Returns an iterator over the nodes in the graph.

Trait Implementations

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

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

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, E> Default for Graph<N, E>

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

Returns the “default value” for a type.

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

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

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

Creates a graph from an edge list.

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

where N: Clone + Hash + Eq,

fn from_iter<I: IntoIterator<Item = N>>(iter: I) -> Graph<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 Graph<N, E>

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.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

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

type IntoIter = IntoIter<N>

Which kind of iterator are we turning this into?

type Item = N

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

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

where N: Hash + Eq, E: PartialEq,

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

Returns true if the two graphs are equal.

Example

use rust_dsa::Graph;

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

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

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

assert!(a == b);

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

assert!(a != c);

c.remove_node(&4);

assert!(a == c);

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 Graph<N, E>

where N: Eq + Hash, E: Eq,