Struct librualg::graph::Graph

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

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.bfs(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 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.