contest_algorithms/graph/
mod.rs

1//! Basic graph module without explicit support for deletion.
2//!
3//! # Panics
4//!
5//! All methods will panic if given an out-of-bounds element index.
6pub mod connectivity;
7pub mod flow;
8pub mod util;
9
10/// Represents a union of disjoint sets. Each set's elements are arranged in a
11/// tree, whose root is the set's representative.
12pub struct DisjointSets {
13    parent: Vec<usize>,
14}
15
16impl DisjointSets {
17    /// Initializes disjoint sets containing one element each.
18    pub fn new(size: usize) -> Self {
19        Self {
20            parent: (0..size).collect(),
21        }
22    }
23
24    /// Finds the set's representative. Do path compression along the way to make
25    /// future queries faster.
26    pub fn find(&mut self, u: usize) -> usize {
27        let pu = self.parent[u];
28        if pu != u {
29            self.parent[u] = self.find(pu);
30        }
31        self.parent[u]
32    }
33
34    /// Merges the sets containing u and v into a single set containing their
35    /// union. Returns true if u and v were previously in different sets.
36    pub fn merge(&mut self, u: usize, v: usize) -> bool {
37        let (pu, pv) = (self.find(u), self.find(v));
38        self.parent[pu] = pv;
39        pu != pv
40    }
41}
42
43/// A compact graph representation. Edges are numbered in order of insertion.
44/// Each adjacency list consists of all edges pointing out from a given vertex.
45pub struct Graph {
46    /// Maps a vertex id to the first edge in its adjacency list.
47    first: Vec<Option<usize>>,
48    /// Maps an edge id to the next edge in the same adjacency list.
49    next: Vec<Option<usize>>,
50    /// Maps an edge id to the vertex that it points to.
51    endp: Vec<usize>,
52}
53
54impl Graph {
55    /// Initializes a graph with vmax vertices and no edges. To reduce
56    /// unnecessary allocations, emax_hint should be close to the number of
57    /// edges that will be inserted.
58    pub fn new(vmax: usize, emax_hint: usize) -> Self {
59        Self {
60            first: vec![None; vmax],
61            next: Vec::with_capacity(emax_hint),
62            endp: Vec::with_capacity(emax_hint),
63        }
64    }
65
66    /// Returns the number of vertices.
67    pub fn num_v(&self) -> usize {
68        self.first.len()
69    }
70
71    /// Returns the number of edges, double-counting undirected edges.
72    pub fn num_e(&self) -> usize {
73        self.endp.len()
74    }
75
76    /// Adds a directed edge from u to v.
77    pub fn add_edge(&mut self, u: usize, v: usize) {
78        self.next.push(self.first[u]);
79        self.first[u] = Some(self.num_e());
80        self.endp.push(v);
81    }
82
83    /// An undirected edge is two directed edges. If edges are added only via
84    /// this funcion, the reverse of any edge e can be found at e^1.
85    pub fn add_undirected_edge(&mut self, u: usize, v: usize) {
86        self.add_edge(u, v);
87        self.add_edge(v, u);
88    }
89
90    /// If we think of each even-numbered vertex as a variable, and its
91    /// odd-numbered successor as its negation, then we can build the
92    /// implication graph corresponding to any 2-CNF formula.
93    /// Note that u||v == !u -> v == !v -> u.
94    pub fn add_two_sat_clause(&mut self, u: usize, v: usize) {
95        self.add_edge(u ^ 1, v);
96        self.add_edge(v ^ 1, u);
97    }
98
99    /// Gets vertex u's adjacency list.
100    pub fn adj_list(&self, u: usize) -> AdjListIterator {
101        AdjListIterator {
102            graph: self,
103            next_e: self.first[u],
104        }
105    }
106}
107
108/// An iterator for convenient adjacency list traversal.
109pub struct AdjListIterator<'a> {
110    graph: &'a Graph,
111    next_e: Option<usize>,
112}
113
114impl<'a> Iterator for AdjListIterator<'a> {
115    type Item = (usize, usize);
116
117    /// Produces an outgoing edge and vertex.
118    fn next(&mut self) -> Option<Self::Item> {
119        self.next_e.map(|e| {
120            let v = self.graph.endp[e];
121            self.next_e = self.graph.next[e];
122            (e, v)
123        })
124    }
125}
126
127#[cfg(test)]
128mod test {
129    use super::*;
130
131    #[test]
132    fn test_adj_list() {
133        let mut graph = Graph::new(5, 6);
134        graph.add_edge(2, 3);
135        graph.add_edge(2, 4);
136        graph.add_edge(4, 1);
137        graph.add_edge(1, 2);
138        graph.add_undirected_edge(0, 2);
139
140        let adj = graph.adj_list(2).collect::<Vec<_>>();
141
142        assert_eq!(adj, vec![(5, 0), (1, 4), (0, 3)]);
143        for (e, v) in adj {
144            assert_eq!(v, graph.endp[e]);
145        }
146    }
147}
contest_algorithms/graph/mod.rs

contest_algorithms/graph/
mod.rs
