terrain_graph/
edge_attributed_directed.rs

1/// An edge-attributed directed graph.
2#[derive(Clone)]
3pub struct EdgeAttributedDirectedGraph<Attr: Copy + Clone + Default> {
4    adjacency_list: Vec<Vec<(usize, Attr)>>,
5    edge_count: usize,
6}
7
8impl<Attr: Copy + Clone + Default> EdgeAttributedDirectedGraph<Attr> {
9    /// Initialize an empty graph with order vertices.
10    pub fn new(order: usize) -> Self {
11        EdgeAttributedDirectedGraph {
12            adjacency_list: vec![vec![]; order],
13            edge_count: 0,
14        }
15    }
16
17    /// Add an edge from vertex v to vertex w, with a specified attribute.
18    pub fn add_edge(&mut self, v: usize, w: usize, attr: Attr) {
19        self.adjacency_list[v].push((w, attr));
20        self.edge_count += 1;
21    }
22
23    /// Remove the edge from vertex v to vertex w.
24    pub fn delete_edge(&mut self, v: usize, w: usize) {
25        self.adjacency_list[v].retain(|&(x, _)| x != w);
26        self.edge_count -= 1;
27    }
28
29    /// Check if there is an edge from vertex v to vertex w.
30    pub fn has_edge(&self, v: usize, w: usize) -> (bool, Attr) {
31        for &(x, attr) in self.adjacency_list[v].iter() {
32            if x == w {
33                return (true, attr);
34            }
35        }
36        (false, Default::default())
37    }
38
39    /// Return the number of vertices in the graph.
40    pub fn order(&self) -> usize {
41        self.adjacency_list.len()
42    }
43
44    /// Return a reference to the adjacency list of vertex v.
45    pub fn neighbors_of(&self, v: usize) -> &Vec<(usize, Attr)> {
46        self.adjacency_list[v].as_ref()
47    }
48
49    /// Return the number of edges in the graph.
50    pub fn size(&self) -> usize {
51        self.edge_count
52    }
53
54    /// Remove all edges from the graph.
55    pub fn clear(&mut self) {
56        for v in self.adjacency_list.iter_mut() {
57            v.clear();
58        }
59        self.edge_count = 0;
60    }
61
62    /// Return the out-degree of vertex v.
63    pub fn outdegree(&self, v: usize) -> usize {
64        self.adjacency_list[v].len()
65    }
66
67    /// Return the in-degree of vertex v.
68    ///
69    /// Note: This requires O(|V| + |E|) time to compute.
70    pub fn indegree(&self, v: usize) -> usize {
71        self.adjacency_list
72            .iter()
73            .filter(|&adj| adj.iter().any(|&(x, _)| x == v))
74            .count()
75    }
76}
terrain_graph/edge_attributed_directed.rs

terrain_graph/
edge_attributed_directed.rs
