fera_graph/graphs/
complete.rs

1// This Source Code Form is subject to the terms of the Mozilla Public
2// License, v. 2.0. If a copy of the MPL was not distributed with this
3// file, You can obtain one at http://mozilla.org/MPL/2.0/.
4
5use choose::Choose;
6use prelude::*;
7use props::{VecEdgeProp, VecVertexProp};
8
9use fera_optional::{BuildNone, OptionalMax, Optioned};
10
11use std::cmp::Ordering;
12use std::hash::{Hash, Hasher};
13use std::iter::Map;
14use std::marker::PhantomData;
15use std::ops::Range;
16
17use rand::Rng;
18
19// TODO: make vertex and edge type parameters (unsigned integer)
20
21pub type CompleteGraph = Complete<Undirected>;
22
23pub type CompleteDigraph = Complete<Directed>;
24
25pub type CVertex = u32;
26
27#[derive(Copy, Clone, PartialEq, Eq, Debug)]
28pub struct Complete<K: CompleteEdgeKind> {
29    n: CVertex,
30    _marker: PhantomData<K>,
31}
32
33impl<K: CompleteEdgeKind> Complete<K> {
34    pub fn new(n: CVertex) -> Self {
35        Complete {
36            n: n,
37            _marker: PhantomData,
38        }
39    }
40}
41
42pub trait CompleteEdgeKind: UniformEdgeKind {
43    type Edge: 'static + GraphItem + EdgeImpl;
44}
45
46pub trait EdgeImpl {
47    fn from_index(index: usize) -> Self;
48    fn to_index(self) -> usize;
49    fn new(n: CVertex, u: CVertex, v: CVertex) -> Self;
50    fn ends(self, n: CVertex) -> (CVertex, CVertex);
51    fn reverse(self, n: CVertex) -> Self;
52}
53
54impl<'a, K: CompleteEdgeKind> VertexTypes<'a, Complete<K>> for Complete<K> {
55    type VertexIter = Range<Vertex<Self>>;
56    type OutNeighborIter = COutNeighborIter;
57}
58
59impl<K: CompleteEdgeKind> WithVertex for Complete<K> {
60    type Vertex = CVertex;
61    type OptionVertex = OptionalMax<CVertex>;
62}
63
64impl<'a, K: CompleteEdgeKind> EdgeTypes<'a, Complete<K>> for Complete<K> {
65    // TODO: write specific iterator for EdgeIter
66    type EdgeIter = Map<Range<usize>, fn(usize) -> K::Edge>;
67    type OutEdgeIter = COutEdgeIter<Edge<Self>>;
68}
69
70impl<K: CompleteEdgeKind> WithEdge for Complete<K> {
71    type Kind = K;
72    type Edge = K::Edge;
73    type OptionEdge = Optioned<K::Edge, MaxNone<K::Edge>>;
74
75    fn source(&self, e: Edge<Self>) -> Vertex<Self> {
76        K::Edge::ends(e, self.n).0
77    }
78
79    fn target(&self, e: Edge<Self>) -> Vertex<Self> {
80        K::Edge::ends(e, self.n).1
81    }
82
83    fn end_vertices(&self, e: Edge<Self>) -> (Vertex<Self>, Vertex<Self>) {
84        K::Edge::ends(e, self.n)
85    }
86
87    fn orientation(&self, _e: Edge<Self>) -> Orientation {
88        K::orientation()
89    }
90
91    fn reverse(&self, e: Edge<Self>) -> Edge<Self> {
92        K::Edge::reverse(e, self.n)
93    }
94
95    fn get_reverse(&self, e: Edge<Self>) -> Option<Edge<Self>> {
96        Some(K::Edge::reverse(e, self.n))
97    }
98}
99
100impl<K: CompleteEdgeKind> VertexList for Complete<K> {
101    fn num_vertices(&self) -> usize {
102        self.n as usize
103    }
104
105    fn vertices(&self) -> VertexIter<Self> {
106        0..self.n
107    }
108}
109
110impl<K: CompleteEdgeKind> EdgeList for Complete<K> {
111    fn edges(&self) -> EdgeIter<Self> {
112        (0..self.num_edges()).map(K::Edge::from_index)
113    }
114
115    fn num_edges(&self) -> usize {
116        let n = self.num_vertices();
117        if K::is_directed() {
118            n * n - n
119        } else {
120            (n * n - n) / 2
121        }
122    }
123
124    fn get_edge_by_ends(&self, u: Vertex<Self>, v: Vertex<Self>) -> Option<Edge<Self>> {
125        if u < self.n && v < self.n && u != v {
126            Some(K::Edge::new(self.n, u, v))
127        } else {
128            None
129        }
130    }
131}
132
133impl<K: CompleteEdgeKind> Adjacency for Complete<K> {
134    fn out_neighbors(&self, v: CVertex) -> OutNeighborIter<Self> {
135        debug_assert!(v < self.n);
136        COutNeighborIter::new(v, self.n)
137    }
138
139    fn out_degree(&self, v: Vertex<Self>) -> usize {
140        debug_assert!(v < self.n);
141        self.num_vertices().checked_sub(1).unwrap_or(0)
142    }
143}
144
145impl<K: CompleteEdgeKind> Incidence for Complete<K> {
146    fn out_edges(&self, v: Vertex<Self>) -> OutEdgeIter<Self> {
147        debug_assert!(v < self.n);
148        COutEdgeIter::new(self.n, v)
149    }
150}
151
152impl<T, K: CompleteEdgeKind> WithVertexProp<T> for Complete<K> {
153    type VertexProp = VecVertexProp<Complete<K>, T>;
154}
155
156impl<T, K: CompleteEdgeKind> WithEdgeProp<T> for Complete<K>
157where
158    Complete<K>: WithEdgeIndexProp,
159{
160    type EdgeProp = VecEdgeProp<Complete<K>, T>;
161}
162
163impl<K: CompleteEdgeKind> BasicVertexProps for Complete<K> {}
164impl<K: CompleteEdgeKind> BasicEdgeProps for Complete<K> {}
165impl<K: CompleteEdgeKind> BasicProps for Complete<K> {}
166
167impl<K: CompleteEdgeKind> Choose for Complete<K> {
168    fn choose_vertex<R: Rng>(&self, mut rng: R) -> Option<Vertex<Self>> {
169        if self.n == 0 {
170            None
171        } else {
172            Some(rng.gen_range(0, self.n))
173        }
174    }
175
176    fn choose_out_neighbor<R: Rng>(&self, v: Vertex<Self>, rng: R) -> Option<Vertex<Self>> {
177        self.choose_out_edge(v, rng).map(|e| self.target(e))
178    }
179
180    fn choose_edge<R: Rng>(&self, mut rng: R) -> Option<Edge<Self>> {
181        if self.num_edges() == 0 {
182            None
183        } else {
184            let e = K::Edge::from_index(rng.gen_range(0, self.num_edges()));
185            Some(if rng.gen() { e } else { e.reverse(self.n) })
186        }
187    }
188
189    fn choose_out_edge<R: Rng>(&self, v: Vertex<Self>, mut rng: R) -> Option<Edge<Self>> {
190        if self.out_degree(v) == 0 {
191            None
192        } else {
193            let mut u = v;
194            while u == v {
195                u = rng.gen_range(0, self.n);
196            }
197            Some(K::Edge::new(self.n, v, u))
198        }
199    }
200}
201
202#[derive(Clone, Debug)]
203pub struct CVertexIndexProp;
204
205impl PropGet<CVertex> for CVertexIndexProp {
206    type Output = usize;
207
208    #[inline]
209    fn get(&self, x: CVertex) -> usize {
210        x as usize
211    }
212}
213
214impl<K: CompleteEdgeKind> WithVertexIndexProp for Complete<K> {
215    type VertexIndexProp = CVertexIndexProp;
216
217    fn vertex_index(&self) -> CVertexIndexProp {
218        CVertexIndexProp
219    }
220}
221
222#[derive(Clone, Debug)]
223pub struct CEdgeIndexProp<E>(PhantomData<E>);
224
225impl<E: EdgeImpl> PropGet<E> for CEdgeIndexProp<E> {
226    type Output = usize;
227
228    #[inline]
229    fn get(&self, e: E) -> usize {
230        E::to_index(e)
231    }
232}
233
234impl<K: CompleteEdgeKind> WithEdgeIndexProp for Complete<K> {
235    type EdgeIndexProp = CEdgeIndexProp<K::Edge>;
236
237    fn edge_index(&self) -> CEdgeIndexProp<K::Edge> {
238        CEdgeIndexProp(PhantomData)
239    }
240}
241
242#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
243pub struct MaxNone<E>(PhantomData<E>);
244
245impl<E: EdgeImpl> BuildNone<E> for MaxNone<E> {
246    fn none() -> E {
247        E::from_index(usize::max_value())
248    }
249
250    fn desc() -> &'static str {
251        "CompleteEdge"
252    }
253}
254
255// Iterators
256
257pub struct COutEdgeIter<E> {
258    n: CVertex,
259    rem: usize,
260    u: CVertex,
261    v: CVertex,
262    _marker: PhantomData<E>,
263}
264
265impl<E> COutEdgeIter<E> {
266    fn new(n: CVertex, u: CVertex) -> Self {
267        COutEdgeIter {
268            n: n,
269            rem: (n - 1) as usize,
270            u: u,
271            v: 0,
272            _marker: PhantomData,
273        }
274    }
275}
276
277impl<E: EdgeImpl> Iterator for COutEdgeIter<E> {
278    type Item = E;
279
280    fn next(&mut self) -> Option<Self::Item> {
281        if self.rem == 0 {
282            None
283        } else {
284            if self.u == self.v {
285                self.v += 1;
286            }
287            let e = Some(E::new(self.n, self.u, self.v));
288            self.v += 1;
289            self.rem -= 1;
290            e
291        }
292    }
293
294    fn size_hint(&self) -> (usize, Option<usize>) {
295        (self.rem, Some(self.rem))
296    }
297}
298
299impl<E: EdgeImpl> ExactSizeIterator for COutEdgeIter<E> {
300    fn len(&self) -> usize {
301        self.rem
302    }
303}
304
305pub struct COutNeighborIter {
306    cur: CVertex,
307    source: CVertex,
308    n: CVertex,
309}
310
311impl COutNeighborIter {
312    fn new(source: CVertex, n: CVertex) -> Self {
313        COutNeighborIter { cur: 0, source, n }
314    }
315}
316
317impl Iterator for COutNeighborIter {
318    type Item = CVertex;
319
320    fn next(&mut self) -> Option<Self::Item> {
321        if self.cur == self.source && self.cur != self.n {
322            self.cur += 1;
323        }
324        if self.cur == self.n {
325            return None;
326        }
327        let cur = self.cur;
328        self.cur += 1;
329        Some(cur)
330    }
331
332    fn size_hint(&self) -> (usize, Option<usize>) {
333        let rem = self.len();
334        (rem, Some(rem))
335    }
336
337    fn nth(&mut self, n: usize) -> Option<Self::Item> {
338        if n >= self.len() {
339            return None
340        }
341        let n = n as CVertex;
342        let i = self.source.checked_sub(self.cur).unwrap_or(0);
343        self.cur += n + (n >= i) as CVertex;
344        self.next()
345    }
346}
347
348impl ExactSizeIterator for COutNeighborIter {
349    fn len(&self) -> usize {
350        (self.n - self.cur - (self.cur >= self.source) as CVertex) as usize
351    }
352}
353
354// Undirected
355
356impl CompleteEdgeKind for Undirected {
357    type Edge = UndirectedEdge;
358}
359
360#[derive(Clone, Copy, Eq, Debug)]
361pub struct UndirectedEdge(usize);
362
363impl PartialEq for UndirectedEdge {
364    #[inline]
365    fn eq(&self, other: &UndirectedEdge) -> bool {
366        self.to_index() == other.to_index()
367    }
368}
369
370impl PartialOrd for UndirectedEdge {
371    #[inline]
372    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
373        Some(self.cmp(other))
374    }
375}
376
377impl Ord for UndirectedEdge {
378    #[inline]
379    fn cmp(&self, other: &Self) -> Ordering {
380        self.to_index().cmp(&other.to_index())
381    }
382}
383
384impl Hash for UndirectedEdge {
385    #[inline]
386    fn hash<H>(&self, state: &mut H)
387    where
388        H: Hasher,
389    {
390        self.to_index().hash(state)
391    }
392}
393
394impl EdgeImpl for UndirectedEdge {
395    #[inline]
396    fn from_index(index: usize) -> Self {
397        UndirectedEdge(index << 1)
398    }
399
400    #[inline]
401    fn to_index(self) -> usize {
402        self.0 >> 1
403    }
404
405    fn new(n: CVertex, u: CVertex, v: CVertex) -> Self {
406        let (n, u, v) = (n as usize, u as usize, v as usize);
407        let id = |u, v| {
408            if u < (n - 1) / 2 {
409                u * n + v
410            } else {
411                (n - u - 1) * n - v - 1
412            }
413        };
414
415        if u < v {
416            UndirectedEdge(id(u, v) << 1)
417        } else {
418            UndirectedEdge(id(v, u) << 1 | 1)
419        }
420    }
421
422    #[inline]
423    fn ends(self, n: CVertex) -> (CVertex, CVertex) {
424        let (u, v) = {
425            let n = n as usize;
426            let e = self.0 >> 1;
427            let (u, v) = (e / n, e % n);
428            if u < v {
429                (u, v)
430            } else {
431                (n - u - 2, n - v - 1)
432            }
433        };
434
435        if self.0 & 1 == 0 {
436            (u as CVertex, v as CVertex)
437        } else {
438            (v as CVertex, u as CVertex)
439        }
440    }
441
442    #[inline]
443    fn reverse(self, _n: CVertex) -> Self {
444        UndirectedEdge(self.0 ^ 1)
445    }
446}
447
448// Directed
449
450#[derive(Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Debug)]
451pub struct DirectedEdge(usize);
452
453impl CompleteEdgeKind for Directed {
454    type Edge = DirectedEdge;
455}
456
457impl EdgeImpl for DirectedEdge {
458    #[inline]
459    fn from_index(index: usize) -> Self {
460        DirectedEdge(index)
461    }
462
463    #[inline]
464    fn to_index(self) -> usize {
465        self.0
466    }
467
468    fn new(n: CVertex, u: CVertex, v: CVertex) -> Self {
469        let (n, u, v) = (n as usize, u as usize, v as usize);
470        DirectedEdge(n * u + v - u - (if v < u { 0 } else { 1 }))
471    }
472
473    #[inline]
474    fn ends(self, n: CVertex) -> (CVertex, CVertex) {
475        let n = n as usize;
476        let e = self.0;
477        let u = e / (n - 1);
478        let mut v = e % (n - 1);
479        if v >= u {
480            v += 1;
481        }
482        (u as CVertex, v as CVertex)
483    }
484
485    fn reverse(self, n: CVertex) -> Self {
486        let (u, v) = Self::ends(self, n);
487        Self::new(n, v, u)
488    }
489}
490
491// Tests
492
493#[cfg(test)]
494mod tests {
495    pub use super::{CVertex, DirectedEdge, EdgeImpl, UndirectedEdge};
496    pub use itertools::Itertools;
497    pub use prelude::*;
498    pub use std::fmt::Debug;
499    pub use tests::GraphTests;
500
501    fn assert_edge<E: EdgeImpl + Debug + Copy>(n: CVertex, u: CVertex, v: CVertex) {
502        let e = E::new(n, u, v);
503        let r = E::reverse(e, n);
504        assert_eq!((u, v), E::ends(e, n), "n = {}, e = {:?}", n, e);
505        assert_eq!((v, u), E::ends(r, n), "n = {}, e = {:?}, r = {:?}", n, e, r);
506    }
507
508    #[test]
509    fn out_neighbor_nth() {
510        use super::COutNeighborIter;
511        let iter = |source, n, nth| COutNeighborIter::new(source, n).nth(nth);
512        assert_eq!(Some(0), iter(2, 4, 0));
513        assert_eq!(Some(1), iter(2, 4, 1));
514        assert_eq!(Some(3), iter(2, 4, 2));
515        assert_eq!(None, iter(2, 4, 3));
516        assert_eq!(None, iter(2, 4, 4));
517
518        assert_eq!(Some(1), iter(0, 4, 0));
519        assert_eq!(Some(2), iter(0, 4, 1));
520        assert_eq!(Some(3), iter(0, 4, 2));
521        assert_eq!(None, iter(0, 4, 3));
522        assert_eq!(None, iter(0, 4, 4));
523
524        assert_eq!(Some(0), iter(3, 4, 0));
525        assert_eq!(Some(1), iter(3, 4, 1));
526        assert_eq!(Some(2), iter(3, 4, 2));
527        assert_eq!(None, iter(3, 4, 3));
528        assert_eq!(None, iter(3, 4, 4));
529    }
530
531    #[test]
532    fn test_large_edges() {
533        let g = CompleteGraph::new(100_000);
534        assert_eq!(
535            (99_999, 99_998),
536            g.end_vertices(g.edge_by_ends(99_999, 99_998))
537        );
538    }
539
540    #[test]
541    fn edge_impl() {
542        for n in 2..10 {
543            for (u, v) in (0..n).tuple_combinations() {
544                assert_edge::<UndirectedEdge>(n, u, v);
545                assert_edge::<UndirectedEdge>(n, v, u);
546
547                assert_edge::<DirectedEdge>(n, u, v);
548                assert_edge::<DirectedEdge>(n, v, u);
549            }
550        }
551    }
552
553    macro_rules! t {
554        ($m:ident, $n:expr, $G:ident, $v:expr, $e:expr) => {
555            mod $m {
556                use super::*;
557
558                struct Test;
559
560                impl GraphTests for Test {
561                    type G = $G;
562
563                    fn new() -> (Self::G, Vec<Vertex<Self::G>>, Vec<Edge<Self::G>>) {
564                        let e = $e.into_iter();
565                        (
566                            $G::new($n),
567                            $v,
568                            e.map(|(u, v)| EdgeImpl::new($n, u, v)).sorted(),
569                        )
570                    }
571                }
572
573                graph_tests!{Test}
574            }
575        };
576    }
577
578    // Undirected
579
580    t!{k0, 0, CompleteGraph, vec![], vec![]}
581    t!{k1, 1, CompleteGraph, vec![0], vec![]}
582    t!{k2, 2, CompleteGraph, vec![0, 1], vec![(0, 1)]}
583
584    t! {
585        k3, 3,
586        CompleteGraph,
587        vec![0, 1, 2],
588        vec![(0, 1), (0, 2), (1, 2)]
589    }
590
591    t!{
592        k4, 4,
593        CompleteGraph,
594        vec![0, 1, 2, 3],
595        vec![(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
596    }
597
598    // Directed
599
600    t!{directed_k0, 0, CompleteDigraph, vec![], vec![]}
601    t!{directed_k1, 1, CompleteDigraph, vec![0], vec![]}
602    t!{directed_k2, 2, CompleteDigraph, vec![0, 1], vec![(0, 1), (1, 0)]}
603
604    t!{
605        directed_k3, 3,
606        CompleteDigraph,
607        vec![0, 1, 2],
608        vec![(0, 1), (0, 2),
609             (1, 0), (1, 2),
610             (2, 0), (2, 1)]
611    }
612
613    t!{
614        directed_k4, 4,
615        CompleteDigraph,
616        vec![0, 1, 2, 3],
617        vec![(0, 1), (0, 2), (0, 3),
618             (1, 0), (1, 2), (1, 3),
619             (2, 0), (2, 1), (2, 3),
620             (3, 0), (3, 1), (3, 2)]
621    }
622}
fera_graph/graphs/complete.rs

fera_graph/graphs/
complete.rs
