Struct structures::graph::Graph

pub struct Graph { /* fields omitted */ }

Directed Graph

Examples

use structures::graph::Graph;

let graph: Graph = vec![
  (1, 2, 7), (1, 3, 9), (1, 6, 14),
  (2, 3, 10), (2, 4, 15), (3, 4, 11),
  (3, 6, 2), (4, 5, 6), (6, 5, 9),
].into_iter().collect();

assert_eq!(graph.shortest_path(1, Some(5))[&5], (20, vec![1, 3, 6, 5]));

assert_eq!(graph.shortest_paths()[&1][&5], (20, vec![1, 3, 6, 5]));

Methods

impl Graph

pub fn new() -> Self

pub fn vertices(&self) -> Vertices

pub fn vertices_outgoing_from(&self, source: Vertex) -> Vertices

pub fn edges(&self) -> Edges

pub fn weight(&self, source: Vertex, target: Vertex) -> Option<Weight>

pub fn add_edge(&mut self, source: Vertex, target: Vertex, weight: Weight)

impl Graph

pub fn shortest_path(
    &self,
    source: Vertex,
    target: Option<Vertex>
) -> HashMap<Vertex, (Weight, Path)>

Dijkstra's Algorithm

pub fn shortest_paths(&self) -> HashMap<Vertex, HashMap<Vertex, (Weight, Path)>>

Floyd-Warshall Algorithm

pub fn topo_sort(&self) -> Option<Path>

Topological Sorting

Trait Implementations

impl Extend<(usize, usize, usize)> for Graph

fn extend<I: IntoIterator<Item = (Vertex, Vertex, Weight)>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

impl Default for Graph

fn default() -> Graph

Returns the "default value" for a type.

impl FromIterator<(usize, usize, usize)> for Graph

fn from_iter<I: IntoIterator<Item = (Vertex, Vertex, Weight)>>(iter: I) -> Self

Creates a value from an iterator.