1 use crate::{Direction, Incoming};
2 
3 use crate::visit::{
4     Data, EdgeCount, EdgeIndexable, EdgeRef, GetAdjacencyMatrix, GraphBase, GraphProp, GraphRef,
5     IntoEdgeReferences, IntoEdges, IntoEdgesDirected, IntoNeighbors, IntoNeighborsDirected,
6     IntoNodeIdentifiers, IntoNodeReferences, NodeCompactIndexable, NodeCount, NodeIndexable,
7     Visitable,
8 };
9 
10 /// An edge-reversing graph adaptor.
11 ///
12 /// All edges have the opposite direction with `Reversed`.
13 #[derive(Copy, Clone, Debug)]
14 pub struct Reversed<G>(pub G);
15 
16 impl<G: GraphBase> GraphBase for Reversed<G> {
17     type NodeId = G::NodeId;
18     type EdgeId = G::EdgeId;
19 }
20 
21 impl<G: GraphRef> GraphRef for Reversed<G> {}
22 
23 Data! {delegate_impl [[G], G, Reversed<G>, access0]}
24 
25 impl<G> IntoNeighbors for Reversed<G>
26 where
27     G: IntoNeighborsDirected,
28 {
29     type Neighbors = G::NeighborsDirected;
neighbors(self, n: G::NodeId) -> G::NeighborsDirected30     fn neighbors(self, n: G::NodeId) -> G::NeighborsDirected {
31         self.0.neighbors_directed(n, Incoming)
32     }
33 }
34 
35 impl<G> IntoNeighborsDirected for Reversed<G>
36 where
37     G: IntoNeighborsDirected,
38 {
39     type NeighborsDirected = G::NeighborsDirected;
neighbors_directed(self, n: G::NodeId, d: Direction) -> G::NeighborsDirected40     fn neighbors_directed(self, n: G::NodeId, d: Direction) -> G::NeighborsDirected {
41         self.0.neighbors_directed(n, d.opposite())
42     }
43 }
44 
45 impl<G> IntoEdges for Reversed<G>
46 where
47     G: IntoEdgesDirected,
48 {
49     type Edges = ReversedEdges<G::EdgesDirected>;
edges(self, a: Self::NodeId) -> Self::Edges50     fn edges(self, a: Self::NodeId) -> Self::Edges {
51         ReversedEdges {
52             iter: self.0.edges_directed(a, Incoming),
53         }
54     }
55 }
56 
57 impl<G> IntoEdgesDirected for Reversed<G>
58 where
59     G: IntoEdgesDirected,
60 {
61     type EdgesDirected = ReversedEdges<G::EdgesDirected>;
edges_directed(self, a: Self::NodeId, dir: Direction) -> Self::Edges62     fn edges_directed(self, a: Self::NodeId, dir: Direction) -> Self::Edges {
63         ReversedEdges {
64             iter: self.0.edges_directed(a, dir.opposite()),
65         }
66     }
67 }
68 
69 impl<G: Visitable> Visitable for Reversed<G> {
70     type Map = G::Map;
visit_map(&self) -> G::Map71     fn visit_map(&self) -> G::Map {
72         self.0.visit_map()
73     }
reset_map(&self, map: &mut Self::Map)74     fn reset_map(&self, map: &mut Self::Map) {
75         self.0.reset_map(map);
76     }
77 }
78 
79 /// A reversed edges iterator.
80 #[derive(Debug, Clone)]
81 pub struct ReversedEdges<I> {
82     iter: I,
83 }
84 
85 impl<I> Iterator for ReversedEdges<I>
86 where
87     I: Iterator,
88     I::Item: EdgeRef,
89 {
90     type Item = ReversedEdgeReference<I::Item>;
next(&mut self) -> Option<Self::Item>91     fn next(&mut self) -> Option<Self::Item> {
92         self.iter.next().map(ReversedEdgeReference)
93     }
size_hint(&self) -> (usize, Option<usize>)94     fn size_hint(&self) -> (usize, Option<usize>) {
95         self.iter.size_hint()
96     }
97 }
98 
99 /// A reversed edge reference
100 #[derive(Copy, Clone, Debug)]
101 pub struct ReversedEdgeReference<R>(R);
102 
103 impl<R> ReversedEdgeReference<R> {
104     /// Return the original, unreversed edge reference.
as_unreversed(&self) -> &R105     pub fn as_unreversed(&self) -> &R {
106         &self.0
107     }
108 
109     /// Consume `self` and return the original, unreversed edge reference.
into_unreversed(self) -> R110     pub fn into_unreversed(self) -> R {
111         self.0
112     }
113 }
114 
115 /// An edge reference
116 impl<R> EdgeRef for ReversedEdgeReference<R>
117 where
118     R: EdgeRef,
119 {
120     type NodeId = R::NodeId;
121     type EdgeId = R::EdgeId;
122     type Weight = R::Weight;
source(&self) -> Self::NodeId123     fn source(&self) -> Self::NodeId {
124         self.0.target()
125     }
target(&self) -> Self::NodeId126     fn target(&self) -> Self::NodeId {
127         self.0.source()
128     }
weight(&self) -> &Self::Weight129     fn weight(&self) -> &Self::Weight {
130         self.0.weight()
131     }
id(&self) -> Self::EdgeId132     fn id(&self) -> Self::EdgeId {
133         self.0.id()
134     }
135 }
136 
137 impl<G> IntoEdgeReferences for Reversed<G>
138 where
139     G: IntoEdgeReferences,
140 {
141     type EdgeRef = ReversedEdgeReference<G::EdgeRef>;
142     type EdgeReferences = ReversedEdgeReferences<G::EdgeReferences>;
edge_references(self) -> Self::EdgeReferences143     fn edge_references(self) -> Self::EdgeReferences {
144         ReversedEdgeReferences {
145             iter: self.0.edge_references(),
146         }
147     }
148 }
149 
150 /// A reversed edge references iterator.
151 #[derive(Debug, Clone)]
152 pub struct ReversedEdgeReferences<I> {
153     iter: I,
154 }
155 
156 impl<I> Iterator for ReversedEdgeReferences<I>
157 where
158     I: Iterator,
159     I::Item: EdgeRef,
160 {
161     type Item = ReversedEdgeReference<I::Item>;
next(&mut self) -> Option<Self::Item>162     fn next(&mut self) -> Option<Self::Item> {
163         self.iter.next().map(ReversedEdgeReference)
164     }
size_hint(&self) -> (usize, Option<usize>)165     fn size_hint(&self) -> (usize, Option<usize>) {
166         self.iter.size_hint()
167     }
168 }
169 
170 macro_rules! access0 {
171     ($e:expr) => {
172         $e.0
173     };
174 }
175 
176 NodeIndexable! {delegate_impl [[G], G, Reversed<G>, access0]}
177 NodeCompactIndexable! {delegate_impl [[G], G, Reversed<G>, access0]}
178 IntoNodeIdentifiers! {delegate_impl [[G], G, Reversed<G>, access0]}
179 IntoNodeReferences! {delegate_impl [[G], G, Reversed<G>, access0]}
180 GraphProp! {delegate_impl [[G], G, Reversed<G>, access0]}
181 NodeCount! {delegate_impl [[G], G, Reversed<G>, access0]}
182 EdgeCount! {delegate_impl [[G], G, Reversed<G>, access0]}
183 EdgeIndexable! {delegate_impl [[G], G, Reversed<G>, access0]}
184 GetAdjacencyMatrix! {delegate_impl [[G], G, Reversed<G>, access0]}
185