terrain_graph/
undirected.rs

1/// An undirected graph.
2#[derive(Clone)]
3pub struct UndirectedGraph {
4    adjacency_list: Vec<Vec<usize>>,
5    edge_count: usize,
6}
7
8impl UndirectedGraph {
9    /// Initialize an empty graph with order vertices.
10    pub fn new(order: usize) -> Self {
11        UndirectedGraph {
12            adjacency_list: vec![vec![]; order],
13            edge_count: 0,
14        }
15    }
16
17    /// Add an edge between vertices v and w.
18    pub fn add_edge(&mut self, v: usize, w: usize) {
19        self.adjacency_list[v].push(w);
20        self.adjacency_list[w].push(v);
21        self.edge_count += 1;
22    }
23
24    /// Remove the edge between vertices v and w.
25    pub fn delete_edge(&mut self, v: usize, w: usize) {
26        self.adjacency_list[v].retain(|&x| x != w);
27        self.adjacency_list[w].retain(|&x| x != v);
28        self.edge_count -= 1;
29    }
30
31    /// Check if there is an edge between vertices v and w.
32    pub fn has_edge(&self, v: usize, w: usize) -> bool {
33        self.adjacency_list[v].contains(&w)
34    }
35
36    /// Return the number of vertices in the graph.
37    pub fn order(&self) -> usize {
38        self.adjacency_list.len()
39    }
40
41    /// Return a reference to the adjacency list of vertex v.
42    pub fn neighbors_of(&self, v: usize) -> &Vec<usize> {
43        self.adjacency_list[v].as_ref()
44    }
45
46    /// Return the number of edges in the graph.
47    pub fn size(&self) -> usize {
48        self.edge_count
49    }
50
51    /// Remove all edges from the graph.
52    pub fn clear(&mut self) {
53        for v in self.adjacency_list.iter_mut() {
54            v.clear();
55        }
56        self.edge_count = 0;
57    }
58
59    /// Return the degree of vertex v.
60    pub fn degree(&self, v: usize) -> usize {
61        self.adjacency_list[v].len()
62    }
63}
terrain_graph/undirected.rs

terrain_graph/
undirected.rs
