Skip to main content

rustc_data_structures/graph/
reversed.rs

1use crate::graph::{DirectedGraph, Predecessors, Successors};
2
3/// View that reverses the direction of edges in its underlying graph, so that
4/// successors become predecessors and vice-versa.
5///
6/// Because of `impl<G: Graph> Graph for &G`, the underlying graph can be
7/// wrapped by-reference instead of by-value if desired.
8#[derive(#[automatically_derived]
impl<G: ::core::clone::Clone> ::core::clone::Clone for ReversedGraph<G> {
    #[inline]
    fn clone(&self) -> ReversedGraph<G> {
        ReversedGraph { inner: ::core::clone::Clone::clone(&self.inner) }
    }
}Clone, #[automatically_derived]
impl<G: ::core::marker::Copy> ::core::marker::Copy for ReversedGraph<G> { }Copy, #[automatically_derived]
impl<G: ::core::fmt::Debug> ::core::fmt::Debug for ReversedGraph<G> {
    #[inline]
    fn fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result {
        ::core::fmt::Formatter::debug_struct_field1_finish(f, "ReversedGraph",
            "inner", &&self.inner)
    }
}Debug)]
9pub struct ReversedGraph<G> {
10    pub inner: G,
11}
12
13impl<G> ReversedGraph<G> {
14    pub fn new(inner: G) -> Self {
15        Self { inner }
16    }
17}
18
19impl<G: DirectedGraph> DirectedGraph for ReversedGraph<G> {
20    type Node = G::Node;
21
22    fn num_nodes(&self) -> usize {
23        self.inner.num_nodes()
24    }
25}
26
27// Implementing `StartNode` is not possible in general, because the start node
28// of an underlying graph is instead an _end_ node in the reversed graph.
29// But would be possible to define another wrapper type that adds an explicit
30// start node to its underlying graph, if desired.
31
32impl<G: Predecessors> Successors for ReversedGraph<G> {
33    fn successors(&self, node: Self::Node) -> impl Iterator<Item = Self::Node> {
34        self.inner.predecessors(node)
35    }
36}
37
38impl<G: Successors> Predecessors for ReversedGraph<G> {
39    fn predecessors(&self, node: Self::Node) -> impl Iterator<Item = Self::Node> {
40        self.inner.successors(node)
41    }
42}