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