Struct librualg::graph::GraphNum[−][src]

pub struct GraphNum { /* fields omitted */ }

Implementations

impl GraphNum[src]

pub fn new(n: usize) -> Self[src]

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

Adds a new vertex to the graph

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

Adds a new oriented edge to the graph

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

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>[src]

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>>)[src]

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>>[src]

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>>[src]

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

pub fn kruskal(&self) -> GraphNum[src]

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>>[src]

Auto Trait Implementations

Blanket Implementations

impl<T> Any for T where
    T: 'static + ?Sized, [src]

pub fn type_id(&self) -> TypeId[src]

Gets the TypeId of self. Read more

impl<T> Borrow<T> for T where
    T: ?Sized, [src]

pub fn borrow(&self) -> &T[src]

Immutably borrows from an owned value. Read more

impl<T> BorrowMut<T> for T where
    T: ?Sized, [src]

pub fn borrow_mut(&mut self) -> &mut T[src]

Mutably borrows from an owned value. Read more

impl<T> From<T> for T[src]

pub fn from(t: T) -> T[src]

Performs the conversion.

impl<T, U> Into<U> for T where
    U: From<T>, [src]

pub fn into(self) -> U[src]

Performs the conversion.

impl<T, U> TryFrom<U> for T where
    U: Into<T>, [src]

type Error = Infallible

The type returned in the event of a conversion error.

pub fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>[src]

Performs the conversion.

impl<T, U> TryInto<U> for T where
    U: TryFrom<T>, [src]

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.

pub fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>[src]

Performs the conversion.