Struct graphlib::Graph

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

Methods

impl<T> Graph<T>

pub fn new() -> Graph<T>

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 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);
 
println!("V1: {:?}", v1);
println!("V2: {:?}", v2);
println!("V3: {:?}", v3);
println!("V4: {:?}", v4);

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<'a>(&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<'a>(&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 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.out_neighbors(&v1) {
    neighbors.push(v);
}
 
assert_eq!(neighbors.len(), 2);
assert_eq!(neighbors[0], &v2);
assert_eq!(neighbors[1], &v4);

Important traits for VertexIter<'a>

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

pub fn neighbors<'a>(&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 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.neighbors(&v1) {
    neighbors.push(v);
}
 
assert_eq!(neighbors.len(), 3);
assert_eq!(neighbors[0], &v2);
assert_eq!(neighbors[1], &v4);
assert_eq!(neighbors[2], &v3);

Important traits for VertexIter<'a>

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

pub fn roots<'a>(&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<'a>(&self) -> Dfs<T>

Returns an iterator over the vertices of the graph in Depth-First Order.

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);

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

// Iterate over vertices
for v in graph.dfs() {
    vertices.push(v);
}
 
assert_eq!(vertices.len(), 4);
assert_eq!(vertices[0], &v3);
assert_eq!(vertices[1], &v1);
assert_eq!(vertices[2], &v2);
assert_eq!(vertices[3], &v4);

Important traits for Bfs<'a, T>

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

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

Returns an iterator over the vertices of the graph in Breadth-First Order.

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);
assert_eq!(vertices[0], &v3);
assert_eq!(vertices[1], &v1);
assert_eq!(vertices[2], &v2);
assert_eq!(vertices[3], &v4);
assert_eq!(vertices[4], &v7);
assert_eq!(vertices[5], &v5);
assert_eq!(vertices[6], &v6);

pub fn fetch_id_ref<'b>(&'b self, id: &VertexId) -> Option<&'b VertexId>

Attempts to fetch a reference to a stored vertex id which is equal to the given VertexId.

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.