Struct librualg::graph::Graph [−][src]
Implementations
impl<Indent> Graph<Indent> where
Indent: Eq + Ord + Clone,
[src]
impl<Indent> Graph<Indent> where
Indent: Eq + Ord + Clone,
[src]pub fn new() -> Self
[src]
pub fn bfs(&self, from: Indent) -> BTreeMap<Indent, VertexProperties<Indent>>
[src]
pub fn bfs(&self, from: Indent) -> BTreeMap<Indent, VertexProperties<Indent>>
[src]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>>
[src]
pub fn dfs(&self, from: Indent) -> BTreeMap<Indent, VertexProperties<Indent>>
[src]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>)
[src]
pub fn dijkstra(
&self,
from: Indent
) -> (BTreeMap<Indent, VertexProperties<Indent>>, BTreeMap<Indent, f32>)
[src]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>>
[src]
pub fn connected_components(&self) -> Vec<Vec<Indent>>
[src]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>>
[src]
pub fn strongly_connected_components(&self) -> Vec<Vec<Indent>>
[src]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 add_oriented_edge(&mut self, from: Indent, to: Indent, weight: f32)
[src]
pub fn add_oriented_edge(&mut self, from: Indent, to: Indent, weight: f32)
[src]Adds a new oriented edge to the graph
pub fn search_path(
&self,
target: Indent,
parents: &BTreeMap<Indent, VertexProperties<Indent>>
) -> Option<Vec<Indent>>
[src]
pub fn search_path(
&self,
target: Indent,
parents: &BTreeMap<Indent, VertexProperties<Indent>>
) -> Option<Vec<Indent>>
[src]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
Auto Trait Implementations
impl<Indent> RefUnwindSafe for Graph<Indent> where
Indent: RefUnwindSafe,
Indent: RefUnwindSafe,
impl<Indent> Send for Graph<Indent> where
Indent: Send,
Indent: Send,
impl<Indent> Sync for Graph<Indent> where
Indent: Sync,
Indent: Sync,
impl<Indent> Unpin for Graph<Indent>
impl<Indent> UnwindSafe for Graph<Indent> where
Indent: RefUnwindSafe,
Indent: RefUnwindSafe,