pathfinder/map/
network.rs

1/*!
2Connects and paths between different connected Nodes.
3 */
4
5use super::*;
6use std::io::{self, Error, ErrorKind};
7
8/**
9Weighted Node
10 */
11struct WNodes {
12    nodes: Vec<Node>,
13    weight: u32,
14}
15
16/**
17Paths between two different points that are connected.
18
19
20## Errors
21
22The provided A and B don't exist in the network.
23
24The path could not be found.
25 */
26pub fn path<'a>(
27    network: &'a Network<Node>,
28    a: &str,
29    b: &str,
30    algorithm: &Fn(&Network<Node>, Node, Node) -> io::Result<Vec<Node>>,
31) -> io::Result<Vec<Node>> {
32    let opt_goal = network.get(b);
33    let opt_start = network.get(a);
34    if opt_goal.is_none() || opt_start.is_none() {
35        Err(Error::new(
36            ErrorKind::Other,
37            "Start or Goal path does not exist in Network",
38        ))
39    } else {
40        algorithm(&network, opt_start.unwrap(), opt_goal.unwrap())
41    }
42}
43
44/**
45Retrieves a node from a network.
46 */
47pub fn get(network: &Network<Node>, element: &str) -> Option<Node> {
48    let hash = node!(element, 0, 0).hash;
49    for (i, elem) in network.hash_map.iter().enumerate() {
50        if elem.is_some() && i == hash as usize % consts::NETWORK_REM {
51            return network.hash_map[i];
52        }
53    }
54
55    None
56}
57
58/**
59Creates a path using the 'shortest leg' in the journey at each stop.
60
61The shorest leg means that for every occurence of a path, the alternatives are sorted and the shortest is always selected.
62
63
64## Errors
65
66The path could not be found.
67
68 */
69pub fn path_shortest_leg<'a>(
70    network: &'a Network<Node>,
71    start: Node,
72    goal: Node,
73) -> io::Result<Vec<Node>> {
74    // Create a new Branch-off path.
75    let format = |mut nodes: Vec<Node>, link: &HL, acc: u32| -> WNodes {
76        let node = network.hash_map[link.t as usize % consts::NETWORK_REM].unwrap();
77        let weight = acc + coordinate::distance(nodes.first().unwrap().geo, node.geo);
78        nodes.insert(0, node);
79        WNodes { weight, nodes }
80    };
81
82    // Create the queue from connected links.
83    let mut queue: Vec<WNodes> = start
84        .links()
85        .iter()
86        .filter(|x| x.is_connected())
87        .map(|x| format(vec![start], x, 0))
88        .collect::<Vec<_>>();
89
90    while !queue.is_empty() {
91        // Sort the queue based on weight.
92        queue.sort_by_key(|wn| wn.weight);
93
94        // Pull the closest path from the Queue.
95        let wnodes = queue.remove(0);
96
97        // Get the current Node in the closest path.
98        let current = wnodes.nodes.first().unwrap();
99
100        // End if we are at the goal.
101        if current.hash == goal.hash {
102            return Ok(wnodes.nodes);
103        }
104
105        // Push new paths to the queue.
106        let _ = current
107            .links()
108            .iter()
109            .filter(|x| x.is_connected())
110            .map(|x| queue.push(format(wnodes.nodes.clone(), x, wnodes.weight)))
111            .collect::<Vec<_>>();
112    }
113
114    // If we run out of items in the Queue, and we have not reacted
115    // the goal, the path is invalid. And does not exist.
116    Err(Error::new(ErrorKind::Other, "not a valid path"))
117}
118
119#[cfg(test)]
120mod tests {
121
122    use super::*;
123
124    // Helper
125    fn nodes() -> Vec<Node> {
126        let nodes = Node::from_list(&[(0, 0), (10, 10), (20, 20), (30, 30)]);
127        Node::linked_list(nodes)
128    }
129
130    // Helper
131    fn network() -> Network<Node> {
132        Network::new(nodes())
133    }
134
135    #[test]
136    fn simple_network_shortest_leg() {
137        let network = network();
138        let path = path(&network, "D", "A", &path_shortest_leg).unwrap();
139        assert_eq!(path.len(), 4);
140    }
141
142    #[test]
143    fn simple_network() {
144        let path = network().path("A", "D").unwrap();
145        assert_eq!(path.len(), 4);
146    }
147
148    #[test]
149    fn simple_network_start_in_the_middle() {
150        let path = network().path("C", "D").unwrap();
151        assert_eq!(path.len(), 2);
152    }
153
154    #[test]
155    fn simple_network_end_in_the_middle() {
156        let path = network().path("C", "D").unwrap();
157        assert_eq!(path.len(), 2);
158    }
159
160    #[test]
161    fn simple_networks_have_same_path() {
162        let net = network();
163        let mut path_sl = path(&net, "D", "A", &path_shortest_leg).unwrap();
164        let path = net.path("A", "D").unwrap();
165        path_sl.reverse();
166
167        let f = |&p: &Node| p.geo;
168        let v1 = path.iter().map(f).collect::<Vec<_>>();
169        let v2 = path_sl.iter().map(f).collect::<Vec<_>>();
170
171        assert_eq!(v1, v2);
172    }
173
174    #[test]
175    fn valid_gets() {
176        let network = network();
177        for l in ["A", "B", "C", "D"].iter() {
178            assert!(get(&network, l).is_some());
179        }
180    }
181
182    #[test]
183    fn invalid_gets() {
184        let network = network();
185        for l in ["", "<>", "Test", "E", "AA", "EE", "f", "a"].iter() {
186            assert!(get(&network, l).is_none());
187        }
188    }
189
190    #[test]
191    fn invalid_network_1() {
192        assert!(network().path("B", "E").is_err());
193    }
194
195    #[test]
196    fn invalid_network_2() {
197        assert!(network().path("Testing", "One, two, Three.").is_err());
198    }
199
200    #[test]
201    fn invalid_network_3() {
202        assert!(network().path("", "<").is_err());
203    }
204
205    #[test]
206    fn invalid_network_4() {
207        assert!(network().path("<html>", "{json:test}").is_err());
208    }
209
210}
pathfinder/map/network.rs

pathfinder/map/
network.rs
