1 
2 use ::{
3     Direction,
4     Incoming,
5 };
6 
7 use visit::{
8     GraphBase,
9     GraphRef,
10     IntoNodeIdentifiers,
11     IntoNodeReferences,
12     IntoNeighbors,
13     IntoNeighborsDirected,
14     IntoEdgeReferences,
15     NodeCompactIndexable,
16     NodeCount,
17     NodeIndexable,
18     Visitable,
19     EdgeRef,
20     Data,
21     GraphProp,
22 };
23 
24 /// An edge-reversing graph adaptor.
25 ///
26 /// All edges have the opposite direction with `Reversed`.
27 #[derive(Copy, Clone, Debug)]
28 pub struct Reversed<G>(pub G);
29 
30 impl<G: GraphBase> GraphBase for Reversed<G> {
31     type NodeId = G::NodeId;
32     type EdgeId = G::EdgeId;
33 }
34 
35 impl<G: GraphRef> GraphRef for Reversed<G> { }
36 
37 Data!{delegate_impl [[G], G, Reversed<G>, access0]}
38 
39 impl<G> IntoNeighbors for Reversed<G>
40     where G: IntoNeighborsDirected
41 {
42     type Neighbors = G::NeighborsDirected;
neighbors(self, n: G::NodeId) -> G::NeighborsDirected43     fn neighbors(self, n: G::NodeId) -> G::NeighborsDirected
44     {
45         self.0.neighbors_directed(n, Incoming)
46     }
47 }
48 
49 impl<G> IntoNeighborsDirected for Reversed<G>
50     where G: IntoNeighborsDirected
51 {
52     type NeighborsDirected = G::NeighborsDirected;
neighbors_directed(self, n: G::NodeId, d: Direction) -> G::NeighborsDirected53     fn neighbors_directed(self, n: G::NodeId, d: Direction)
54         -> G::NeighborsDirected
55     {
56         self.0.neighbors_directed(n, d.opposite())
57     }
58 }
59 
60 impl<G: Visitable> Visitable for Reversed<G>
61 {
62     type Map = G::Map;
visit_map(&self) -> G::Map63     fn visit_map(&self) -> G::Map {
64         self.0.visit_map()
65     }
reset_map(&self, map: &mut Self::Map)66     fn reset_map(&self, map: &mut Self::Map) {
67         self.0.reset_map(map);
68     }
69 }
70 
71 
72 /// A reversed edge reference
73 #[derive(Copy, Clone, Debug)]
74 pub struct ReversedEdgeReference<R>(R);
75 
76 /// An edge reference
77 impl<R> EdgeRef for ReversedEdgeReference<R>
78     where R: EdgeRef,
79 {
80     type NodeId = R::NodeId;
81     type EdgeId = R::EdgeId;
82     type Weight = R::Weight;
source(&self) -> Self::NodeId83     fn source(&self) -> Self::NodeId {
84         self.0.target()
85     }
target(&self) -> Self::NodeId86     fn target(&self) -> Self::NodeId {
87         self.0.source()
88     }
weight(&self) -> &Self::Weight89     fn weight(&self) -> &Self::Weight {
90         self.0.weight()
91     }
id(&self) -> Self::EdgeId92     fn id(&self) -> Self::EdgeId {
93         self.0.id()
94     }
95 }
96 
97 impl<G> IntoEdgeReferences for Reversed<G>
98     where G: IntoEdgeReferences
99 {
100     type EdgeRef = ReversedEdgeReference<G::EdgeRef>;
101     type EdgeReferences = ReversedEdgeReferences<G::EdgeReferences>;
edge_references(self) -> Self::EdgeReferences102     fn edge_references(self) -> Self::EdgeReferences {
103         ReversedEdgeReferences {
104             iter: self.0.edge_references(),
105         }
106     }
107 }
108 
109 /// A reversed edge references iterator.
110 pub struct ReversedEdgeReferences<I> {
111     iter: I,
112 }
113 
114 impl<I> Iterator for ReversedEdgeReferences<I>
115     where I: Iterator,
116           I::Item: EdgeRef,
117 {
118     type Item = ReversedEdgeReference<I::Item>;
next(&mut self) -> Option<Self::Item>119     fn next(&mut self) -> Option<Self::Item> {
120         self.iter.next().map(ReversedEdgeReference)
121     }
122 }
123 
124 macro_rules! access0 {
125     ($e:expr) => ($e.0)
126 }
127 
128 NodeIndexable!{delegate_impl [[G], G, Reversed<G>, access0]}
129 NodeCompactIndexable!{delegate_impl [[G], G, Reversed<G>, access0]}
130 IntoNodeIdentifiers!{delegate_impl [[G], G, Reversed<G>, access0]}
131 IntoNodeReferences!{delegate_impl [[G], G, Reversed<G>, access0]}
132 GraphProp!{delegate_impl [[G], G, Reversed<G>, access0]}
133 NodeCount!{delegate_impl [[G], G, Reversed<G>, access0]}
134 
135 
136