Struct Graph

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

Graph data-structure

Implementations

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!(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!(graph.capacity() >= 5);

graph.shrink_to_fit();
assert!(graph.capacity() < 5);

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_check_cycle( &mut self, a: &VertexId, b: &VertexId, ) -> Result<(), GraphErr>

Attempts to place a new edge in the graph, checking if the specified edge will create a cycle in the graph. If it does, this operation will fail.

Note that this operation has a bigger performance hit than Graph::add_edge().

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_check_cycle(&v1, &v2);
graph.add_edge_check_cycle(&v1, &v2);
graph.add_edge_check_cycle(&v1, &v2);

// Fails on adding an edge which creates
// a cycle in the graph.
assert_eq!(graph.add_edge_check_cycle(&v2, &v1), Err(GraphErr::CycleError));

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 map<R>(&self, fun: impl Fn(&T) -> R) -> Graph<R>

Performs a map over all of the vertices of the graph, applying the given transformation function to each one.

Returns a new graph with the same edges but with transformed vertices.

Example

use graphlib::Graph;

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

graph.add_edge(&id1, &id2);

// Map each vertex
let mapped: Graph<usize> = graph.map(|v| v + 2);

assert!(graph.has_edge(&id1, &id2));
assert!(mapped.has_edge(&id1, &id2));
assert_eq!(graph.fetch(&id1).unwrap(), &1);
assert_eq!(graph.fetch(&id2).unwrap(), &2);
assert_eq!(mapped.fetch(&id1).unwrap(), &3);
assert_eq!(mapped.fetch(&id2).unwrap(), &4);

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

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

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

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

Example

#[macro_use] extern crate graphlib;
use std::collections::HashSet;
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());

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

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

Example

#[macro_use] extern crate graphlib;
use std::collections::HashSet;
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);

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

pub fn tips(&self) -> VertexIter<'_>

Returns an iterator over the tips of the graph. These are all the vertices that have an inbound edge but no outbound edge.

Example

#[macro_use] extern crate graphlib;
use std::collections::HashSet;
use graphlib::Graph;

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

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 tips
for v in graph.tips() {
    tips.insert(v);
}

assert_eq!(tips.len(), 2);
assert_eq!(tips, set![&v2, &v4]);

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

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

#[macro_use] extern crate graphlib;
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());

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

pub fn topo(&self) -> Topo<'_, T>

Returns an iterator over the vertices of the graph which follows a DFS based topological order (Kahn’s algorithm).

Topological sorting is not possible for graphs which contain a cycle. You may use topo.is_cylic() == false to verify that your graph is a DAG.

If you attempt to use a topological order without confirming that your graph is a DAG, you may encounter a panic!().

The panic!() will be encountered when the iterator detects that there are no more vertices to visit, but all vertices have not been visited.

Example

#[macro_use] extern crate graphlib;
use graphlib::Graph;
use std::collections::HashSet;

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);
let v4 = graph.add_vertex(4);

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

let mut topo = graph.topo();

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

pub fn dijkstra<'a>( &'a self, src: &'a VertexId, dest: &'a VertexId, ) -> VertexIter<'a>

Returns an iterator over the shortest path from the source vertex to the destination vertex. The iterator will yield None if there is no such path or the provided vertex ids do not belong to any vertices in the graph.

Example

#[macro_use] extern crate graphlib;
use graphlib::Graph;
use std::collections::HashSet;

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);
let v4 = graph.add_vertex(4);
let v5 = graph.add_vertex(5);
let v6 = graph.add_vertex(6);

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

let mut dijkstra = graph.dijkstra(&v1, &v4);

assert_eq!(dijkstra.next(), Some(&v1));
assert_eq!(dijkstra.next(), Some(&v2));
assert_eq!(dijkstra.next(), Some(&v3));
assert_eq!(dijkstra.next(), Some(&v4));
assert_eq!(dijkstra.next(), None);

pub fn values(&self) -> ValuesIter<'_, T>

Returns an iterator over the values of the vertices placed in the graph.

Example

#[macro_use] extern crate graphlib;
use graphlib::Graph;
use std::collections::HashSet;

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

let mut values = graph.values();

assert!(set![&1, &2, &3] == values.collect());

pub fn to_dot( &self, graph_name: &str, output: &mut impl Write, ) -> Result<(), GraphErr>

Creates a file with the dot representation of the graph. This method requires the dot crate feature.

Example

use graphlib::Graph;

use std::fs::File;
let mut f = File::create("example1.dot").unwrap();

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

 let v1 = graph.add_vertex("test1".to_string());
 let v2 = graph.add_vertex("test2".to_string());
 let v3 = graph.add_vertex("test3".to_string());
 let v4 = graph.add_vertex("test4".to_string());

 let v5 = graph.add_vertex("test5".to_string());
 let v6 = graph.add_vertex("test6".to_string());

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

 assert!(graph.to_dot("example1", &mut f).is_ok());

pub fn add_vertex_label( &mut self, vertex_id: &VertexId, label: &str, ) -> Result<Option<String>, GraphErr>

Labels the vertex with the given id. Returns the old label if successful.

This method requires the dot crate feature.

Example

use graphlib::{Graph, VertexId};

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

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

assert!(graph.add_vertex_label(&v1, "V1").is_ok());
assert!(graph.add_vertex_label(&v2, "V2").is_ok());
assert!(graph.add_vertex_label(&v3, "V3").is_ok());
assert!(graph.add_vertex_label(&random_id, "will fail").is_err());

pub fn add_edge_label( &mut self, a: &VertexId, b: &VertexId, label: &str, ) -> Result<Option<String>, GraphErr>

Labels the edge with between the given vertices. Returns the old label if successful.

This method requires the dot crate feature.

Example

use graphlib::{Graph, VertexId};

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

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

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

assert!(graph.add_edge_label(&v1, &v2, "V1->V2").is_ok());
assert!(graph.add_edge_label(&v3, &v1, "V3->V1").is_ok());
assert!(graph.add_edge_label(&v2, &v3, "V2->V3").is_err());
assert!(graph.add_edge_label(&v1, &v3, "V1->V3").is_err());

pub fn vertex_label(&self, vertex_id: &VertexId) -> Option<&str>

Retrieves the label of the vertex with the given id.

This method requires the dot crate feature.

Returns None if there is no vertex associated with the given id in the graph.

pub fn edge_label(&self, a: &VertexId, b: &VertexId) -> Option<&str>

Retrieves the label of the edge with the given vertices.

This method requires the dot crate feature.

Returns None if there is no edge associated with the given vertices in the graph.

pub fn map_vertex_labels( &mut self, fun: impl FnMut(&VertexId, Option<&str>) -> String, )

Maps each label that is placed on a vertex to a new label.

This method requires the dot crate feature.

use std::collections::HashMap;
use graphlib::{Graph, VertexId};

let mut graph: Graph<usize> = Graph::new();
let random_id = VertexId::random();
let mut vertex_id: usize = 1;

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

assert!(graph.add_vertex_label(&v1, &format!("V{}", vertex_id)).is_ok());
vertex_id += 1;

assert!(graph.add_vertex_label(&v2, &format!("V{}", vertex_id)).is_ok());
vertex_id += 1;

assert!(graph.add_vertex_label(&v3, &format!("V{}", vertex_id)).is_ok());

assert_eq!(graph.vertex_label(&v1).unwrap(), "V1");
assert_eq!(graph.vertex_label(&v2).unwrap(), "V2");
assert_eq!(graph.vertex_label(&v3).unwrap(), "V3");

let new_labels: HashMap<VertexId, String> = vec![v1.clone(), v2.clone(), v3.clone(), v4.clone()]
    .iter()
    .map(|id| {
        vertex_id += 1;
        let label = format!("V{}", vertex_id);

        (id.clone(), label)
    })
    .collect();

graph.map_vertex_labels(|id, _old_label| new_labels.get(id).unwrap().clone());

assert_eq!(graph.vertex_label(&v1).unwrap(), "V4");
assert_eq!(graph.vertex_label(&v2).unwrap(), "V5");
assert_eq!(graph.vertex_label(&v3).unwrap(), "V6");
assert_eq!(graph.vertex_label(&v4).unwrap(), "V7");

pub fn map_edge_labels( &mut self, fun: impl FnMut(&Edge, Option<&str>) -> String, )

Maps each label that is placed on an edge to a new label.

This method requires the dot crate feature.

use std::collections::HashMap;
use graphlib::{Graph, VertexId};

let mut graph: Graph<usize> = Graph::new();
let random_id = VertexId::random();
let mut vertex_id: usize = 1;

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(&v1, &v4).unwrap();
graph.add_edge(&v4, &v3).unwrap();

assert!(graph.add_edge_label(&v1, &v2, &"V1->V2").is_ok());
assert!(graph.add_edge_label(&v2, &v3, &"V2->V3").is_ok());
assert!(graph.add_edge_label(&v1, &v4, &"V1->V4").is_ok());
assert!(graph.add_edge_label(&v4, &v3, &"V4->V3").is_ok());
assert!(graph.add_edge_label(&v1, &v3, &"V1->V3").is_err());

assert_eq!(graph.edge_label(&v1, &v2).unwrap(), "V1->V2");
assert_eq!(graph.edge_label(&v2, &v3).unwrap(), "V2->V3");
assert_eq!(graph.edge_label(&v1, &v4).unwrap(), "V1->V4");
assert_eq!(graph.edge_label(&v4, &v3).unwrap(), "V4->V3");

graph.map_edge_labels(|edge, old_label| format!("*{}*", old_label.unwrap()));

assert_eq!(graph.edge_label(&v1, &v2).unwrap(), "*V1->V2*");
assert_eq!(graph.edge_label(&v2, &v3).unwrap(), "*V2->V3*");
assert_eq!(graph.edge_label(&v1, &v4).unwrap(), "*V1->V4*");
assert_eq!(graph.edge_label(&v4, &v3).unwrap(), "*V4->V3*");

Trait Implementations

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

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

Returns a duplicate 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.

impl<T: Default> Default for Graph<T>

fn default() -> Graph<T>

Returns the “default value” for a type.