pub trait ArithmeticallyWeightedGraph<T, W>where
T: Clone + Copy + Eq + Hash + PartialEq,
W: Clone + Copy + Add<Output = W> + Sub<Output = W> + PartialOrd + Ord + Default,{
// Provided methods
fn dijkstra(&self, from: T, to: T) -> Option<W>
where Self: Traversable<T, W> { ... }
fn dijkstra_with_path(&self, from: T, to: T) -> Option<(Vec<T>, W)>
where Self: Traversable<T, W> { ... }
fn a_star<G>(&self, from: T, to: T, heuristic: G) -> Option<W>
where Self: Traversable<T, W>,
G: Fn(T) -> W { ... }
fn a_star_with_path<G>(
&self,
from: T,
to: T,
heuristic: G,
) -> Option<(Vec<T>, W)>
where Self: Traversable<T, W>,
G: Fn(T) -> W { ... }
fn edmonds_karp(&self, source: T, sink: T) -> HashMap<(T, T), W>
where Self: Traversable<T, W> + Sized { ... }
}Provided Methods§
Sourcefn dijkstra(&self, from: T, to: T) -> Option<W>where
Self: Traversable<T, W>,
fn dijkstra(&self, from: T, to: T) -> Option<W>where
Self: Traversable<T, W>,
Returns the shortest length among paths from from to to.
§Examples
use yagraphc::graph::UnGraph;
use yagraphc::graph::traits::{GraphBuilding, Traversable};
use yagraphc::graph::traits::ArithmeticallyWeightedGraph;
let mut graph = UnGraph::new();
graph.add_edge(1, 2, 1);
graph.add_edge(2, 3, 2);
graph.add_edge(3, 4, 3);
graph.add_edge(1, 4, 7);
assert_eq!(graph.dijkstra(1, 4), Some(6));
assert_eq!(graph.dijkstra(1, 5), None);Sourcefn dijkstra_with_path(&self, from: T, to: T) -> Option<(Vec<T>, W)>where
Self: Traversable<T, W>,
fn dijkstra_with_path(&self, from: T, to: T) -> Option<(Vec<T>, W)>where
Self: Traversable<T, W>,
Returns the shortest path among paths from from to to, together with its length.
§Examples
use yagraphc::graph::UnGraph;
use yagraphc::graph::traits::{GraphBuilding, Traversable};
use yagraphc::graph::traits::ArithmeticallyWeightedGraph;
let mut graph = UnGraph::new();
graph.add_edge(1, 2, 1);
graph.add_edge(2, 3, 2);
graph.add_edge(3, 4, 3);
graph.add_edge(1, 4, 7);
assert_eq!(graph.dijkstra_with_path(1, 4).unwrap().0, vec![1, 2, 3, 4]);
assert_eq!(graph.dijkstra_with_path(1, 5), None);Sourcefn a_star<G>(&self, from: T, to: T, heuristic: G) -> Option<W>where
Self: Traversable<T, W>,
G: Fn(T) -> W,
fn a_star<G>(&self, from: T, to: T, heuristic: G) -> Option<W>where
Self: Traversable<T, W>,
G: Fn(T) -> W,
Returns the shortest length among paths from from to to using A*.
heuristic corresponds to the heuristic function of the A* algorithm.
§Examples
use yagraphc::graph::UnGraph;
use yagraphc::graph::traits::{GraphBuilding, Traversable};
use yagraphc::graph::traits::ArithmeticallyWeightedGraph;
let mut graph = UnGraph::new();
graph.add_edge(1, 2, 1);
graph.add_edge(2, 3, 2);
graph.add_edge(3, 4, 3);
graph.add_edge(1, 4, 7);
assert_eq!(graph.a_star(1, 4, |_| 0), Some(6));
assert_eq!(graph.a_star(1, 5, |_| 0), None);Sourcefn a_star_with_path<G>(
&self,
from: T,
to: T,
heuristic: G,
) -> Option<(Vec<T>, W)>where
Self: Traversable<T, W>,
G: Fn(T) -> W,
fn a_star_with_path<G>(
&self,
from: T,
to: T,
heuristic: G,
) -> Option<(Vec<T>, W)>where
Self: Traversable<T, W>,
G: Fn(T) -> W,
Returns the shortest path from from to to using A*, together with its length.
heuristic corresponds to the heuristic function of the A* algorithm.
§Examples
use yagraphc::graph::UnGraph;
use yagraphc::graph::traits::{GraphBuilding, Traversable};
use yagraphc::graph::traits::ArithmeticallyWeightedGraph;
let mut graph = UnGraph::new();
graph.add_edge(1, 2, 1);
graph.add_edge(2, 3, 2);
graph.add_edge(3, 4, 3);
graph.add_edge(1, 4, 7);
assert_eq!(graph.a_star_with_path(1, 4, |_| 0).unwrap().0, vec![1, 2, 3, 4]);
assert_eq!(graph.a_star_with_path(1, 5, |_| 0), None);Sourcefn edmonds_karp(&self, source: T, sink: T) -> HashMap<(T, T), W>where
Self: Traversable<T, W> + Sized,
fn edmonds_karp(&self, source: T, sink: T) -> HashMap<(T, T), W>where
Self: Traversable<T, W> + Sized,
Runs the Edmonds-Karp algorithm on the graph to find max flow.
Assumes the edge weights are the capacities.
Returns a HashMap with the flow values for each edge.
Please select a number type for W which allows for subtraction and negative values, otherwise there may be undefined behavior.
§Examples
use yagraphc::graph::UnGraph;
use yagraphc::graph::traits::{ArithmeticallyWeightedGraph, GraphBuilding, Traversable};
let mut graph = UnGraph::new();
graph.add_edge(1, 2, 1000);
graph.add_edge(2, 4, 1000);
graph.add_edge(1, 3, 1000);
graph.add_edge(3, 4, 1000);
graph.add_edge(2, 3, 1);
let flows = graph.edmonds_karp(1, 4);
assert_eq!(*flows.get(&(1, 2)).unwrap(), 1000);
assert_eq!(*flows.get(&(1, 3)).unwrap(), 1000);
assert_eq!(*flows.get(&(2, 3)).unwrap_or(&0), 0);Dyn Compatibility§
This trait is not dyn compatible.
In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.