Struct Graph

pub struct Graph<Indent>
where
    Indent: Eq + Ord + Clone,
{ /* private fields */ }

Implementations

impl<Indent> Graph<Indent>

where Indent: Eq + Ord + Clone,

pub fn new() -> Self

pub fn bfs(&self, from: Indent) -> BTreeMap<Indent, VertexProperties<Indent>>

BFS (Breadth-First Search) algorithm. Returns an ancestor vector along the graph traversal path

 use librualg::graph::Graph;

 let mut graph = Graph::new();
 graph.add_oriented_edge(1, 2, 0.0);
 graph.add_oriented_edge(2, 3, 0.0);
 graph.add_oriented_edge(2, 4, 0.0);
 graph.add_oriented_edge(2, 5, 0.0);
 graph.add_oriented_edge(4, 8, 0.0);
 graph.add_oriented_edge(8, 17, 0.0);
 let parents = graph.bfs(1);
 assert_eq!(graph.search_path(5, &parents).unwrap(), vec![1, 2, 5]);
 assert_eq!(graph.search_path(17, &parents).unwrap(), vec![1, 2, 4, 8, 17]);

pub fn dfs(&self, from: Indent) -> BTreeMap<Indent, VertexProperties<Indent>>

DFS (Depth-First Search) algorithm. Returns an ancestor vector along the graph traversal path

 use librualg::graph::Graph;

 let mut graph = Graph::new();
 graph.add_oriented_edge(1, 2, 0.0);
 graph.add_oriented_edge(2, 3, 0.0);
 graph.add_oriented_edge(3, 5, 0.0);

 let res = graph.dfs(1);
 assert_eq!(graph.search_path(5, &res).unwrap(), vec![1, 2, 3, 5]);

pub fn dijkstra( &self, from: Indent, ) -> (BTreeMap<Indent, VertexProperties<Indent>>, BTreeMap<Indent, f32>)

Dijkstra algorithm. Returns an ancestor vector along the graph traversal path and distances to the other vertexs

 use librualg::graph::Graph;

 let mut graph = Graph::new();
 graph.add_oriented_edge(1, 2, 2.0);
 graph.add_oriented_edge(2, 3, 5.0);
 graph.add_oriented_edge(3, 5, 7.0);
 graph.add_oriented_edge(1, 5, 19.0);

 let (parents, distances) = graph.dijkstra(1);
 assert_eq!(graph.search_path(5, &parents).unwrap(), vec![1, 2, 3, 5]);
 assert_eq!(graph.search_path(3, &parents).unwrap(), vec![1, 2, 3]);
 assert_eq!(*distances.get(&5).unwrap(), 14.0);

pub fn connected_components(&self) -> Vec<Vec<Indent>>

Get connected components

 use librualg::graph::Graph;

 let mut graph = Graph::new();
 graph.add_oriented_edge(1, 2, 0.0);
 graph.add_oriented_edge(2, 3, 0.0);
 graph.add_oriented_edge(3, 4, 0.0);

 graph.add_oriented_edge(5, 6, 0.0);
 graph.add_oriented_edge(6, 7, 0.0);

 graph.add_oriented_edge(8, 9, 0.0);
 graph.add_oriented_edge(9, 10, 0.0);
 graph.add_oriented_edge(10, 11, 0.0);

 let components = graph.connected_components();
 assert_eq!(components[0], [1, 2, 3, 4]);
 assert_eq!(components[1], [5, 6, 7]);
 assert_eq!(components[2], [8, 9, 10, 11]);

pub fn strongly_connected_components(&self) -> Vec<Vec<Indent>>

Get strongly connected components

use librualg::graph::Graph;

let mut graph = Graph::new();
graph.add_oriented_edge("a", "b", 0.0);
graph.add_oriented_edge("b", "f", 0.0);
graph.add_oriented_edge("e", "a", 0.0);
graph.add_oriented_edge("b", "e", 0.0);
graph.add_oriented_edge("e", "f", 0.0);

graph.add_oriented_edge("b", "c", 0.0);
graph.add_oriented_edge("f", "g", 0.0);
graph.add_oriented_edge("g", "f", 0.0);
graph.add_oriented_edge("c", "g", 0.0);

graph.add_oriented_edge("c", "d", 0.0);
graph.add_oriented_edge("d", "c", 0.0);
graph.add_oriented_edge("d", "h", 0.0);
graph.add_oriented_edge("h", "d", 0.0);
graph.add_oriented_edge("h", "g", 0.0);

let components = graph.strongly_connected_components();
assert_eq!(components[0], ["a", "b", "e"]);
assert_eq!(components[1], ["c", "d", "h"]);
assert_eq!(components[2], ["f", "g"]);

pub fn topological_sort(&self) -> Vec<Indent>

Topologic sort

use librualg::graph::Graph;
let mut graph = Graph::new();
graph.add_oriented_edge("a", "b", 0.0);
graph.add_oriented_edge("a", "c", 0.0);
graph.add_oriented_edge("a", "e", 0.0);
graph.add_oriented_edge("a", "d", 0.0);
graph.add_oriented_edge("b", "d", 0.0);
graph.add_oriented_edge("c", "d", 0.0);
graph.add_oriented_edge("c", "e", 0.0);

assert_eq!(graph.topological_sort(), vec!["a", "b", "c", "d", "e"]);

pub fn kruskal(&self) -> Graph<Indent>

Kruskal’s algorithm

use librualg::graph::Graph;

let mut graph = Graph::new();
graph.add_oriented_edge('A', 'B', 7.0);
graph.add_oriented_edge('B', 'A', 7.0);
graph.add_oriented_edge('A', 'D', 5.0);
graph.add_oriented_edge('D', 'A', 5.0);
let tree = graph.kruskal();

pub fn add_oriented_edge(&mut self, from: Indent, to: Indent, weight: f32)

Adds a new oriented edge to the graph

pub fn search_path( &self, target: Indent, parents: &BTreeMap<Indent, VertexProperties<Indent>>, ) -> Option<Vec<Indent>>

Returns the path in the graph between two vertices based on the ancestor vector Returns None if the path does not exist

use librualg::graph::Graph;

let mut graph = Graph::new();
graph.add_oriented_edge(1, 2, 0.0);
graph.add_oriented_edge(2, 3, 0.0);
graph.add_oriented_edge(2, 4, 0.0);
graph.add_oriented_edge(2, 5, 0.0);
graph.add_oriented_edge(4, 8, 0.0);
graph.add_oriented_edge(8, 17, 0.0);
let parents = graph.bfs(1);
assert_eq!(graph.search_path(5, &parents).unwrap(), vec![1, 2, 5]);
assert_eq!(graph.search_path(17, &parents).unwrap(), vec![1, 2, 4, 8, 17]);

let parents = graph.bfs(101);
assert_eq!(graph.search_path(101, &parents), None);

Trait Implementations

impl<Indent> Default for Graph<Indent>

where Indent: Eq + Ord + Clone,

fn default() -> Self

Returns the “default value” for a type.