walky/
preconditions.rs

1//! This module defines functions that evaluate,
2//! if certain conditions hold on a given graph.
3use std::collections::HashSet;
4
5use crate::datastructures::Graph;
6
7/// This function checks whether the graph is fully connected.
8/// This is a prerequisite for the TSP.
9pub fn is_fully_connected(g: &Graph) -> bool {
10    let n = g.num_vertices();
11    g.iter().all(|v| v.degree() == n - 1)
12}
13
14/// This function checks that whether the graph has multiple edges from one vertex to another
15pub fn is_multi_edge(graph: &Graph) -> bool {
16    graph.vertices.iter().any(|vertex| {
17        let destinations: Vec<usize> = vertex.edges.iter().map(|edge| edge.to).collect();
18        let unique_destinations: Vec<usize> = destinations
19            .clone()
20            .into_iter()
21            .collect::<HashSet<_>>()
22            .into_iter()
23            .collect();
24        destinations.len() != unique_destinations.len()
25    })
26}
27
28/// This function verifies that the graph is actual undirected, i.e. the weights are the same for
29/// both directions.
30pub fn is_undirected(graph: &Graph) -> bool {
31    for i in 0..graph.num_vertices() {
32        let v1 = &graph.vertices[i];
33        for v1e in v1.iter() {
34            // Find the Vertex connected to the edge
35            let v2 = &graph.vertices[v1e.to];
36
37            // Find reverse edge link
38            for v2e in v2.iter() {
39                if v2e.to == i {
40                    // If not same weight => directed graph
41                    if v2e.cost != v1e.cost {
42                        return false;
43                    }
44                    break;
45                }
46            }
47        }
48    }
49    true
50}
51
52#[cfg(test)]
53mod test_preconditions {
54    use super::*;
55    use crate::datastructures::{Edge, Vertex};
56
57    #[test]
58    fn test_fully_connected_graph() {
59        let graph = Graph {
60            vertices: vec![
61                Vertex {
62                    edges: vec![
63                        Edge { to: 1, cost: 0.0 },
64                        Edge { to: 2, cost: 0.0 },
65                        Edge { to: 3, cost: 0.0 },
66                    ],
67                },
68                Vertex {
69                    edges: vec![
70                        Edge { to: 0, cost: 0.0 },
71                        Edge { to: 2, cost: 0.0 },
72                        Edge { to: 3, cost: 0.0 },
73                    ],
74                },
75                Vertex {
76                    edges: vec![
77                        Edge { to: 0, cost: 0.0 },
78                        Edge { to: 1, cost: 0.0 },
79                        Edge { to: 3, cost: 0.0 },
80                    ],
81                },
82                Vertex {
83                    edges: vec![
84                        Edge { to: 0, cost: 0.0 },
85                        Edge { to: 1, cost: 0.0 },
86                        Edge { to: 2, cost: 0.0 },
87                    ],
88                },
89            ],
90        };
91        assert!(is_fully_connected(&graph))
92    }
93
94    #[test]
95    fn test_not_fully_connected_graph() {
96        let graph = Graph {
97            vertices: vec![
98                Vertex {
99                    edges: vec![
100                        Edge { to: 1, cost: 0.0 },
101                        Edge { to: 2, cost: 0.0 },
102                        Edge { to: 3, cost: 0.0 },
103                    ],
104                },
105                Vertex {
106                    edges: vec![Edge { to: 2, cost: 0.0 }, Edge { to: 3, cost: 0.0 }],
107                },
108                Vertex {
109                    edges: vec![
110                        Edge { to: 0, cost: 0.0 },
111                        Edge { to: 1, cost: 0.0 },
112                        Edge { to: 3, cost: 0.0 },
113                    ],
114                },
115                Vertex {
116                    edges: vec![
117                        Edge { to: 0, cost: 0.0 },
118                        Edge { to: 1, cost: 0.0 },
119                        Edge { to: 2, cost: 0.0 },
120                    ],
121                },
122            ],
123        };
124        assert!(!is_fully_connected(&graph));
125    }
126
127    #[test]
128    fn test_not_multi_edge() {
129        let graph = Graph {
130            vertices: vec![
131                Vertex {
132                    edges: vec![
133                        Edge { to: 1, cost: 0.0 },
134                        Edge { to: 2, cost: 0.0 },
135                        Edge { to: 3, cost: 0.0 },
136                    ],
137                },
138                Vertex {
139                    edges: vec![
140                        Edge { to: 0, cost: 0.0 },
141                        Edge { to: 2, cost: 0.0 },
142                        Edge { to: 3, cost: 0.0 },
143                    ],
144                },
145                Vertex {
146                    edges: vec![
147                        Edge { to: 0, cost: 0.0 },
148                        Edge { to: 1, cost: 0.0 },
149                        Edge { to: 3, cost: 0.0 },
150                    ],
151                },
152                Vertex {
153                    edges: vec![
154                        Edge { to: 0, cost: 0.0 },
155                        Edge { to: 1, cost: 0.0 },
156                        Edge { to: 2, cost: 0.0 },
157                    ],
158                },
159            ],
160        };
161        assert!(!is_multi_edge(&graph))
162    }
163
164    #[test]
165    fn test_is_multi_edge() {
166        let graph = Graph {
167            vertices: vec![
168                Vertex {
169                    edges: vec![
170                        Edge { to: 1, cost: 0.0 },
171                        Edge { to: 2, cost: 0.0 },
172                        Edge { to: 1, cost: 0.0 },
173                    ],
174                },
175                Vertex {
176                    edges: vec![
177                        Edge { to: 0, cost: 0.0 },
178                        Edge { to: 2, cost: 0.0 },
179                        Edge { to: 3, cost: 0.0 },
180                    ],
181                },
182                Vertex {
183                    edges: vec![
184                        Edge { to: 0, cost: 0.0 },
185                        Edge { to: 1, cost: 0.0 },
186                        Edge { to: 3, cost: 0.0 },
187                    ],
188                },
189                Vertex {
190                    edges: vec![
191                        Edge { to: 0, cost: 0.0 },
192                        Edge { to: 1, cost: 0.0 },
193                        Edge { to: 2, cost: 0.0 },
194                    ],
195                },
196            ],
197        };
198        assert!(is_multi_edge(&graph))
199    }
200
201    #[test]
202    fn test_undirected() {
203        let graph = Graph {
204            vertices: vec![
205                Vertex {
206                    edges: vec![
207                        Edge { to: 1, cost: 5.0 },
208                        Edge { to: 2, cost: 0.0 },
209                        Edge { to: 3, cost: 7.5 },
210                    ],
211                },
212                Vertex {
213                    edges: vec![
214                        Edge { to: 0, cost: 5.0 },
215                        Edge { to: 2, cost: 0.0 },
216                        Edge { to: 3, cost: 0.0 },
217                    ],
218                },
219                Vertex {
220                    edges: vec![
221                        Edge { to: 0, cost: 0.0 },
222                        Edge { to: 1, cost: 0.0 },
223                        Edge { to: 3, cost: 0.0 },
224                    ],
225                },
226                Vertex {
227                    edges: vec![
228                        Edge { to: 0, cost: 7.5 },
229                        Edge { to: 1, cost: 0.0 },
230                        Edge { to: 2, cost: 0.0 },
231                    ],
232                },
233            ],
234        };
235        assert!(is_undirected(&graph))
236    }
237
238    #[test]
239    fn test_not_undirected() {
240        let graph = Graph {
241            vertices: vec![
242                Vertex {
243                    edges: vec![
244                        Edge { to: 1, cost: 0.0 },
245                        Edge { to: 2, cost: 0.0 },
246                        Edge { to: 3, cost: 0.0 },
247                    ],
248                },
249                Vertex {
250                    edges: vec![
251                        Edge { to: 0, cost: 0.0 },
252                        Edge { to: 2, cost: 5.0 },
253                        Edge { to: 3, cost: 0.0 },
254                    ],
255                },
256                Vertex {
257                    edges: vec![
258                        Edge { to: 0, cost: 0.0 },
259                        Edge { to: 1, cost: 4.0 },
260                        Edge { to: 3, cost: 0.0 },
261                    ],
262                },
263                Vertex {
264                    edges: vec![
265                        Edge { to: 0, cost: 0.0 },
266                        Edge { to: 1, cost: 0.0 },
267                        Edge { to: 2, cost: 0.0 },
268                    ],
269                },
270            ],
271        };
272        assert!(!is_undirected(&graph))
273    }
274}
walky/preconditions.rs

walky/
preconditions.rs
