### 1 unstable release

0.1.0 | Aug 2, 2022 |
---|

#**1267** in Math

**MIT**license

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`(``)``;`
network`.``add_nodes``(``(``0``..``6``)``.``map``(``|``i``|` `(`i`,` `(``)``)``)``)``;`
network`.``add_arcs``(``[`
`(``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`(``)``;`
expected_network`.``add_nodes``(``[`
`(``0``,` `Distance``::`Finite`(``0``)``)``,`
`(``1``,` `Distance``::`Finite`(``7``)``)``,`
`(``2``,` `Distance``::`Finite`(``9``)``)``,`
`(``3``,` `Distance``::`Finite`(``20``)``)``,`
`(``4``,` `Distance``::`Finite`(``20``)``)``,`
`(``5``,` `Distance``::`Finite`(``11``)``)``,`
`]``)``;`
expected_network`.``add_arcs``(``[`
`(``1``,` `0``)``,`
`(``2``,` `0``)``,`
`(``3``,` `2``)``,`
`(``5``,` `2``)``,`
`(``4``,` `5``)``,`
`]``)``;`
`assert_eq!``(`shortest_path_tree`,` expected_network`)``;`

License: MIT or Apache-2.0

#### Dependencies

~1.5MB

~27K SLoC