algograph/tagged/
naive_impl.rs

1use crate::graph::*;
2use crate::tagged::traits::{GrowableTaggedGraph, TaggedGraph};
3use ahash::RandomState;
4use bimap::BiHashMap;
5use std::hash::Hash;
6
7/// A naive implementation of tagged graphs.
8#[derive(Clone)]
9pub struct NaiveTaggedGraph<V, E, G = directed::TreeBackedGraph>
10where
11    V: Hash + Eq + Clone,
12    E: Hash + Eq + Clone,
13{
14    lower_graph: G,
15    vertices: BiHashMap<VertexId, V, RandomState, RandomState>,
16    edges: BiHashMap<EdgeId, E, RandomState, RandomState>,
17}
18
19impl<V, E, G> DirectedOrNot for NaiveTaggedGraph<V, E, G>
20where
21    V: Hash + Eq + Clone,
22    E: Hash + Eq + Clone,
23    G: DirectedOrNot,
24{
25    const DIRECTED_OR_NOT: bool = G::DIRECTED_OR_NOT;
26}
27
28impl<V, E, G> Default for NaiveTaggedGraph<V, E, G>
29where
30    V: Hash + Eq + Clone,
31    E: Hash + Eq + Clone + super::Edge,
32    G: GrowableGraph,
33{
34    fn default() -> Self {
35        Self::new()
36    }
37}
38
39impl<V, E, G> super::TaggedGraph for NaiveTaggedGraph<V, E, G>
40where
41    V: Hash + Eq + Clone,
42    E: Hash + Eq + Clone + super::Edge,
43{
44    type LowerGraph = G;
45    type Vertex = V;
46    type Edge = E;
47
48    fn lower_graph(&self) -> &Self::LowerGraph {
49        &self.lower_graph
50    }
51
52    fn vertex_by_id(&self, vid: &VertexId) -> Option<&Self::Vertex> {
53        self.vertices.get_by_left(vid)
54    }
55
56    fn id_by_vertex(&self, vert: &Self::Vertex) -> Option<VertexId> {
57        self.vertices.get_by_right(vert).copied()
58    }
59
60    fn edge_by_id(&self, eid: &EdgeId) -> Option<&Self::Edge> {
61        self.edges.get_by_left(eid)
62    }
63
64    fn id_by_edge(&self, edge: &Self::Edge) -> Option<EdgeId> {
65        self.edges.get_by_right(edge).copied()
66    }
67}
68
69impl<V, E, G> super::GrowableTaggedGraph for NaiveTaggedGraph<V, E, G>
70where
71    V: Hash + Eq + Clone,
72    E: Hash + Eq + Clone + super::Edge,
73    G: GrowableGraph,
74{
75    fn new() -> Self {
76        Self {
77            lower_graph: G::new(),
78            vertices: BiHashMap::with_hashers(RandomState::new(), RandomState::new()),
79            edges: BiHashMap::with_hashers(RandomState::new(), RandomState::new()),
80        }
81    }
82
83    fn overwrite_vertex(&mut self, vert: Self::Vertex) -> VertexId {
84        if let Some((vid, _)) = self.vertices.remove_by_right(&vert) {
85            self.vertices.insert(vid, vert);
86            vid
87        } else {
88            let vid = self.lower_graph.add_vertex();
89            self.vertices.insert(vid, vert);
90            vid
91        }
92    }
93
94    fn add_edge(&mut self, edge: Self::Edge) -> EdgeId {
95        let vid_src = edge.source();
96        let vid_snk = edge.sink();
97        let eid = self.lower_graph.add_edge(vid_src, vid_snk);
98        self.edges.insert(eid, edge);
99        eid
100    }
101
102    fn update_edge(&mut self, eid: EdgeId, new: Self::Edge) {
103        {
104            let old = self.edge_by_id(&eid).unwrap();
105            assert_eq!(old.source(), new.source());
106            assert_eq!(old.sink(), new.sink());
107        }
108        let _ = self.edges.insert(eid, new);
109    }
110}
111
112impl<V, E, G> super::EdgeShrinkableTaggedGraph for NaiveTaggedGraph<V, E, G>
113where
114    V: Hash + Eq + Clone,
115    E: Hash + Eq + Clone + super::Edge,
116    G: EdgeShrinkableGraph,
117{
118    fn remove_edge(&mut self, eid: &EdgeId) -> Option<Self::Edge> {
119        self.lower_graph
120            .remove_edge(eid)
121            .and_then(|_| self.edges.remove_by_left(eid))
122            .map(|(_, e)| e)
123    }
124}
125
126impl<V, E, G> super::VertexShrinkableTaggedGraph for NaiveTaggedGraph<V, E, G>
127where
128    V: Hash + Eq + Clone,
129    E: Hash + Eq + Clone + super::Edge,
130    G: VertexShrinkableGraph,
131{
132    fn remove_vertex(
133        &mut self,
134        vid: &VertexId,
135    ) -> Box<dyn Iterator<Item = (EdgeId, Self::Edge)> + '_> {
136        if self.vertices.remove_by_left(vid).is_some() {
137            let eids: Vec<_> = self.lower_graph.remove_vertex(vid).map(|e| e.id).collect();
138            let res: Vec<_> = eids
139                .iter()
140                .map(|eid| self.edges.remove_by_left(eid).unwrap())
141                .collect();
142            Box::new(res.into_iter())
143        } else {
144            Box::new(std::iter::empty())
145        }
146    }
147}
148
149impl<V, E, G> super::QueryableTaggedGraph for NaiveTaggedGraph<V, E, G>
150where
151    V: Hash + Eq + Clone,
152    E: Hash + Eq + Clone + super::Edge,
153    G: QueryableGraph,
154{
155    fn vertex_size(&self) -> usize {
156        self.vertices.len()
157    }
158
159    fn iter_vertices(&self) -> Box<dyn Iterator<Item = (VertexId, &Self::Vertex)> + '_> {
160        let it = self
161            .lower_graph
162            .iter_vertices()
163            .map(|vid| (vid, self.vertex_by_id(&vid).unwrap()));
164        Box::new(it)
165    }
166
167    fn edge_size(&self) -> usize {
168        self.edges.len()
169    }
170
171    fn iter_edges(&self) -> Box<dyn Iterator<Item = (crate::graph::Edge, &Self::Edge)> + '_> {
172        let it = self.lower_graph.iter_edges().map(|e| {
173            let upper_edge = self.edge_by_id(&e.id).unwrap();
174            (e, upper_edge)
175        });
176        Box::new(it)
177    }
178
179    fn edges_connecting(
180        &self,
181        source: &VertexId,
182        sink: &VertexId,
183    ) -> Box<dyn Iterator<Item = (crate::graph::Edge, &Self::Edge)> + '_> {
184        let it = self.lower_graph.edges_connecting(source, sink).map(|e| {
185            let upper_edge = self.edge_by_id(&e.id).unwrap();
186            (e, upper_edge)
187        });
188        Box::new(it)
189    }
190
191    fn in_edges(
192        &self,
193        vid: &VertexId,
194    ) -> Box<dyn Iterator<Item = (crate::graph::Edge, &Self::Edge)> + '_> {
195        let it = self.lower_graph.in_edges(vid).map(|e| {
196            let upper_edge = self.edge_by_id(&e.id).unwrap();
197            (e, upper_edge)
198        });
199        Box::new(it)
200    }
201
202    fn out_edges(
203        &self,
204        vid: &VertexId,
205    ) -> Box<dyn Iterator<Item = (crate::graph::Edge, &Self::Edge)> + '_> {
206        let it = self.lower_graph.out_edges(vid).map(|e| {
207            let upper_edge = self.edge_by_id(&e.id).unwrap();
208            (e, upper_edge)
209        });
210        Box::new(it)
211    }
212}
algograph/tagged/naive_impl.rs

algograph/tagged/
naive_impl.rs
