spokes

Network and Network Flow Optimization Tools

Introduction

The following example is based on the following graph sourced from [Wikipedia][https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm].

Here, the goal is to find the shortest path tree rooted at node 0. In the example, it is verified the distance from node 0 to node 4 is 20.

```rust use spokes::{Network, algorithms::{dijkstrashortestpath, Distance}, ArcStorage};

let mut network: Network = Network::new(); network.addnodes((0..6).map(|i| (i, ()))); network.addarcs([ (0, 1, 7), (1, 0, 7), (0, 5, 14), (5, 0, 14), (0, 2, 9), (2, 0, 9), (1, 2, 10), (2, 1, 10), (1, 3, 15), (3, 1, 15), (2, 5, 2), (5, 2, 2), (2, 3, 11), (3, 2, 11), (3, 4, 6), (4, 3, 6), (4, 5, 9), (5, 4, 9), ]);

let shortestpathtree = dijkstrashortestpath(&network, 0);

asserteq!(shortestpath_tree.node(&4), Some(&Distance::Finite(20)));

let mut expected_network: Network, ()> = Network::new();

expectednetwork.addnodes([ (0, Distance::Finite(0)), (1, Distance::Finite(7)), (2, Distance::Finite(9)), (3, Distance::Finite(20)), (4, Distance::Finite(20)), (5, Distance::Finite(11)), ]);

expectednetwork.addarcs([ (1, 0), (2, 0), (3, 2), (5, 2), (4, 5), ]);

asserteq!(shortestpathtree, expectednetwork); ```

License: MIT or Apache-2.0