Struct GraphNum

pub struct GraphNum { /* private fields */ }

Implementations

impl GraphNum

pub fn new(n: usize) -> Self

pub fn add_vertex(&mut self, vertex: usize)

Adds a new vertex to the graph

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

Adds a new oriented edge to the graph

pub fn bfs(&self, from: usize) -> Vec<VertexNumProperties>

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

 use librualg::graph::GraphNum;

 let mut graph = GraphNum::new(20);
 graph.add_vertex(1);
 graph.add_vertex(2);
 graph.add_vertex(3);
 graph.add_vertex(4);
 graph.add_vertex(5);
 graph.add_vertex(8);
 graph.add_vertex(17);
 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]);

 graph.add_oriented_edge(17, 1, 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(11);
 assert_eq!(graph.search_path(11, &parents), None);

pub fn dfs(&self, from: usize) -> Vec<VertexNumProperties>

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

 use librualg::graph::GraphNum;

 let mut graph = GraphNum::new(10);

 graph.add_vertex(1);
 graph.add_vertex(2);
 graph.add_vertex(3);
 graph.add_vertex(5);
 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: usize, ) -> (Vec<VertexNumProperties>, Vec<Option<f32>>)

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

 use librualg::graph::GraphNum;

 let mut graph = GraphNum::new(10);

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

 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[5].unwrap(), 14.0);
 assert_eq!(distances[7], None);

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

Get connected components

 use librualg::graph::GraphNum;

 let mut graph = GraphNum::new(20);
 graph.add_vertex(1);
 graph.add_vertex(2);
 graph.add_vertex(3);
 graph.add_vertex(4);
 graph.add_vertex(5);
 graph.add_vertex(6);
 graph.add_vertex(7);
 graph.add_vertex(8);
 graph.add_vertex(9);
 graph.add_vertex(10);
 graph.add_vertex(11);
 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<usize>>

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

pub fn kruskal(&self) -> GraphNum

Kruskal’s algorithm

use librualg::graph::GraphNum;

let mut graph = GraphNum::new(20);

graph.add_vertex(1);
graph.add_vertex(2);
graph.add_vertex(3);
graph.add_vertex(4);
graph.add_vertex(5);
graph.add_vertex(6);
graph.add_vertex(7);

graph.add_oriented_edge(1, 2, 7.0);
graph.add_oriented_edge(2, 1, 7.0);
graph.add_oriented_edge(1, 4, 5.0);
graph.add_oriented_edge(4, 1, 5.0);
graph.add_oriented_edge(2, 3, 8.0);
graph.add_oriented_edge(3, 2, 8.0);
graph.add_oriented_edge(2, 5, 7.0);
graph.add_oriented_edge(5, 2, 7.0);
graph.add_oriented_edge(2, 4, 9.0);
graph.add_oriented_edge(4, 2, 9.0);
graph.add_oriented_edge(3, 5, 5.0);
graph.add_oriented_edge(5, 3, 5.0);
graph.add_oriented_edge(5, 7, 9.0);
graph.add_oriented_edge(7, 5, 9.0);
graph.add_oriented_edge(5, 6, 8.0);
graph.add_oriented_edge(6, 5, 8.0);
graph.add_oriented_edge(5, 4, 15.0);
graph.add_oriented_edge(4, 5, 15.0);
graph.add_oriented_edge(6, 7, 11.0);
graph.add_oriented_edge(7, 6, 11.0);
graph.add_oriented_edge(6, 4, 6.0);
graph.add_oriented_edge(4, 6, 6.0);
let tree = graph.kruskal();
assert_eq!(vec![1, 2, 5, 7], tree.search_path(7, &tree.bfs(1)).unwrap());
assert_eq!(vec![1, 2, 5, 3], tree.search_path(3, &tree.bfs(1)).unwrap());

pub fn search_path( &self, target: usize, parents: &[VertexNumProperties], ) -> Option<Vec<usize>>