spokes

A network and network flow library

1 unstable release

 0.1.0 Aug 2, 2022

#1267 in Math

88KB
2K SLoC

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.

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

let mut network: Network<usize, (), u16> = Network::new();
(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 shortest_path_tree = dijkstra_shortest_path(&network, 0);

assert_eq!(shortest_path_tree.node(&4), Some(&Distance::Finite(20)));

let mut expected_network: Network<usize, Distance<u16>, ()> = Network::new();

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

(1, 0),
(2, 0),
(3, 2),
(5, 2),
(4, 5),
]);

assert_eq!(shortest_path_tree, expected_network);
``````