1use std::marker::PhantomData;
2
3pub trait GraphBase {
4 type VIndex: Copy + Eq;
5}
6pub trait EIndexedGraph: GraphBase {
7 type EIndex: Copy + Eq;
8}
9
10pub trait VertexSize: GraphBase {
11 fn vsize(&self) -> usize;
12}
13pub trait EdgeSize: GraphBase {
14 fn esize(&self) -> usize;
15}
16
17pub trait Vertices: GraphBase {
18 type VIter<'g>: Iterator<Item = Self::VIndex>
19 where
20 Self: 'g;
21 fn vertices(&self) -> Self::VIter<'_>;
22}
23pub trait Edges: EIndexedGraph {
24 type EIter<'g>: Iterator<Item = Self::EIndex>
25 where
26 Self: 'g;
27 fn edges<'g>(&self) -> Self::EIter<'g>;
28}
29
30pub trait AdjacencyIndex {
31 type VIndex: Copy + Eq;
32 fn vindex(&self) -> Self::VIndex;
33}
34pub trait Adjacencies: GraphBase {
35 type AIndex: AdjacencyIndex<VIndex = Self::VIndex>;
36 type AIter<'g>: Iterator<Item = Self::AIndex>
37 where
38 Self: 'g;
39 fn adjacencies(&self, vid: Self::VIndex) -> Self::AIter<'_>;
40}
41
42pub trait AdjacenciesWithEindex: EIndexedGraph {
43 type AIndex: AdjacencyIndexWithEindex<VIndex = Self::VIndex, EIndex = Self::EIndex>;
44 type AIter<'g>: Iterator<Item = Self::AIndex>
45 where
46 Self: 'g;
47 fn adjacencies_with_eindex(&self, vid: Self::VIndex) -> Self::AIter<'_>;
48}
49pub trait AdjacencyIndexWithEindex: AdjacencyIndex {
50 type EIndex: Copy + Eq;
51 fn eindex(&self) -> Self::EIndex;
52}
53
54pub trait AdjacencyIndexWithValue: AdjacencyIndex {
55 type AValue: Clone;
56 fn avalue(&self) -> Self::AValue;
57}
58pub trait AdjacenciesWithValue<T>: GraphBase
59where
60 T: Clone,
61{
62 type AIndex: AdjacencyIndexWithValue<VIndex = Self::VIndex, AValue = T>;
63 type AIter<'g>: Iterator<Item = Self::AIndex>
64 where
65 Self: 'g;
66 fn adjacencies_with_value(&self, vid: Self::VIndex) -> Self::AIter<'_>;
67}
68
69impl AdjacencyIndex for usize {
70 type VIndex = usize;
71 fn vindex(&self) -> Self::VIndex {
72 *self
73 }
74}
75impl<V, E> AdjacencyIndex for (V, E)
76where
77 V: Copy + Eq,
78 E: Copy + Eq,
79{
80 type VIndex = V;
81 fn vindex(&self) -> Self::VIndex {
82 self.0
83 }
84}
85impl<V, E> AdjacencyIndexWithEindex for (V, E)
86where
87 V: Copy + Eq,
88 E: Copy + Eq,
89{
90 type EIndex = E;
91 fn eindex(&self) -> Self::EIndex {
92 self.1
93 }
94}
95
96#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
97pub struct VIndex<V>(V);
98#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
99pub struct VIndexWithEIndex<V, E>(V, E);
100#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
101pub struct VIndexWithValue<V, T>(V, T);
102#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
103pub struct VIndexWithEIndexValue<V, E, T>(V, E, T);
104
105impl<V> AdjacencyIndex for VIndex<V>
106where
107 V: Eq + Copy,
108{
109 type VIndex = V;
110 fn vindex(&self) -> Self::VIndex {
111 self.0
112 }
113}
114impl<V, E> AdjacencyIndex for VIndexWithEIndex<V, E>
115where
116 V: Eq + Copy,
117{
118 type VIndex = V;
119 fn vindex(&self) -> Self::VIndex {
120 self.0
121 }
122}
123impl<V, E> AdjacencyIndexWithEindex for VIndexWithEIndex<V, E>
124where
125 V: Eq + Copy,
126 E: Eq + Copy,
127{
128 type EIndex = E;
129 fn eindex(&self) -> Self::EIndex {
130 self.1
131 }
132}
133impl<V, T> AdjacencyIndex for VIndexWithValue<V, T>
134where
135 V: Eq + Copy,
136{
137 type VIndex = V;
138 fn vindex(&self) -> Self::VIndex {
139 self.0
140 }
141}
142impl<V, T> AdjacencyIndexWithValue for VIndexWithValue<V, T>
143where
144 V: Eq + Copy,
145 T: Clone,
146{
147 type AValue = T;
148 fn avalue(&self) -> Self::AValue {
149 self.1.clone()
150 }
151}
152impl<V, E, T> AdjacencyIndex for VIndexWithEIndexValue<V, E, T>
153where
154 V: Eq + Copy,
155{
156 type VIndex = V;
157 fn vindex(&self) -> Self::VIndex {
158 self.0
159 }
160}
161impl<V, E, T> AdjacencyIndexWithEindex for VIndexWithEIndexValue<V, E, T>
162where
163 V: Eq + Copy,
164 E: Eq + Copy,
165{
166 type EIndex = E;
167 fn eindex(&self) -> Self::EIndex {
168 self.1
169 }
170}
171impl<V, E, T> AdjacencyIndexWithValue for VIndexWithEIndexValue<V, E, T>
172where
173 V: Eq + Copy,
174 T: Clone,
175{
176 type AValue = T;
177 fn avalue(&self) -> Self::AValue {
178 self.2.clone()
179 }
180}
181impl<V> From<V> for VIndex<V> {
182 fn from(vid: V) -> Self {
183 VIndex(vid)
184 }
185}
186impl<V, E> From<(V, E)> for VIndexWithEIndex<V, E> {
187 fn from((vid, eid): (V, E)) -> Self {
188 VIndexWithEIndex(vid, eid)
189 }
190}
191impl<V, T> From<(V, T)> for VIndexWithValue<V, T> {
192 fn from((vid, value): (V, T)) -> Self {
193 VIndexWithValue(vid, value)
194 }
195}
196impl<V, E, T> From<(V, E, T)> for VIndexWithEIndexValue<V, E, T> {
197 fn from((vid, eid, value): (V, E, T)) -> Self {
198 VIndexWithEIndexValue(vid, eid, value)
199 }
200}
201impl<V, T> VIndexWithValue<V, T> {
202 pub fn map<U, F>(self, mut f: F) -> VIndexWithValue<V, U>
203 where
204 F: FnMut(T) -> U,
205 {
206 VIndexWithValue(self.0, f(self.1))
207 }
208}
209impl<V, E, T> VIndexWithEIndexValue<V, E, T> {
210 pub fn map<U, F>(self, mut f: F) -> VIndexWithEIndexValue<V, E, U>
211 where
212 F: FnMut(T) -> U,
213 {
214 VIndexWithEIndexValue(self.0, self.1, f(self.2))
215 }
216}
217
218pub trait VertexMap<T>: GraphBase {
219 type Vmap;
220 fn construct_vmap<F>(&self, f: F) -> Self::Vmap
221 where
222 F: FnMut() -> T;
223 fn vmap_get<'a>(&self, map: &'a Self::Vmap, vid: Self::VIndex) -> &'a T;
224 fn vmap_get_mut<'a>(&self, map: &'a mut Self::Vmap, vid: Self::VIndex) -> &'a mut T;
225 fn vmap_set(&self, map: &mut Self::Vmap, vid: Self::VIndex, x: T) {
226 *self.vmap_get_mut(map, vid) = x;
227 }
228}
229pub trait VertexView<M, T>: GraphBase
230where
231 M: ?Sized,
232{
233 fn vview(&self, map: &M, vid: Self::VIndex) -> T;
234}
235pub trait EdgeMap<T>: EIndexedGraph {
236 type Emap;
237 fn construct_emap<F>(&self, f: F) -> Self::Emap
238 where
239 F: FnMut() -> T;
240 fn emap_get<'a>(&self, map: &'a Self::Emap, eid: Self::EIndex) -> &'a T;
241 fn emap_get_mut<'a>(&self, map: &'a mut Self::Emap, eid: Self::EIndex) -> &'a mut T;
242 fn emap_set(&self, map: &mut Self::Emap, eid: Self::EIndex, x: T) {
243 *self.emap_get_mut(map, eid) = x;
244 }
245}
246pub trait EdgeView<M, T>: EIndexedGraph
247where
248 M: ?Sized,
249{
250 fn eview(&self, map: &M, eid: Self::EIndex) -> T;
251}
252
253impl<G, F, T> VertexView<F, T> for G
254where
255 G: GraphBase,
256 F: Fn(Self::VIndex) -> T,
257{
258 fn vview(&self, map: &F, vid: Self::VIndex) -> T {
259 (map)(vid)
260 }
261}
262impl<G, F, T> EdgeView<F, T> for G
263where
264 G: EIndexedGraph,
265 F: Fn(Self::EIndex) -> T,
266{
267 fn eview(&self, map: &F, eid: Self::EIndex) -> T {
268 (map)(eid)
269 }
270}
271
272pub trait AdjacencyView<'a, M, T>: GraphBase
273where
274 M: ?Sized,
275{
276 type AViewIter<'g>: Iterator<Item = VIndexWithValue<Self::VIndex, T>>
277 where
278 M: 'a,
279 Self: 'g;
280 fn aviews<'g>(&'g self, map: &'a M, vid: Self::VIndex) -> Self::AViewIter<'g>;
281}
282
283pub struct AdjacencyViewIterFromEindex<'g, 'a, G, M, T>
284where
285 G: AdjacenciesWithEindex,
286{
287 iter: G::AIter<'g>,
288 g: &'g G,
289 map: &'a M,
290 _marker: PhantomData<fn() -> T>,
291}
292impl<'g, 'a, G, M, T> AdjacencyViewIterFromEindex<'g, 'a, G, M, T>
293where
294 G: AdjacenciesWithEindex,
295{
296 pub fn new(iter: G::AIter<'g>, g: &'g G, map: &'a M) -> Self {
297 Self {
298 iter,
299 g,
300 map,
301 _marker: PhantomData,
302 }
303 }
304}
305impl<'a, G, M, T> Iterator for AdjacencyViewIterFromEindex<'_, 'a, G, M, T>
306where
307 G: AdjacenciesWithEindex + EdgeView<M, T>,
308 M: 'a,
309{
310 type Item = VIndexWithValue<G::VIndex, T>;
311 fn next(&mut self) -> Option<Self::Item> {
312 self.iter
313 .next()
314 .map(|adj| (adj.vindex(), self.g.eview(self.map, adj.eindex())).into())
315 }
316}
317
318pub struct AdjacencyViewIterFromValue<'g, 'a, G, M, T, U>
319where
320 G: 'g + AdjacenciesWithValue<T>,
321 T: Clone,
322{
323 iter: G::AIter<'g>,
324 map: &'a M,
325 _marker: PhantomData<fn() -> U>,
326}
327impl<'g, 'a, G, M, T, U> AdjacencyViewIterFromValue<'g, 'a, G, M, T, U>
328where
329 G: AdjacenciesWithValue<T>,
330 T: Clone,
331{
332 pub fn new(iter: G::AIter<'g>, map: &'a M) -> Self {
333 Self {
334 iter,
335 map,
336 _marker: PhantomData,
337 }
338 }
339}
340impl<'a, G, M, T, U> Iterator for AdjacencyViewIterFromValue<'_, 'a, G, M, T, U>
341where
342 G: AdjacenciesWithValue<T>,
343 T: Clone,
344 M: 'a + Fn(T) -> U,
345{
346 type Item = VIndexWithValue<G::VIndex, U>;
347 fn next(&mut self) -> Option<Self::Item> {
348 self.iter
349 .next()
350 .map(|adj| (adj.vindex(), (self.map)(adj.avalue())).into())
351 }
352}