algograph/graph/undirected/
tree_backed.rs

1use crate::graph::*;
2use std::collections::{BTreeMap, BTreeSet};
3
4/// An undirected graph with balanced computational complexity.
5///
6/// |                    | Complexity                                                                                   |
7/// | ------------------ | -------------------------------------------------------------------------------------------- |
8/// | `add_vertex`       | $O(\log \|V\|)$                                                                              |
9/// | `add_edge`         | $O(\log \|V\| + \log \|E\|)$                                                                 |
10/// | `remove_edge`      | $O(\log \|E\|)$                                                                              |
11/// | `remove_vertex`    | $O(\log \|V\| + \|E'\|)$, where $E'$ is the set of edges connecting to the vertex to remove. |
12/// | `vertex_size`      | $O(1)$                                                                                       |
13/// | `iter_vertices`    | amortized $O(1)$ and $O(\log \|V\|)$ in the worst cases.                                     |
14/// | `contains_vertex`  | $O(\log \|V\|)$                                                                              |
15/// | `edge_size`        | $O(1)$                                                                                       |
16/// | `iter_edges`       | amortized $O(1)$ and $O(\log \|E\|)$ in the worst cases.                                     |
17/// | `contains_edge`    | $O(\log \|E\|)$                                                                              |
18/// | `find_edge`        | $O(\log \|E\|)$                                                                              |
19/// | `edges_connecting` | returns in $O(\log \|E\|)$. amortized $O(1)$ and $O(\log \|E\|)$ in the worst cases on each call to `.next`.|
20/// | `in_edges`         | returns in $O(\log \|E\|)$. amortized $O(1)$ and $O(\log \|E\|)$ in the worst cases on each call to `.next`.|
21/// | `out_edges`        | returns in $O(\log \|E\|)$. amortized $O(1)$ and $O(\log \|E\|)$ in the worst cases on each call to `.next`.|
22#[derive(Clone)]
23pub struct TreeBackedGraph {
24    vid_factory: VertexIdFactory,
25    eid_factory: EdgeIdFactory,
26    vertices: BTreeSet<VertexId>,
27    edges: BTreeMap<EdgeId, (VertexId, VertexId)>,
28    adjacent_edges: BTreeSet<(VertexId, VertexId, EdgeId)>,
29}
30
31impl DirectedOrNot for TreeBackedGraph {
32    const DIRECTED_OR_NOT: bool = false;
33}
34
35impl std::fmt::Debug for TreeBackedGraph {
36    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
37        writeln!(f, "TreeBackedGraph {{")?;
38        for v in self.vertices.iter() {
39            writeln!(f, "{:?}:", v)?;
40            for e in self.out_edges(v) {
41                writeln!(f, "  -> {:?} by {:?}", e.sink, e.id)?;
42            }
43        }
44        writeln!(f, "}}")?;
45        Ok(())
46    }
47}
48
49impl GrowableGraph for TreeBackedGraph {
50    fn new() -> Self {
51        Self {
52            vid_factory: VertexIdFactory::new(),
53            eid_factory: EdgeIdFactory::new(),
54            vertices: BTreeSet::new(),
55            edges: BTreeMap::new(),
56            adjacent_edges: BTreeSet::new(),
57        }
58    }
59
60    fn add_vertex(&mut self) -> VertexId {
61        let vid = self.vid_factory.one_more();
62        self.vertices.insert(vid);
63        vid
64    }
65
66    fn add_edge(&mut self, source: VertexId, sink: VertexId) -> EdgeId {
67        debug_assert!(self.vertices.contains(&source));
68        debug_assert!(self.vertices.contains(&sink));
69        let eid = self.eid_factory.one_more();
70        self.edges.insert(eid, (source, sink));
71        self.adjacent_edges.insert((sink, source, eid));
72        self.adjacent_edges.insert((source, sink, eid));
73        eid
74    }
75}
76
77impl EdgeShrinkableGraph for TreeBackedGraph {
78    fn remove_edge(&mut self, edge: &EdgeId) -> Option<Edge> {
79        match self.edges.remove(edge) {
80            None => None,
81            Some((src, snk)) => {
82                self.adjacent_edges.remove(&(snk, src, *edge));
83                self.adjacent_edges.remove(&(src, snk, *edge));
84                Some(Edge {
85                    id: *edge,
86                    source: src,
87                    sink: snk,
88                })
89            }
90        }
91    }
92}
93
94impl VertexShrinkableGraph for TreeBackedGraph {
95    fn remove_vertex(&mut self, vertex: &VertexId) -> Box<dyn Iterator<Item = Edge> + 'static> {
96        if !self.vertices.remove(vertex) {
97            return Box::new(std::iter::empty());
98        }
99        let start = (*vertex, VertexId::MIN, EdgeId::MIN);
100        let end = (vertex.next(), VertexId::MIN, EdgeId::MIN);
101        let res: BTreeSet<_> = self
102            .adjacent_edges
103            .range(start..end)
104            .map(|(snk, src, edge)| Edge {
105                id: *edge,
106                source: *src,
107                sink: *snk,
108            })
109            .collect();
110        for x in res.iter() {
111            self.remove_edge(&x.id);
112        }
113        Box::new(res.into_iter())
114    }
115}
116
117impl QueryableGraph for TreeBackedGraph {
118    fn vertex_size(&self) -> usize {
119        self.vertices.len()
120    }
121
122    fn iter_vertices(&self) -> Box<dyn Iterator<Item = VertexId> + '_> {
123        Box::new(self.vertices.iter().copied())
124    }
125
126    fn contains_vertex(&self, v: &VertexId) -> bool {
127        self.vertices.contains(v)
128    }
129
130    fn edge_size(&self) -> usize {
131        self.edges.len()
132    }
133
134    fn iter_edges(&self) -> Box<dyn Iterator<Item = Edge> + '_> {
135        Box::new(self.edges.iter().map(|(e, (src, snk))| Edge {
136            id: *e,
137            source: *src,
138            sink: *snk,
139        }))
140    }
141
142    fn contains_edge(&self, e: &EdgeId) -> bool {
143        self.edges.contains_key(e)
144    }
145
146    fn find_edge(&self, e: &EdgeId) -> Option<Edge> {
147        self.edges.get(e).map(|(src, snk)| Edge {
148            id: *e,
149            source: *src,
150            sink: *snk,
151        })
152    }
153
154    fn in_edges(&self, v: &VertexId) -> Box<dyn Iterator<Item = Edge> + '_> {
155        let start = (*v, VertexId::MIN, EdgeId::MIN);
156        let end = (v.next(), VertexId::MIN, EdgeId::MIN);
157        let it = self
158            .adjacent_edges
159            .range(start..end)
160            .map(|(snk, src, e)| Edge {
161                id: *e,
162                source: *src,
163                sink: *snk,
164            });
165        Box::new(it)
166    }
167
168    fn out_edges(&self, v: &VertexId) -> Box<dyn Iterator<Item = Edge> + '_> {
169        let it = self.in_edges(v).map(|e| Edge {
170            id: e.id,
171            source: e.sink,
172            sink: e.source,
173        });
174        Box::new(it)
175    }
176
177    fn edges_connecting<'a, 'b>(
178        &'a self,
179        source: &'b VertexId,
180        sink: &'b VertexId,
181    ) -> Box<dyn Iterator<Item = Edge> + 'a> {
182        let source = *source;
183        let sink = *sink;
184        let start = (source, sink, EdgeId::MIN);
185        let end = (source, sink, EdgeId::MAX);
186        let it = self
187            .adjacent_edges
188            .range(start..=end)
189            .map(move |(_, _, eid)| Edge {
190                id: *eid,
191                source,
192                sink,
193            });
194        Box::new(it)
195    }
196}
197
198#[cfg(test)]
199mod tests {
200    use crate::graph::*;
201    use quickcheck_macros::*;
202
203    #[quickcheck]
204    fn tree_backed_gen(ops: directed::Ops) {
205        let dig: MappedGraph<directed::AdjacentListGraph> = (&ops).into();
206        let oracle: MappedGraph<undirected::AdjacentListGraph> = dig.transform();
207        let trial: MappedGraph<undirected::TreeBackedGraph> = dig.transform();
208        assert_eq!(oracle, trial);
209    }
210}
algograph/graph/undirected/tree_backed.rs

algograph/graph/undirected/
tree_backed.rs
