spokes 0.3.0

A network and network flow library.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

//! Example datasets

use std::io::{BufRead, BufReader};

use flate2::bufread::GzDecoder;

use crate::{ArcInfo, Network};

#[derive(Clone, Debug)]
/// Description of city nodes in the Knuth Miles dataset
pub struct KnuthMilesNodeAttributes {
    /// Name of the city
    pub name: String,
    /// Location of city in x,y coordinates
    pub position: (f64, f64),
    /// Population
    pub population: f64,
}

/// Load example graph from Knuth miles example dataset
///
/// # Panics
/// This panics if the dataset has invalid keys.
#[must_use]
pub fn knuth_miles() -> Network<u16, KnuthMilesNodeAttributes, u16> {
    let file_bytes = include_bytes!("../resources/knuth_miles.txt.gz");
    let reader = BufReader::new(GzDecoder::new(&file_bytes[..]));

    let mut network: Network<u16, KnuthMilesNodeAttributes, u16> = Network::new();

    let mut i = 0;
    let mut next_node_id = 0;

    for line in reader.lines() {
        let line = line.expect("The next line should be readable");

        if let Some(first_char) = line.chars().next() {
            // Skip lines that begin with '*'
            if first_char == '*' {
                continue;
            }

            if first_char.is_ascii_digit() {
                // This line has the distances for the current city
                let distances: Vec<u16> = line
                    .split_whitespace()
                    .map(|s| s.parse().expect("Distances should be integers"))
                    .collect();

                for distance in distances {
                    network
                        .add_arc((
                            next_node_id - 1,
                            u16::try_from(network.n_nodes() - i - 1)
                                .expect("All values are u16 encodable"),
                            distance,
                        ))
                        .expect("Nodes should be in network already");
                    i += 1;
                }
            } else {
                // This line defines a new node / City
                i = 1;

                let (name, rem) = line.split_once('[').expect("Should have [ delimiter");
                let (coord, pop) = rem.split_once(']').expect("Should have ] delimiter");
                let (x, y) = coord
                    .split_once(',')
                    .expect("Coords should be comma seperated values");

                let x = x.parse().expect("x coordinate should be an integer");
                let y = y.parse().expect("y coordinate should be an integer");

                let population = pop.parse().expect("Population should be an integer");

                network.add_node(
                    next_node_id,
                    KnuthMilesNodeAttributes {
                        name: name.to_string(),
                        position: (x, y),
                        population,
                    },
                );

                next_node_id += 1;
            }
        }
    }

    // Add backwards arcs
    let backwards_arcs: Vec<_> = network
        .arc_iter()
        .map(|a| ArcInfo::new(a.head, a.tail, a.attributes))
        .collect();
    network
        .add_arcs(backwards_arcs)
        .expect("Head and Tail nodes are already inserted.");

    network
}

#[cfg(test)]
mod tests {
    use super::knuth_miles;

    #[test]
    fn load_knuth_miles() {
        let network = knuth_miles();

        assert_eq!(network.n_nodes(), 128);

        for (&id, _) in network.iter_nodes() {
            assert_eq!(network.forward_arcs(&id).count(), 127);
        }
    }
}