fera_graph/graphs/
mod.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
5//! Graph traits and implementations.
6
7pub mod adaptors;
8pub mod adjset;
9pub mod complete;
10pub mod static_;
11
12mod common;
13mod ref_;
14
15pub use self::common::*;
16
17use params::IntoOwned;
18use prelude::*;
19
20use std::fmt::Debug;
21use std::hash::Hash;
22
23pub type Vertex<G> = <G as WithVertex>::Vertex;
24pub type OptionVertex<G> = <G as WithVertex>::OptionVertex;
25pub type VertexIndexProp<G> = <G as WithVertexIndexProp>::VertexIndexProp;
26pub type VertexIter<'a, G> = <G as VertexTypes<'a, G>>::VertexIter;
27pub type OutNeighborIter<'a, G> = <G as VertexTypes<'a, G>>::OutNeighborIter;
28pub type DefaultVertexPropMut<G, T> = <G as WithVertexProp<T>>::VertexProp;
29
30pub type Edge<G> = <G as WithEdge>::Edge;
31pub type OptionEdge<G> = <G as WithEdge>::OptionEdge;
32pub type EdgeIndexProp<G> = <G as WithEdgeIndexProp>::EdgeIndexProp;
33pub type EdgeIter<'a, G> = <G as EdgeTypes<'a, G>>::EdgeIter;
34pub type OutEdgeIter<'a, G> = <G as EdgeTypes<'a, G>>::OutEdgeIter;
35pub type DefaultEdgePropMut<G, T> = <G as WithEdgeProp<T>>::EdgeProp;
36
37macro_rules! items {
38    ($($item:item)*) => ($($item)*);
39}
40
41macro_rules! trait_alias {
42    ($name:ident = $($base:tt)+) => {
43        items! {
44            pub trait $name: $($base)+ { }
45            impl<T: $($base)+> $name for T { }
46        }
47    };
48}
49
50trait_alias!(Graph = VertexList + EdgeList<Kind = Undirected> + BasicProps);
51trait_alias!(AdjacencyGraph = Graph + Adjacency);
52trait_alias!(IncidenceGraph = AdjacencyGraph + Incidence);
53
54trait_alias!(Digraph = VertexList + EdgeList<Kind = Directed> + BasicProps);
55trait_alias!(AdjacencyDigraph = Digraph + Adjacency);
56trait_alias!(IncidenceDigraph = AdjacencyDigraph + Incidence);
57
58trait_alias!(GraphItem = Copy + Eq + Hash + Debug);
59
60#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Debug)]
61pub enum Orientation {
62    Directed,
63    Undirected,
64}
65
66impl Orientation {
67    #[inline]
68    pub fn is_directed(&self) -> bool {
69        *self == Orientation::Directed
70    }
71
72    #[inline]
73    pub fn is_undirected(&self) -> bool {
74        *self == Orientation::Undirected
75    }
76}
77
78pub trait EdgeKind {}
79
80pub trait UniformEdgeKind: EdgeKind {
81    fn orientation() -> Orientation;
82
83    #[inline]
84    fn is_directed() -> bool {
85        Self::orientation().is_directed()
86    }
87
88    #[inline]
89    fn is_undirected() -> bool {
90        Self::orientation().is_undirected()
91    }
92}
93
94#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug)]
95pub enum Directed {}
96
97impl EdgeKind for Directed {}
98
99impl UniformEdgeKind for Directed {
100    #[inline]
101    fn orientation() -> Orientation {
102        Orientation::Directed
103    }
104}
105
106#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug)]
107pub enum Undirected {}
108
109impl EdgeKind for Undirected {}
110
111impl UniformEdgeKind for Undirected {
112    #[inline]
113    fn orientation() -> Orientation {
114        Orientation::Undirected
115    }
116}
117
118// TODO: write a graph with mixed edges and test it
119#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug)]
120pub enum Mixed {}
121
122impl EdgeKind for Mixed {}
123
124pub trait VertexTypes<'a, G: WithVertex> {
125    type VertexIter: Iterator<Item = Vertex<G>>;
126    type OutNeighborIter: Iterator<Item = Vertex<G>>;
127}
128
129pub trait WithVertex: Sized + for<'a> VertexTypes<'a, Self> {
130    type Vertex: 'static + GraphItem;
131    type OptionVertex: 'static + GraphItem + Optional<Vertex<Self>> + From<Option<Vertex<Self>>>;
132
133    // TODO: is this necessary?
134    fn vertex_none() -> OptionVertex<Self> {
135        Default::default()
136    }
137
138    // TODO: is this necessary?
139    fn vertex_some(v: Vertex<Self>) -> OptionVertex<Self> {
140        From::from(v)
141    }
142
143    fn vertex_prop<P, T>(&self, value: T) -> P
144    where
145        P: VertexPropMutNew<Self, T>,
146        T: Clone,
147    {
148        P::new_vertex_prop(self, value)
149    }
150
151    fn vertex_prop_from_fn<P, T, F>(&self, mut fun: F) -> P
152    where
153        Self: VertexList,
154        P: VertexPropMutNew<Self, T>,
155        F: FnMut(Vertex<Self>) -> T,
156        T: Default + Clone,
157    {
158        // FIXME: Can we remove T: Default + Clone?
159        let mut p: P = self.vertex_prop(T::default());
160        for v in self.vertices() {
161            p[v] = fun(v);
162        }
163        p
164    }
165}
166
167pub trait EdgeTypes<'a, G: WithEdge> {
168    type EdgeIter: Iterator<Item = Edge<G>>;
169    type OutEdgeIter: Iterator<Item = Edge<G>>;
170}
171
172pub trait WithEdge: Sized + WithVertex + for<'a> EdgeTypes<'a, Self> {
173    type Kind: EdgeKind;
174    type Edge: 'static + GraphItem;
175    type OptionEdge: 'static + GraphItem + Optional<Edge<Self>> + From<Option<Edge<Self>>>;
176
177    fn orientation(&self, _e: Edge<Self>) -> Orientation;
178
179    fn source(&self, e: Edge<Self>) -> Vertex<Self>;
180
181    fn target(&self, e: Edge<Self>) -> Vertex<Self>;
182
183    fn ends<'a, I, O>(&'a self, item: I) -> O
184    where
185        I: Ends<'a, Self, O>,
186    {
187        item._ends(self)
188    }
189
190    fn end_vertices(&self, e: Edge<Self>) -> (Vertex<Self>, Vertex<Self>) {
191        self.ends(e)
192    }
193
194    fn with_ends<I>(&self, iter: I) -> EdgesWithEnds<Self, I::IntoIter>
195    where
196        I: IntoIterator,
197        I::Item: IntoOwned<Edge<Self>>,
198    {
199        EdgesWithEnds {
200            g: self,
201            iter: iter.into_iter(),
202        }
203    }
204
205    fn opposite(&self, u: Vertex<Self>, e: Edge<Self>) -> Vertex<Self> {
206        let (s, t) = self.ends(e);
207        if u == s {
208            t
209        } else if u == t {
210            s
211        } else {
212            panic!("u is not an end of e");
213        }
214    }
215
216    fn is_incident(&self, v: Vertex<Self>, e: Edge<Self>) -> bool {
217        let (s, t) = self.ends(e);
218        v == s || v == t
219    }
220
221    fn reverse(&self, e: Edge<Self>) -> Edge<Self>
222    where
223        Self: WithEdge<Kind = Undirected>,
224    {
225        self.get_reverse(e)
226            .expect("the reverse of an edge (all undirected graphs must implement reverse)")
227    }
228
229    fn get_reverse(&self, _e: Edge<Self>) -> Option<Edge<Self>> {
230        // TODO: remove default impl
231        None
232    }
233
234    // TODO: is this necessary?
235    fn edge_none() -> OptionEdge<Self> {
236        Default::default()
237    }
238
239    // TODO: is this necessary?
240    fn edge_some(e: Edge<Self>) -> OptionEdge<Self> {
241        From::from(e)
242    }
243
244    fn edge_prop<P, T>(&self, value: T) -> P
245    where
246        P: EdgePropMutNew<Self, T>,
247        T: Clone,
248    {
249        P::new_edge_prop(self, value)
250    }
251
252    fn edge_prop_from_fn<P, F, T>(&self, mut fun: F) -> P
253    where
254        Self: EdgeList,
255        P: EdgePropMutNew<Self, T>,
256        F: FnMut(Edge<Self>) -> T,
257        T: Default + Clone,
258    {
259        // FIXME: Can we remove T: Default + Clone?
260        let mut p: P = self.edge_prop(T::default());
261        for e in self.edges() {
262            p[e] = fun(e);
263        }
264        p
265    }
266}
267
268pub trait VertexList: Sized + WithVertex {
269    fn vertices(&self) -> VertexIter<Self>;
270
271    fn num_vertices(&self) -> usize {
272        self.vertices().count()
273    }
274}
275
276pub trait EdgeList: Sized + WithEdge {
277    fn edges(&self) -> EdgeIter<Self>;
278
279    fn edges_ends(&self) -> EdgesEnds<Self, EdgeIter<Self>> {
280        // TODO: specialize
281        self.ends(self.edges())
282    }
283
284    fn edges_with_ends(&self) -> EdgesWithEnds<Self, EdgeIter<Self>> {
285        // TODO: specialize
286        self.with_ends(self.edges())
287    }
288
289    fn num_edges(&self) -> usize {
290        self.edges().count()
291    }
292
293    fn get_edge_by_ends(&self, u: Vertex<Self>, v: Vertex<Self>) -> Option<Edge<Self>> {
294        // TODO: specialize for Incidence
295        for (e, a, b) in self.edges_with_ends() {
296            if (u, v) == (a, b) {
297                return Some(e);
298            }
299            if self.orientation(e).is_directed() {
300                continue;
301            }
302            if let Some(e) = self.get_reverse(e) {
303                if (u, v) == (b, a) {
304                    return Some(e);
305                }
306            }
307        }
308        None
309    }
310
311    fn edge_by_ends(&self, u: Vertex<Self>, v: Vertex<Self>) -> Edge<Self> {
312        // TODO: fix expect message
313        self.get_edge_by_ends(u, v).expect("an edge (u, v)")
314    }
315}
316
317pub trait Adjacency: WithVertex {
318    fn out_neighbors(&self, v: Vertex<Self>) -> OutNeighborIter<Self>;
319
320    fn out_degree(&self, v: Vertex<Self>) -> usize {
321        self.out_neighbors(v).count()
322    }
323}
324
325pub trait Incidence: WithEdge + Adjacency {
326    fn out_edges(&self, v: Vertex<Self>) -> OutEdgeIter<Self>;
327
328    fn out_edges_ends(&self, v: Vertex<Self>) -> EdgesEnds<Self, OutEdgeIter<Self>> {
329        // TODO: specialize
330        self.ends(self.out_edges(v))
331    }
332
333    fn out_edges_with_ends(&self, v: Vertex<Self>) -> EdgesWithEnds<Self, OutEdgeIter<Self>> {
334        // TODO: specialize
335        self.with_ends(self.out_edges(v))
336    }
337}
338
339// Ends
340
341pub trait Ends<'a, G, O> {
342    fn _ends(self, g: &'a G) -> O;
343}
344
345impl<'a, G> Ends<'a, G, (Vertex<G>, Vertex<G>)> for Edge<G>
346where
347    G: WithEdge,
348{
349    fn _ends(self, g: &'a G) -> (Vertex<G>, Vertex<G>) {
350        (g.source(self), g.target(self))
351    }
352}
353
354impl<'a, G> Ends<'a, G, (Edge<G>, Vertex<G>, Vertex<G>)> for Edge<G>
355where
356    G: WithEdge,
357{
358    fn _ends(self, g: &'a G) -> (Edge<G>, Vertex<G>, Vertex<G>) {
359        let (u, v) = g.ends(self);
360        (self, u, v)
361    }
362}
363
364impl<'a, G, I> Ends<'a, G, EdgesEnds<'a, G, I::IntoIter>> for I
365where
366    G: WithEdge,
367    I: IntoIterator,
368    I::Item: IntoOwned<Edge<G>>,
369{
370    fn _ends(self, g: &'a G) -> EdgesEnds<'a, G, I::IntoIter> {
371        EdgesEnds {
372            g: g,
373            iter: self.into_iter(),
374        }
375    }
376}
377
378// Iterators
379
380pub struct EdgesEnds<'a, G: 'a, I> {
381    g: &'a G,
382    iter: I,
383}
384
385impl<'a, G, I> Iterator for EdgesEnds<'a, G, I>
386where
387    G: WithEdge,
388    I: Iterator,
389    I::Item: IntoOwned<Edge<G>>,
390{
391    type Item = (Vertex<G>, Vertex<G>);
392
393    fn next(&mut self) -> Option<Self::Item> {
394        self.iter.next().map(|e| self.g.ends(e.into_owned()))
395    }
396
397    fn size_hint(&self) -> (usize, Option<usize>) {
398        self.iter.size_hint()
399    }
400}
401
402impl<'a, G, I> ExactSizeIterator for EdgesEnds<'a, G, I>
403where
404    G: WithEdge,
405    I: Iterator,
406    I::Item: IntoOwned<Edge<G>>,
407{
408}
409
410pub struct EdgesWithEnds<'a, G: 'a, I> {
411    g: &'a G,
412    iter: I,
413}
414
415impl<'a, G, I> Iterator for EdgesWithEnds<'a, G, I>
416where
417    G: WithEdge,
418    I: Iterator,
419    I::Item: IntoOwned<Edge<G>>,
420{
421    type Item = (Edge<G>, Vertex<G>, Vertex<G>);
422
423    fn next(&mut self) -> Option<Self::Item> {
424        self.iter.next().map(|e| self.g.ends(e.into_owned()))
425    }
426
427    fn size_hint(&self) -> (usize, Option<usize>) {
428        self.iter.size_hint()
429    }
430}
431
432impl<'a, G, I> ExactSizeIterator for EdgesWithEnds<'a, G, I>
433where
434    G: WithEdge,
435    I: Iterator,
436    I::Item: IntoOwned<Edge<G>>,
437{
438}
fera_graph/graphs/mod.rs

fera_graph/graphs/
mod.rs
