rs-graph 0.14.1

/*
 * Copyright (c) 2017 Frank Fischer <frank-fischer@shadow-soft.de>
 *
 * This program is free software: you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see  <http://www.gnu.org/licenses/>
 */

//! Reverse the direction of the edges of a digraph.

use {Builder, Digraph, Graph, IndexGraph, IndexNetwork, Network};

/// A digraph wrapping an existing graph with edges in opposite
/// directions.
///
/// The sets of outgoing and incoming edges handled by the methods of
/// `Digraph` and `Network` are swapped, so incoming edges becoming
/// outgoing edges and vice versa.
///
/// # Example
///
/// ```
/// use rs_graph::{Graph, Digraph, IndexGraph, ReverseDigraph, LinkedListGraph};
/// use rs_graph::reverse;
/// use rs_graph::classes::star;
///
/// let g = star::<LinkedListGraph>(42);
/// assert_eq!(g.num_nodes(), 43);
/// assert_eq!(g.num_edges(), 42);
/// assert!(g.edges().all(|e| g.node_id(g.src(e)) == 0 && g.node_id(g.snk(e)) > 0));
/// assert!(g.outedges(g.id2node(0)).all(|(_,v)| g.node_id(v) > 0));
/// assert!(g.inedges(g.id2node(0)).all(|(_,v)| g.node_id(v) == 0));
/// assert_eq!(g.outedges(g.id2node(0)).count(), 42);
/// assert_eq!(g.inedges(g.id2node(0)).count(), 0);
///
/// // Can be used by wrapping a reference.
/// {
///     let g = reverse(&g);
///     assert_eq!(g.num_nodes(), 43);
///     assert_eq!(g.num_edges(), 42);
/// }
///
/// // Or by conversion.
/// let g = reverse(g);
/// assert_eq!(g.num_nodes(), 43);
/// assert_eq!(g.num_edges(), 42);
/// assert!(g.edges().all(|e| g.node_id(g.snk(e)) == 0 && g.node_id(g.src(e)) > 0));
/// assert!(g.outedges(g.id2node(0)).all(|(_,v)| g.node_id(v) == 0));
/// assert!(g.inedges(g.id2node(0)).all(|(_,v)| g.node_id(v) > 0));
/// assert_eq!(g.outedges(g.id2node(0)).count(), 0);
/// assert_eq!(g.inedges(g.id2node(0)).count(), 42);
///
/// ```
pub struct ReverseDigraph<G>(G);

impl<'a, G> Graph<'a> for ReverseDigraph<G>
where
    G: Graph<'a>,
{
    type Node = G::Node;

    type Edge = G::Edge;

    type NodeIter = G::NodeIter;

    type EdgeIter = G::EdgeIter;

    type NeighIter = G::NeighIter;

    fn num_nodes(&self) -> usize {
        self.0.num_nodes()
    }

    fn num_edges(&self) -> usize {
        self.0.num_edges()
    }

    fn enodes(&'a self, e: Self::Edge) -> (Self::Node, Self::Node) {
        self.0.enodes(e)
    }

    fn nodes(&'a self) -> Self::NodeIter {
        self.0.nodes()
    }

    fn edges(&'a self) -> Self::EdgeIter {
        self.0.edges()
    }

    fn neighs(&'a self, u: Self::Node) -> Self::NeighIter {
        self.0.neighs(u)
    }
}

impl<'a, G> IndexGraph<'a> for ReverseDigraph<G>
where
    G: IndexGraph<'a>,
{
    fn node_id(&self, u: Self::Node) -> usize {
        self.0.node_id(u)
    }

    fn id2node(&'a self, id: usize) -> Self::Node {
        self.0.id2node(id)
    }

    fn edge_id(&self, e: Self::Edge) -> usize {
        self.0.edge_id(e)
    }

    fn id2edge(&'a self, id: usize) -> Self::Edge {
        self.0.id2edge(id)
    }
}

impl<'a, G> Digraph<'a> for ReverseDigraph<G>
where
    G: Digraph<'a>,
{
    type OutEdgeIter = G::InEdgeIter;

    type InEdgeIter = G::OutEdgeIter;

    fn src(&'a self, e: Self::Edge) -> Self::Node {
        self.0.snk(e)
    }

    fn snk(&'a self, e: Self::Edge) -> Self::Node {
        self.0.src(e)
    }

    fn outedges(&'a self, u: Self::Node) -> Self::OutEdgeIter {
        self.0.inedges(u)
    }

    fn inedges(&'a self, u: Self::Node) -> Self::InEdgeIter {
        self.0.outedges(u)
    }
}

impl<'a, G> Network<'a> for ReverseDigraph<G>
where
    G: Network<'a>,
{
    fn is_reverse(&self, e: Self::Edge, f: Self::Edge) -> bool {
        self.0.is_reverse(e, f)
    }

    fn reverse(&'a self, e: Self::Edge) -> Self::Edge {
        self.0.reverse(e)
    }

    fn is_forward(&self, e: Self::Edge) -> bool {
        self.0.is_forward(e)
    }

    fn forward(&'a self, e: Self::Edge) -> Self::Edge {
        self.0.forward(e)
    }

    fn is_backward(&self, e: Self::Edge) -> bool {
        self.0.is_backward(e)
    }

    fn backward(&'a self, e: Self::Edge) -> Self::Edge {
        self.0.backward(e)
    }

    fn bisrc(&'a self, e: Self::Edge) -> Self::Node {
        self.0.bisnk(e)
    }

    fn bisnk(&'a self, e: Self::Edge) -> Self::Node {
        self.0.bisrc(e)
    }
}

impl<'a, G> IndexNetwork<'a> for ReverseDigraph<G>
where
    G: IndexNetwork<'a>,
{
    fn biedge_id(&self, e: Self::Edge) -> usize {
        self.0.biedge_id(e)
    }

    fn id2biedge(&'a self, id: usize) -> Self::Edge {
        self.0.id2biedge(id)
    }
}

/// Builder for a reversed digraph.
pub struct ReverseDigraphBuilder<B>(B);

impl<B> Builder for ReverseDigraphBuilder<B>
where
    B: Builder,
{
    type Graph = ReverseDigraph<B::Graph>;

    type Node = B::Node;

    type Edge = B::Edge;

    fn new() -> Self {
        ReverseDigraphBuilder(B::new())
    }

    fn with_capacities(nnodes: usize, nedges: usize) -> Self {
        ReverseDigraphBuilder(B::with_capacities(nnodes, nedges))
    }

    fn reserve(&mut self, nnodes: usize, nedges: usize) {
        self.0.reserve(nnodes, nedges)
    }

    fn add_node(&mut self) -> Self::Node {
        self.0.add_node()
    }

    fn add_nodes(&mut self, n: usize) -> Vec<Self::Node> {
        self.0.add_nodes(n)
    }

    fn add_edge(&mut self, u: Self::Node, v: Self::Node) -> Self::Edge {
        self.0.add_edge(u, v)
    }

    fn node2id(&self, u: Self::Node) -> usize {
        self.0.node2id(u)
    }

    fn edge2id(&self, e: Self::Edge) -> usize {
        self.0.edge2id(e)
    }

    fn to_graph(self) -> Self::Graph {
        ReverseDigraph(self.0.to_graph())
    }
}

impl<G> From<G> for ReverseDigraph<G> {
    fn from(g: G) -> Self {
        ReverseDigraph(g)
    }
}

pub fn reverse<'a, G: Digraph<'a>>(g: G) -> ReverseDigraph<G> {
    ReverseDigraph(g)
}