rs_graph/adapters/
reversedigraph.rs

1/*
2 * Copyright (c) 2017-2022 Frank Fischer <frank-fischer@shadow-soft.de>
3 *
4 * This program is free software: you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License as
6 * published by the Free Software Foundation, either version 3 of the
7 * License, or (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful, but
10 * WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12 * General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program.  If not, see  <http://www.gnu.org/licenses/>
16 */
17
18//! Reverse the direction of the edges of a digraph.
19
20use crate::traits::refs::{DirectedRef, FiniteDigraphRef, FiniteGraphRef, GraphTypeRef, IndexGraphRef, UndirectedRef};
21use crate::traits::{
22    Directed, DirectedEdge, FiniteDigraph, FiniteGraph, GraphIterator, GraphType, IndexGraph, Undirected,
23};
24
25/// A digraph wrapping an existing graph with edges in opposite
26/// directions.
27///
28/// The sets of outgoing and incoming edges handled by the methods of
29/// `Digraph` and `Network` are swapped, so incoming edges becoming
30/// outgoing edges and vice versa.
31///
32/// # Example
33///
34/// ```
35/// use rs_graph::LinkedListGraph;
36/// use rs_graph::traits::*;
37/// use rs_graph::reverse;
38/// use rs_graph::classes::star;
39///
40/// let g = star::<LinkedListGraph>(42);
41/// assert_eq!(g.num_nodes(), 43);
42/// assert_eq!(g.num_edges(), 42);
43/// assert!(g.edges().all(|e| g.node_id(g.src(e)) == 0 && g.node_id(g.snk(e)) > 0));
44/// assert!(g.outedges(g.id2node(0)).all(|(_,v)| g.node_id(v) > 0));
45/// assert!(g.inedges(g.id2node(0)).all(|(_,v)| g.node_id(v) == 0));
46/// assert_eq!(g.outedges(g.id2node(0)).count(), 42);
47/// assert_eq!(g.inedges(g.id2node(0)).count(), 0);
48///
49/// // Can be used by wrapping a reference.
50/// {
51///     let g = reverse(&g);
52///     assert_eq!(g.num_nodes(), 43);
53///     assert_eq!(g.num_edges(), 42);
54/// }
55///
56/// // Or by conversion.
57/// let g = reverse(&g);
58/// assert_eq!(g.num_nodes(), 43);
59/// assert_eq!(g.num_edges(), 42);
60/// assert!(g.edges().all(|e| g.node_id(g.snk(e)) == 0 && g.node_id(g.src(e)) > 0));
61/// assert!(g.outedges(g.id2node(0)).all(|(_,v)| g.node_id(v) == 0));
62/// assert!(g.inedges(g.id2node(0)).all(|(_,v)| g.node_id(v) > 0));
63/// assert_eq!(g.outedges(g.id2node(0)).count(), 0);
64/// assert_eq!(g.inedges(g.id2node(0)).count(), 42);
65///
66/// ```
67#[derive(Clone, Copy)]
68pub struct ReverseDigraph<'a, G>(&'a G);
69
70#[derive(Clone, Copy, PartialEq, Eq)]
71pub struct ReverseDirectedEdge<E>(E);
72
73#[derive(Clone)]
74pub struct ReverseWrapIt<I>(I);
75
76impl<'a, G, I> GraphIterator<ReverseDigraph<'a, G>> for ReverseWrapIt<I>
77where
78    I: GraphIterator<G>,
79{
80    type Item = I::Item;
81
82    fn next(&mut self, g: &ReverseDigraph<'a, G>) -> Option<I::Item> {
83        self.0.next(g.0)
84    }
85
86    fn size_hint(&self, g: &ReverseDigraph<'a, G>) -> (usize, Option<usize>) {
87        self.0.size_hint(g.0)
88    }
89
90    fn count(self, g: &ReverseDigraph<'a, G>) -> usize {
91        self.0.count(g.0)
92    }
93}
94
95impl<E> DirectedEdge for ReverseDirectedEdge<E>
96where
97    E: DirectedEdge,
98{
99    type Edge = E::Edge;
100
101    fn is_incoming(&self) -> bool {
102        self.0.is_outgoing()
103    }
104
105    fn is_outgoing(&self) -> bool {
106        self.0.is_incoming()
107    }
108
109    fn edge(&self) -> Self::Edge {
110        self.0.edge()
111    }
112}
113
114impl<'g, G> GraphType for ReverseDigraph<'g, G>
115where
116    G: GraphType,
117{
118    type Node<'a> = G::Node<'a>;
119
120    type Edge<'a> = G::Edge<'a>;
121}
122
123impl<'g, G> FiniteGraph for ReverseDigraph<'g, G>
124where
125    G: FiniteGraph,
126{
127    type NodeIt<'a> = ReverseWrapIt<G::NodeIt<'a>>
128    where
129        G: 'a,
130        'g: 'a;
131
132    type EdgeIt<'a> = ReverseWrapIt<G::EdgeIt<'a>>
133    where
134        G: 'a,
135        'g: 'a;
136
137    fn num_nodes(&self) -> usize {
138        self.0.num_nodes()
139    }
140
141    fn num_edges(&self) -> usize {
142        self.0.num_edges()
143    }
144
145    fn nodes_iter(&self) -> Self::NodeIt<'_> {
146        ReverseWrapIt(self.0.nodes_iter())
147    }
148
149    fn edges_iter(&self) -> Self::EdgeIt<'_> {
150        ReverseWrapIt(self.0.edges_iter())
151    }
152
153    fn enodes(&self, e: Self::Edge<'_>) -> (Self::Node<'_>, Self::Node<'_>) {
154        self.0.enodes(e)
155    }
156}
157
158impl<'g, G> FiniteDigraph for ReverseDigraph<'g, G>
159where
160    G: FiniteDigraph,
161{
162    fn src(&self, e: Self::Edge<'_>) -> Self::Node<'_> {
163        self.0.snk(e)
164    }
165
166    fn snk(&self, e: Self::Edge<'_>) -> Self::Node<'_> {
167        self.0.src(e)
168    }
169}
170
171impl<'g, G> Undirected for ReverseDigraph<'g, G>
172where
173    G: Undirected,
174{
175    type NeighIt<'a> = ReverseWrapIt<G::NeighIt<'a>>
176    where
177        G: 'a,
178        'g: 'a;
179
180    fn neigh_iter(&self, u: Self::Node<'_>) -> Self::NeighIt<'_> {
181        ReverseWrapIt(self.0.neigh_iter(u))
182    }
183}
184
185impl<'g, G> IndexGraph for ReverseDigraph<'g, G>
186where
187    G: IndexGraph,
188{
189    fn node_id(&self, u: Self::Node<'_>) -> usize {
190        self.0.node_id(u)
191    }
192
193    fn id2node(&self, id: usize) -> Self::Node<'_> {
194        self.0.id2node(id)
195    }
196
197    fn edge_id(&self, e: Self::Edge<'_>) -> usize {
198        self.0.edge_id(e)
199    }
200
201    fn id2edge(&self, id: usize) -> Self::Edge<'_> {
202        self.0.id2edge(id)
203    }
204}
205
206#[derive(Clone)]
207pub struct ReverseIncidentIt<I>(I);
208
209impl<'a, G, I, N, D> GraphIterator<ReverseDigraph<'a, G>> for ReverseIncidentIt<I>
210where
211    I: GraphIterator<G, Item = (D, N)>,
212    D: DirectedEdge,
213{
214    type Item = (ReverseDirectedEdge<D>, N);
215
216    fn next(&mut self, g: &ReverseDigraph<G>) -> Option<Self::Item> {
217        self.0.next(g.0).map(|(e, v)| (ReverseDirectedEdge(e), v))
218    }
219
220    fn size_hint(&self, g: &ReverseDigraph<G>) -> (usize, Option<usize>) {
221        self.0.size_hint(g.0)
222    }
223
224    fn count(self, g: &ReverseDigraph<G>) -> usize {
225        self.0.count(g.0)
226    }
227}
228
229impl<'g, G> Directed for ReverseDigraph<'g, G>
230where
231    G: Directed,
232{
233    type OutIt<'a> = ReverseWrapIt<G::InIt<'a>>
234    where
235        G: 'a,
236        'g: 'a;
237
238    type InIt<'a> = ReverseWrapIt<G::OutIt<'a>>
239    where
240        G: 'a,
241        'g: 'a;
242
243    type IncidentIt<'a> = ReverseIncidentIt<G::IncidentIt<'a>>
244    where
245        G: 'a,
246        'g: 'a,;
247
248    type DirectedEdge<'a> = ReverseDirectedEdge<G::DirectedEdge<'a>>
249    where
250        Self: 'a;
251
252    fn out_iter(&self, u: Self::Node<'_>) -> Self::OutIt<'_> {
253        ReverseWrapIt(self.0.in_iter(u))
254    }
255
256    fn in_iter(&self, u: Self::Node<'_>) -> Self::InIt<'_> {
257        ReverseWrapIt(self.0.out_iter(u))
258    }
259
260    fn incident_iter(&self, u: Self::Node<'_>) -> Self::IncidentIt<'_> {
261        ReverseIncidentIt(self.0.incident_iter(u))
262    }
263}
264
265pub fn reverse<G: Directed>(g: &G) -> ReverseDigraph<G> {
266    ReverseDigraph(g)
267}
268
269impl<'a, G> GraphTypeRef<'a> for ReverseDigraph<'a, G>
270where
271    G: GraphTypeRef<'a>,
272{
273    type Node = G::Node;
274    type Edge = G::Edge;
275}
276
277impl<'a, G> FiniteGraphRef<'a> for ReverseDigraph<'a, G>
278where
279    G: FiniteGraphRef<'a>,
280{
281    type NodeIt = ReverseWrapIt<G::NodeIt>;
282
283    type EdgeIt = ReverseWrapIt<G::EdgeIt>;
284
285    fn num_nodes(&self) -> usize {
286        self.0.num_nodes()
287    }
288
289    fn num_edges(&self) -> usize {
290        self.0.num_edges()
291    }
292
293    fn nodes_iter(&self) -> Self::NodeIt {
294        ReverseWrapIt(self.0.nodes_iter())
295    }
296
297    fn edges_iter(&self) -> Self::EdgeIt {
298        ReverseWrapIt(self.0.edges_iter())
299    }
300
301    fn enodes(&self, e: Self::Edge) -> (Self::Node, Self::Node) {
302        self.0.enodes(e)
303    }
304}
305
306impl<'a, G> FiniteDigraphRef<'a> for ReverseDigraph<'a, G>
307where
308    G: FiniteDigraphRef<'a>,
309{
310    fn src(&self, e: Self::Edge) -> Self::Node {
311        self.0.snk(e)
312    }
313
314    fn snk(&self, e: Self::Edge) -> Self::Node {
315        self.0.src(e)
316    }
317}
318
319impl<'a, G> UndirectedRef<'a> for ReverseDigraph<'a, G>
320where
321    G: UndirectedRef<'a>,
322{
323    type NeighIt = ReverseWrapIt<G::NeighIt>;
324
325    fn neigh_iter(&self, u: Self::Node) -> Self::NeighIt {
326        ReverseWrapIt(UndirectedRef::neigh_iter(self.0, u))
327    }
328}
329
330impl<'a, G> DirectedRef<'a> for ReverseDigraph<'a, G>
331where
332    G: DirectedRef<'a>,
333{
334    type OutIt = ReverseWrapIt<G::InIt>;
335
336    type InIt = ReverseWrapIt<G::OutIt>;
337
338    type IncidentIt = ReverseIncidentIt<G::IncidentIt>;
339
340    type DirectedEdge = ReverseDirectedEdge<G::DirectedEdge>;
341
342    fn out_iter(&self, u: Self::Node) -> Self::OutIt {
343        ReverseWrapIt(DirectedRef::in_iter(self.0, u))
344    }
345
346    fn in_iter(&self, u: Self::Node) -> Self::InIt {
347        ReverseWrapIt(DirectedRef::out_iter(self.0, u))
348    }
349
350    fn incident_iter(&self, u: Self::Node) -> Self::IncidentIt {
351        ReverseIncidentIt(self.0.incident_iter(u))
352    }
353}
354
355impl<'a, G> IndexGraphRef<'a> for ReverseDigraph<'a, G>
356where
357    G: IndexGraphRef<'a>,
358{
359    fn node_id(&self, u: Self::Node) -> usize {
360        self.0.node_id(u)
361    }
362
363    fn edge_id(&self, e: Self::Edge) -> usize {
364        self.0.edge_id(e)
365    }
366
367    fn id2node(&self, id: usize) -> Self::Node {
368        self.0.id2node(id)
369    }
370
371    fn id2edge(&self, id: usize) -> Self::Edge {
372        self.0.id2edge(id)
373    }
374}
rs_graph/adapters/reversedigraph.rs

rs_graph/adapters/
reversedigraph.rs
