terrain_graph/
edge_attributed_undirected.rs

1/// An edge-attributed undirected graph.
2#[derive(Clone)]
3pub struct EdgeAttributedUndirectedGraph<Attr: Copy + Clone + Default> {
4    adjacency_list: Vec<Vec<(usize, Attr)>>,
5    edge_count: usize,
6}
7
8impl<Attr: Copy + Clone + Default> EdgeAttributedUndirectedGraph<Attr> {
9    /// Initialize an empty graph with order vertices.
10    pub fn new(order: usize) -> Self {
11        EdgeAttributedUndirectedGraph {
12            adjacency_list: vec![vec![]; order],
13            edge_count: 0,
14        }
15    }
16
17    /// Add an edge between vertices v and w, with a specified weight.
18    pub fn add_edge(&mut self, v: usize, w: usize, attr: Attr) {
19        self.adjacency_list[v].push((w, attr));
20        self.adjacency_list[w].push((v, attr));
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, Attr) {
33        for &(x, attr) in self.adjacency_list[v].iter() {
34            if x == w {
35                return (true, attr);
36            }
37        }
38        (false, Default::default())
39    }
40
41    /// Return the number of vertices in the graph.
42    pub fn order(&self) -> usize {
43        self.adjacency_list.len()
44    }
45
46    /// Return a reference to the adjacency list of vertex v.
47    pub fn neighbors_of(&self, v: usize) -> &Vec<(usize, Attr)> {
48        self.adjacency_list[v].as_ref()
49    }
50
51    /// Return the number of edges in the graph.
52    pub fn size(&self) -> usize {
53        self.edge_count
54    }
55
56    /// Remove all edges from the graph.
57    pub fn clear(&mut self) {
58        for v in self.adjacency_list.iter_mut() {
59            v.clear();
60        }
61        self.edge_count = 0;
62    }
63
64    /// Return the degree of vertex v.
65    pub fn degree(&self, v: usize) -> usize {
66        self.adjacency_list[v].len()
67    }
68}
terrain_graph/edge_attributed_undirected.rs

terrain_graph/
edge_attributed_undirected.rs
