Struct Graph

pub struct Graph<V: Label, E: Label> { /* private fields */ }

Directed graph data-structure with generic parameters

It is assumed that the user can specify the data types stored at each vertex and edge.

For example, if you want to make a structure like this: (town1) <----- 100 km -----> (town2) you can use Graph<String, u32> data type

Serialization to String in Trivial Graph Format

See impl<V, E> Display for Graph<V, E>

Deserialization from &str in Trivial Graph Format

See impl<V, E> FromStr for Graph<V, E>

Example

In this example, we will make several cities and link them together with specified distance in km

use simple_graph::Graph;
use std::str::FromStr;

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

let moscow = graph.add_vertex("Moscow".into()).unwrap();
let vladimir = graph.add_vertex("Vladimir".into()).unwrap();
let yaroslavl = graph.add_vertex("Yaroslavl".into()).unwrap();
let novgorod = graph.add_vertex("Novgorod".into()).unwrap();
let vologda = graph.add_vertex("Vologda".into()).unwrap();

graph.add_edge(moscow, vladimir, 180).unwrap();
graph.add_edge(moscow, yaroslavl, 250).unwrap();
graph.add_edge(vladimir, novgorod, 225).unwrap();
graph.add_edge(yaroslavl, vologda, 175).unwrap();

let serialized = graph.to_string();
let expected = concat!(
    "1 Moscow\n",
    "2 Vladimir\n",
    "3 Yaroslavl\n",
    "4 Novgorod\n",
    "5 Vologda\n",
    "#\n",
    "1 2 180\n",
    "1 3 250\n",
    "2 4 225\n",
    "3 5 175\n",
);
assert_eq!(serialized, expected);

let mut graph_deserialized = Graph::from_str(&serialized).unwrap();
assert_eq!(graph, graph_deserialized);

Implementations

impl<V: Label, E: Label> Graph<V, E>

pub fn new() -> Self

Creates new graph

use simple_graph::Graph;

let _: Graph<String, u32> = Graph::new();

pub fn get_vertex_id(&self, vertex: &V) -> VertexId

Gets VertexId by it’s value. It just creates hash of the &V, doesn’t panics

use simple_graph::Graph;
use std::str::FromStr;

let graph: Graph<String, u32> = Graph::new();
assert_ne!(graph.get_vertex_id(&"Moscow".into()), graph.get_vertex_id(&"Vladimir".into()));

let graph: Graph<String, u32> = Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();

let moscow = graph.get_vertex_id(&"Moscow".into());
let vladimir = graph.get_vertex_id(&"Vladimir".into());

assert_eq!(graph.get_edge_value(moscow, vladimir), Ok(&180));

pub fn add_vertex(&mut self, vertex: V) -> Result<VertexId>

Trying to add vertex to the graph, returns GraphOperationError::VertexAlreadyExists if can’t do this

use simple_graph::{Graph, GraphOperationError};

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

assert!(graph.add_vertex("Moscow".into()).is_ok());
assert_eq!(graph.add_vertex("Moscow".into()), Err(GraphOperationError::VertexAlreadyExists));

pub fn get_vertex(&self, vertex: VertexId) -> Result<&V>

Trying to get vertex by id, returns GraphOperationError::VertexDoesNotExist if can’t do this

use simple_graph::{Graph, GraphOperationError};
use std::str::FromStr;

let graph: Graph<String, u32> = Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();

assert!(graph.get_vertex(graph.get_vertex_id(&"Moscow".into())).is_ok());
assert_eq!(graph.get_vertex(graph.get_vertex_id(&"New York".into())), Err(GraphOperationError::VertexDoesNotExist));

pub fn remove_vertex(&mut self, target_vertex: VertexId) -> Result<()>

Trying to remove vertex by id, returns GraphOperationError::VertexDoesNotExist if can’t do this

use simple_graph::{Graph, GraphOperationError};
use std::str::FromStr;

let mut graph: Graph<String, u32> = Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();

assert!(graph.remove_vertex(graph.get_vertex_id(&"Moscow".into())).is_ok());
assert_eq!(graph.remove_vertex(graph.get_vertex_id(&"New York".into())), Err(GraphOperationError::VertexDoesNotExist));

assert_eq!(graph.vertices_count(), 4);

pub fn add_edge(&mut self, from: VertexId, to: VertexId, edge: E) -> Result<()>

Trying to add edge between two vertices, returns GraphOperationError::VertexDoesNotExist if can’t do this

use simple_graph::{Graph, GraphOperationError};
use std::str::FromStr;

let mut graph: Graph<String, u32> = Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();

let novgorod = graph.get_vertex_id(&"Novgorod".into());
let kazan = graph.add_vertex("Kazan".into()).unwrap();
let new_york = graph.get_vertex_id(&"New York".into());

assert!(graph.add_edge(novgorod, kazan, 325).is_ok());
assert_eq!(graph.add_edge(new_york, kazan, 9000), Err(GraphOperationError::VertexDoesNotExist));

pub fn get_edge( &self, from: VertexId, to: VertexId, ) -> Result<&([VertexId; 2], E)>

Trying to get edge between two vertices, returns GraphOperationError::EdgeDoesNotExist if can’t do this

use simple_graph::{Graph, GraphOperationError};
use std::str::FromStr;

let graph: Graph<String, u32> = Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();

let moscow = graph.get_vertex_id(&"Moscow".into());
let vladimir = graph.get_vertex_id(&"Vladimir".into());

// Moscow -> Vladimir (ok)
let ([_from, _to], value) = graph.get_edge(moscow, vladimir).unwrap();
assert_eq!(value, &180);
// Vladimir -> Moscow (err)
assert_eq!(graph.get_edge(vladimir, moscow), Err(GraphOperationError::EdgeDoesNotExist));

pub fn get_edge_value(&self, from: VertexId, to: VertexId) -> Result<&E>

Trying to get edge value between two vertices, returns GraphOperationError::EdgeDoesNotExist if can’t do this

use simple_graph::Graph;
use std::str::FromStr;

let graph: Graph<String, u32> = Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();

let moscow = graph.get_vertex_id(&"Moscow".into());
let vladimir = graph.get_vertex_id(&"Vladimir".into());

assert_eq!(graph.get_edge_value(moscow, vladimir), Ok(&180));

pub fn remove_edge(&mut self, from: VertexId, to: VertexId) -> Result<()>

Trying to remove edge between two vertices, returns GraphOperationError::EdgeDoesNotExist if can’t do this

use simple_graph::{Graph, GraphOperationError};
use std::str::FromStr;

let mut  graph: Graph<String, u32> = Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();

let moscow = graph.get_vertex_id(&"Moscow".into());
let vladimir = graph.get_vertex_id(&"Vladimir".into());

assert!(graph.remove_edge(moscow, vladimir).is_ok());
assert_eq!(graph.remove_edge(moscow, vladimir), Err(GraphOperationError::EdgeDoesNotExist));

pub fn vertices_count(&self) -> usize

Returns count of vertices in the graph

use simple_graph::Graph;
use std::str::FromStr;

let mut graph: Graph<String, u32> = Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();
assert_eq!(graph.vertices_count(), 5);

pub fn edges_count(&self) -> usize

Returns count of edges in the graph

use simple_graph::Graph;
use std::str::FromStr;

let mut graph: Graph<String, u32> = Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();
assert_eq!(graph.edges_count(), 4);

pub fn vertices(&self) -> Result<Vec<(&V, Vec<(&V, &E)>)>>

Returns [Result<Vec<(&V, Vec<(&V, &E)>)>>] which is vertices representation

where

• &V - vertex
• Vec<(&V, &E)> - adjacent vertices

use simple_graph::Graph;
use std::str::FromStr;

let graph: Graph<String, u32> = Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();

for (vertex, adjacent_vertices) in graph.vertices().unwrap() {
    println!("{vertex}: {adjacent_vertices:?}");
}

//output looks like

//Moscow: [("Vladimir", 180), ("Yaroslavl", 250)]
//Vladimir: [("Novgorod", 225)]
//Yaroslavl: [("Vologda", 175)]
//Novgorod: []
//Vologda: []

pub fn edges(&self) -> Result<Vec<([&V; 2], &E)>>

Returns [Result<Vec<([&V; 2], &E)>>] which is edges representation

where

• [&V; 2] - [from, to]
• &E - edge data

use simple_graph::Graph;
use std::str::FromStr;

let graph: Graph<String, u32> = Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();

for ([from, to], data) in graph.edges().unwrap() {
   println!("{from} ---- [{data}] ----> {to}");
}

//output looks like

//Moscow ---- [180] ----> Vladimir
//Moscow ---- [250] ----> Yaroslavl
//Vladimir ---- [225] ----> Novgorod
//Yaroslavl ---- [175] ----> Vologda

pub fn get_vertex_info( &self, vertex_id: VertexId, ) -> Result<(&V, Vec<(&V, &E)>)>

Trying to get detailed information about the vertex

use simple_graph::Graph;
use std::str::FromStr;

let graph: Graph<String, u32> = Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();

let moscow = graph.get_vertex_id(&"Moscow".into());

let (vertex_data, adjacent_vertices) = graph.get_vertex_info(moscow).unwrap();
assert_eq!(vertex_data, &String::from("Moscow"));
assert_eq!(adjacent_vertices, vec![(&"Vladimir".into(), &180), (&"Yaroslavl".into(), &250)]);

pub fn bfs<F: FnMut(&V, Vec<(&V, &E)>)>( &self, source: VertexId, access: F, ) -> Result<()>

Breadth-first search algorithm uses VecDeque for queue

use simple_graph::Graph;
use std::str::FromStr;

let graph: Graph<String, u32> =
    Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();

let moscow = graph.get_vertex_id(&"Moscow".into());

let mut visited = Vec::new();
graph
    .bfs(moscow, |vertex, adjacent_vertices| {
        visited.push(format!("{vertex}: {adjacent_vertices:?}"));
    })
    .expect("failed to perform BFS");

//(1) Moscow ->
//              (2) Vladimir  -> (4) Novgorod
//              (3) Yaroslavl -> (5) Vologda
let expected = vec![
    r#"Moscow: [("Vladimir", 180), ("Yaroslavl", 250)]"#, //1
    r#"Vladimir: [("Novgorod", 225)]"#, //2
    r#"Yaroslavl: [("Vologda", 175)]"#, //3
    r#"Novgorod: []"#, //4
    r#"Vologda: []"#, //5
];
assert_eq!(visited, expected);

pub fn dfs<F: FnMut(&V, Vec<(&V, &E)>)>( &self, source: VertexId, access: F, ) -> Result<()>

Depth-first search algorithm uses Vec for stack

use simple_graph::Graph;
use std::str::FromStr;

let graph: Graph<String, u32> =
    Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();

let moscow = graph.get_vertex_id(&"Moscow".into());

let mut visited = Vec::new();
graph
    .dfs(moscow, |vertex, adjacent_vertices| {
        visited.push(format!("{vertex}: {adjacent_vertices:?}"));
    })
    .expect("failed to perform DFS");

//(1) Moscow ->
//              (2) Yaroslavl  -> (3) Vologda
//              (4) Vladimir   -> (5) Novgorod
let expected = vec![
    r#"Moscow: [("Vladimir", 180), ("Yaroslavl", 250)]"#,
    r#"Yaroslavl: [("Vologda", 175)]"#,
    r#"Vologda: []"#,
    r#"Vladimir: [("Novgorod", 225)]"#,
    r#"Novgorod: []"#,
];
assert_eq!(visited, expected);

Trait Implementations

impl<V: Debug + Label, E: Debug + Label> Debug for Graph<V, E>

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

Formats the value using the given formatter.

impl<V: Default + Label, E: Default + Label> Default for Graph<V, E>

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

Returns the “default value” for a type.

impl<V: Label, E: Label> Display for Graph<V, E>

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

Formats graph as string in Trivial Graph Format

use simple_graph::Graph;

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

let first_node_id = graph.add_vertex("First node".into()).unwrap();
let second_node_id = graph.add_vertex("Second node".into()).unwrap();

graph.add_edge(first_node_id, second_node_id, "Edge between the two".into()).unwrap();

let s = concat!(
    "1 First node\n",
    "2 Second node\n",
    "#\n",
    "1 2 Edge between the two\n",
);
assert_eq!(graph.to_string(), s);

impl<V: Label, E: Label> FromStr for Graph<V, E>

fn from_str(s: &str) -> Result<Self, Self::Err>

Parses crate::Graph<V, E> from &str in Trivial Graph Format

use simple_graph::{Graph, VertexId};
use std::str::FromStr;

let s = concat!(
    "1 First node\n",
    "2 Second node\n",
    "#\n",
    "1 2 Edge between the two\n",
);
let mut graph = Graph::<String, String>::from_str(s).unwrap();

let first_node_id = graph.get_vertex_id(&"First node".into());
let second_node_id = graph.get_vertex_id(&"Second node".into());

let ([from, to], edge) = graph.get_edge(first_node_id, second_node_id).unwrap();
assert!(*from == first_node_id && *to == second_node_id && edge == "Edge between the two");

type Err = ParseGraphError

The associated error which can be returned from parsing.

impl<V: PartialEq + Label, E: PartialEq + Label> PartialEq for Graph<V, E>

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

Tests for self and other values to be equal, and is used by ==.

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<V: Eq + Label, E: Eq + Label> Eq for Graph<V, E>

impl<V: Label, E: Label> StructuralPartialEq for Graph<V, E>