Struct graphlib::Graph

pub struct Graph<T> { /* fields omitted */ }

Graph data-structure

Methods

impl<T> Graph<T>

pub fn new() -> Graph<T>

Creates a new graph.

Example

use graphlib::Graph;

let mut graph: Graph<usize> = Graph::new();

graph.add_vertex(0);
assert_eq!(graph.vertex_count(), 1);

pub fn with_capacity(capacity: usize) -> Graph<T>

Creates a new graph with the given capacity.

Example

use graphlib::Graph;

let mut graph: Graph<usize> = Graph::with_capacity(5);

pub fn capacity(&self) -> usize

Returns the current capacity of the graph.

Example

use graphlib::Graph;

let mut graph: Graph<usize> = Graph::with_capacity(5);

assert_eq!(graph.capacity(), 5);

pub fn reserve(&mut self, additional: usize)

Reserves capacity for at least additional more elements to be inserted in the given graph. After calling reserve, capacity will be greater than or equal to self.vertex_count() + additional.

Example

use graphlib::Graph;

let mut graph: Graph<usize> = Graph::with_capacity(3);

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

graph.add_vertex(0);
graph.add_vertex(1);
graph.add_vertex(2);

graph.reserve(10);
assert!(graph.capacity() >= 13);

pub fn shrink_to_fit(&mut self)

Shrinks the capacity of the graph as much as possible.

It will drop down as close as possible to the length but the allocator may still inform the vector that there is space for a few more elements.

Example

use graphlib::Graph;

let mut graph: Graph<usize> = Graph::with_capacity(5);

assert_eq!(graph.capacity(), 5);

graph.shrink_to_fit();
assert_eq!(graph.capacity(), 0);

pub fn add_vertex(&mut self, item: T) -> VertexId

Adds a new vertex to the graph and returns the id of the added vertex.

Example

use graphlib::Graph;

let mut graph: Graph<usize> = Graph::new();
let id = graph.add_vertex(1);

assert_eq!(graph.fetch(&id).unwrap(), &1);

pub fn add_edge(&mut self, a: &VertexId, b: &VertexId) -> Result<(), GraphErr>

Attempts to place a new edge in the graph.

Example

use graphlib::{Graph, GraphErr, VertexId};

let mut graph: Graph<usize> = Graph::new();

// Id of vertex that is not place in the graph
let id = VertexId::random();

let v1 = graph.add_vertex(1);
let v2 = graph.add_vertex(2);

// Adding an edge is idempotent
graph.add_edge(&v1, &v2);
graph.add_edge(&v1, &v2);
graph.add_edge(&v1, &v2);

// Fails on adding an edge between an
// existing vertex and a non-existing one.
assert_eq!(graph.add_edge(&v1, &id), Err(GraphErr::NoSuchVertex));

pub fn add_edge_with_weight(
    &mut self,
    a: &VertexId,
    b: &VertexId,
    weight: f32
) -> Result<(), GraphErr>

Attempts to place a new edge in the graph.

Example

use graphlib::{Graph, GraphErr, VertexId};

let mut graph: Graph<usize> = Graph::new();

// Id of vertex that is not place in the graph
let id = VertexId::random();

let v1 = graph.add_vertex(1);
let v2 = graph.add_vertex(2);

// Adding an edge is idempotent
graph.add_edge_with_weight(&v1, &v2, 0.3);

// Fails on adding an edge between an
// existing vertex and a non-existing one.
assert_eq!(graph.weight(&v1, &v2), Some(0.3));

pub fn weight(&self, a: &VertexId, b: &VertexId) -> Option<f32>

Returns the weight of the specified edge if it is listed.

use graphlib::{Graph, GraphErr, VertexId};

let mut graph: Graph<usize> = Graph::new();

// Id of vertex that is not place in the graph
let id = VertexId::random();

let v1 = graph.add_vertex(1);
let v2 = graph.add_vertex(2);
let v3 = graph.add_vertex(3);

// Adding an edge is idempotent
graph.add_edge_with_weight(&v1, &v2, 0.54543);

assert_eq!(graph.weight(&v1, &v2), Some(0.54543));
assert_eq!(graph.weight(&v1, &v3), None);

pub fn set_weight(
    &mut self,
    a: &VertexId,
    b: &VertexId,
    new_weight: f32
) -> Result<(), GraphErr>

Sets the weight of the edge to the new value if the edge exists in the graph. Note that the given weight must be a number between (and including) -1.0 and 1.0.

use graphlib::{Graph, GraphErr, VertexId};

let mut graph: Graph<usize> = Graph::new();

// Id of vertex that is not place in the graph
let id = VertexId::random();

let v1 = graph.add_vertex(1);
let v2 = graph.add_vertex(2);
let v3 = graph.add_vertex(3);

graph.add_edge_with_weight(&v1, &v2, 0.54543);
assert_eq!(graph.weight(&v1, &v2), Some(0.54543));
 
// Set new weight
graph.set_weight(&v1, &v2, 0.123).unwrap();
assert_eq!(graph.weight(&v1, &v2), Some(0.123));

pub fn has_edge(&self, a: &VertexId, b: &VertexId) -> bool

Checks whether or not exists an edge between the vertices with the given ids.

Example

use graphlib::Graph;

let mut graph: Graph<usize> = Graph::new();

let v1 = graph.add_vertex(1);
let v2 = graph.add_vertex(2);
let v3 = graph.add_vertex(3);

graph.add_edge(&v1, &v2).unwrap();

assert!(graph.has_edge(&v1, &v2));
assert!(!graph.has_edge(&v2, &v3));

pub fn edge_count(&self) -> usize

Returns the total number of edges that are listed in the graph.

Example

use graphlib::Graph;

let mut graph: Graph<usize> = Graph::new();

let v1 = graph.add_vertex(0);
let v2 = graph.add_vertex(1);
let v3 = graph.add_vertex(2);
let v4 = graph.add_vertex(3);

graph.add_edge(&v1, &v2).unwrap();
graph.add_edge(&v2, &v3).unwrap();
graph.add_edge(&v3, &v4).unwrap();

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

pub fn vertex_count(&self) -> usize

Returns the number of vertices that are placed in the graph.

Example

use graphlib::Graph;

let mut graph: Graph<usize> = Graph::new();

graph.add_vertex(1);
graph.add_vertex(2);
graph.add_vertex(3);

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

pub fn fetch(&self, id: &VertexId) -> Option<&T>

Attempts to fetch a reference to an item placed in the graph using the provided VertexId.

Example

use graphlib::Graph;

let mut graph: Graph<usize> = Graph::new();
let id = graph.add_vertex(1);

assert_eq!(*graph.fetch(&id).unwrap(), 1);

pub fn fetch_mut(&mut self, id: &VertexId) -> Option<&mut T>

Attempts to fetch a mutable reference to an item placed in the graph using the provided VertexId.

Example

use graphlib::Graph;

let mut graph: Graph<usize> = Graph::new();
let id = graph.add_vertex(1);

assert_eq!(*graph.fetch(&id).unwrap(), 1);

// Fetch a mutable reference
let v = graph.fetch_mut(&id).unwrap();

// Mutate vertex value
*v = 2;

assert_eq!(*graph.fetch(&id).unwrap(), 2);

pub fn remove(&mut self, id: &VertexId)

Removes a vertex that matches the given VertexId.

Example

use graphlib::Graph;

let mut graph: Graph<usize> = Graph::new();

let v1 = graph.add_vertex(1);
let v2 = graph.add_vertex(2);
let v3 = graph.add_vertex(3);

// The remove operation is idempotent
graph.remove(&v2);
graph.remove(&v2);
graph.remove(&v2);

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

pub fn remove_edge(&mut self, a: &VertexId, b: &VertexId)

Removes the specified edge from the graph.

Example

use graphlib::Graph;

let mut graph: Graph<usize> = Graph::new();

let v1 = graph.add_vertex(0);
let v2 = graph.add_vertex(1);
let v3 = graph.add_vertex(2);
let v4 = graph.add_vertex(3);

graph.add_edge(&v1, &v2).unwrap();
graph.add_edge(&v2, &v3).unwrap();
graph.add_edge(&v3, &v4).unwrap();

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

// The remove edge operation is idempotent
graph.remove_edge(&v2, &v3);
graph.remove_edge(&v2, &v3);
graph.remove_edge(&v2, &v3);

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

pub fn retain(&mut self, fun: impl Fn(&T) -> bool)

Iterates through the graph and only keeps vertices that match the given condition.

Example

use graphlib::Graph;

let mut graph: Graph<usize> = Graph::new();

graph.add_vertex(1);
graph.add_vertex(2);
graph.add_vertex(2);
graph.add_vertex(2);
graph.add_vertex(3);

graph.retain(|v| *v != 2);

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

pub fn fold<A>(&self, initial: A, fun: impl Fn(&T, A) -> A) -> A

Performs a fold over the vertices that are situated in the graph in Depth-First Order.

Example

use graphlib::Graph;

let mut graph: Graph<usize> = Graph::new();

graph.add_vertex(1);
graph.add_vertex(2);
graph.add_vertex(3);

let result = graph.fold(0, |v, acc| v + acc);

assert_eq!(result, 6);

pub fn is_cyclic(&self) -> bool

Returns true if the graph has cycles.

use graphlib::Graph;

let mut graph: Graph<usize> = Graph::new();

let v1 = graph.add_vertex(0);
let v2 = graph.add_vertex(1);
let v3 = graph.add_vertex(2);
let v4 = graph.add_vertex(3);

graph.add_edge(&v1, &v2).unwrap();
graph.add_edge(&v2, &v3).unwrap();
graph.add_edge(&v3, &v4).unwrap();

assert!(!graph.is_cyclic());

graph.add_edge(&v3, &v1);

assert!(graph.is_cyclic());

pub fn roots_count(&self) -> usize

Returns the number of root vertices in the graph.

Example

use graphlib::Graph;

let mut graph: Graph<usize> = Graph::new();

let v1 = graph.add_vertex(0);
let v2 = graph.add_vertex(1);
let v3 = graph.add_vertex(2);
let v4 = graph.add_vertex(3);

graph.add_edge(&v1, &v2).unwrap();
graph.add_edge(&v3, &v1).unwrap();
graph.add_edge(&v1, &v4).unwrap();

assert_eq!(graph.roots_count(), 1);

pub fn neighbors_count(&self, id: &VertexId) -> usize

Returns the total count of neighboring vertices of the vertex with the given id.

Example

use graphlib::Graph;

let mut graph: Graph<usize> = Graph::new();

let v1 = graph.add_vertex(0);
let v2 = graph.add_vertex(1);
let v3 = graph.add_vertex(2);
let v4 = graph.add_vertex(3);

graph.add_edge(&v1, &v2).unwrap();
graph.add_edge(&v3, &v1).unwrap();
graph.add_edge(&v1, &v4).unwrap();

assert_eq!(graph.neighbors_count(&v1), 3);

pub fn in_neighbors_count(&self, id: &VertexId) -> usize

Returns the total count of inbound neighboring vertices of the vertex with the given id.

Example

use graphlib::Graph;

let mut graph: Graph<usize> = Graph::new();

let v1 = graph.add_vertex(0);
let v2 = graph.add_vertex(1);
let v3 = graph.add_vertex(2);
let v4 = graph.add_vertex(3);

graph.add_edge(&v1, &v2).unwrap();
graph.add_edge(&v3, &v1).unwrap();
graph.add_edge(&v1, &v4).unwrap();

assert_eq!(graph.in_neighbors_count(&v1), 1);

pub fn out_neighbors_count(&self, id: &VertexId) -> usize

Returns the total count of outbound neighboring vertices of the vertex with the given id.

Example

use graphlib::Graph;

let mut graph: Graph<usize> = Graph::new();

let v1 = graph.add_vertex(0);
let v2 = graph.add_vertex(1);
let v3 = graph.add_vertex(2);
let v4 = graph.add_vertex(3);
let v5 = graph.add_vertex(4);

graph.add_edge(&v1, &v2).unwrap();
graph.add_edge(&v3, &v1).unwrap();
graph.add_edge(&v1, &v4).unwrap();
graph.add_edge(&v2, &v5).unwrap();
graph.add_edge(&v2, &v3).unwrap();

assert_eq!(graph.out_neighbors_count(&v1), 2);
assert_eq!(graph.out_neighbors_count(&v2), 2);

Important traits for VertexIter<'a>

impl<'a> Iterator for VertexIter<'a> type Item = &'a VertexId;

pub fn in_neighbors(&self, id: &VertexId) -> VertexIter

Returns an iterator over the inbound neighbors of the vertex with the given id.

Example

use graphlib::Graph;

let mut graph: Graph<usize> = Graph::new();
let mut neighbors = vec![];

let v1 = graph.add_vertex(0);
let v2 = graph.add_vertex(1);
let v3 = graph.add_vertex(2);
let v4 = graph.add_vertex(3);

graph.add_edge(&v1, &v2).unwrap();
graph.add_edge(&v3, &v1).unwrap();
graph.add_edge(&v1, &v4).unwrap();

// Iterate over neighbors
for v in graph.in_neighbors(&v1) {
    neighbors.push(v);
}

assert_eq!(neighbors.len(), 1);
assert_eq!(neighbors[0], &v3);

Important traits for VertexIter<'a>

impl<'a> Iterator for VertexIter<'a> type Item = &'a VertexId;

pub fn out_neighbors(&self, id: &VertexId) -> VertexIter

Returns an iterator over the outbound neighbors of the vertex with the given id.

Example

use graphlib::Graph;

let mut graph: Graph<usize> = Graph::new();

let v1 = graph.add_vertex(0);
let v2 = graph.add_vertex(1);
let v3 = graph.add_vertex(2);
let v4 = graph.add_vertex(3);

graph.add_edge(&v1, &v2).unwrap();
graph.add_edge(&v3, &v1).unwrap();
graph.add_edge(&v1, &v4).unwrap();

assert!(set![&v2, &v4] == graph.out_neighbors(&v1).collect());

Important traits for VertexIter<'a>

impl<'a> Iterator for VertexIter<'a> type Item = &'a VertexId;

pub fn neighbors(&self, id: &VertexId) -> VertexIter

Returns an iterator over the inbound and outbound neighbors of the vertex with the given id.

Example

use graphlib::Graph;

let mut graph: Graph<usize> = Graph::new();

let v1 = graph.add_vertex(0);
let v2 = graph.add_vertex(1);
let v3 = graph.add_vertex(2);
let v4 = graph.add_vertex(3);

graph.add_edge(&v1, &v2).unwrap();
graph.add_edge(&v3, &v1).unwrap();
graph.add_edge(&v1, &v4).unwrap();

assert!(set![&v2, &v4, &v3] == graph.neighbors(&v1).collect());

pub fn edges(&self) -> impl Iterator<Item = (&VertexId, &VertexId)>

Returns an iterator over all edges that are situated in the graph.

Example

use graphlib::Graph;

let mut graph: Graph<usize> = Graph::new();
let mut edges = vec![];

let v1 = graph.add_vertex(0);
let v2 = graph.add_vertex(1);
let v3 = graph.add_vertex(2);
let v4 = graph.add_vertex(3);

graph.add_edge(&v1, &v2).unwrap();
graph.add_edge(&v3, &v1).unwrap();
graph.add_edge(&v1, &v4).unwrap();

// Iterate over edges
for v in graph.edges() {
    edges.push(v);
}

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

Important traits for VertexIter<'a>

impl<'a> Iterator for VertexIter<'a> type Item = &'a VertexId;

pub fn roots(&self) -> VertexIter

Returns an iterator over the root vertices of the graph.

Example

use graphlib::Graph;

let mut graph: Graph<usize> = Graph::new();
let mut roots = vec![];

let v1 = graph.add_vertex(0);
let v2 = graph.add_vertex(1);
let v3 = graph.add_vertex(2);
let v4 = graph.add_vertex(3);

graph.add_edge(&v1, &v2).unwrap();
graph.add_edge(&v3, &v1).unwrap();
graph.add_edge(&v1, &v4).unwrap();

// Iterate over roots
for v in graph.roots() {
    roots.push(v);
}

assert_eq!(roots.len(), 1);
assert_eq!(roots[0], &v3);

Important traits for VertexIter<'a>

impl<'a> Iterator for VertexIter<'a> type Item = &'a VertexId;

pub fn vertices(&self) -> VertexIter

Returns an iterator over all of the vertices that are placed in the graph.

Example

use graphlib::Graph;

let mut graph: Graph<usize> = Graph::new();
let mut vertices = vec![];

let v1 = graph.add_vertex(0);
let v2 = graph.add_vertex(1);
let v3 = graph.add_vertex(2);
let v4 = graph.add_vertex(3);

// Iterate over vertices
for v in graph.vertices() {
    vertices.push(v);
}

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

Important traits for Dfs<'a, T>

impl<'a, T> Iterator for Dfs<'a, T> type Item = &'a VertexId;

pub fn dfs(&self) -> Dfs<T>

Returns an iterator over the vertices of the graph in Depth-First Order. The iterator will follow vertices with lower weights first.

Example

use graphlib::Graph;
use std::collections::HashSet;

let mut graph: Graph<usize> = Graph::new();

let v1 = graph.add_vertex(0);
let v2 = graph.add_vertex(1);
let v3 = graph.add_vertex(2);
let v4 = graph.add_vertex(3);

graph.add_edge(&v1, &v2).unwrap();
graph.add_edge(&v3, &v1).unwrap();
graph.add_edge(&v1, &v4).unwrap();

let mut dfs = graph.dfs();

assert_eq!(dfs.next(), Some(&v3));
assert_eq!(dfs.next(), Some(&v1));
assert!(set![&v2, &v4] == dfs.collect());

Important traits for Bfs<'a, T>

impl<'a, T> Iterator for Bfs<'a, T> type Item = &'a VertexId;

pub fn bfs(&self) -> Bfs<T>

Returns an iterator over the vertices of the graph in Breadth-First Order. The iterator will follow vertices with lower weights first.

Example

use graphlib::Graph;

let mut graph: Graph<usize> = Graph::new();
let mut vertices = vec![];

let v1 = graph.add_vertex(0);
let v2 = graph.add_vertex(1);
let v3 = graph.add_vertex(2);
let v4 = graph.add_vertex(3);
let v5 = graph.add_vertex(4);
let v6 = graph.add_vertex(5);
let v7 = graph.add_vertex(6);

graph.add_edge(&v1, &v2).unwrap();
graph.add_edge(&v3, &v1).unwrap();
graph.add_edge(&v1, &v4).unwrap();
graph.add_edge(&v1, &v7).unwrap();
graph.add_edge(&v2, &v5).unwrap();
graph.add_edge(&v5, &v6).unwrap();

// Iterate over vertices
for v in graph.bfs() {
    vertices.push(v);
}

assert_eq!(vertices.len(), 7);

Trait Implementations

impl<T: Clone> Clone for Graph<T>

fn clone(&self) -> Graph<T>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Debug> Debug for Graph<T>

fn fmt(&self, f: &mut Formatter) -> Result

Formats the value using the given formatter.