rs-graph 0.14.1

/*
 * Copyright (c) 2017, 2018 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/>
 */

//! Traits for graph data structures.
//!
//! The traits for graph data structures provide an additional level
//! of information about (the edges of) the graph. There are three
//! levels:
//!
//! 1. `Graph`: an undirected graph, edges have no defined source or
//!     sink.
//! 2. `Digraph`: a directed graph, each edge has a designated source
//!     and a designated sink node. Furthermore, there is the concept
//!     of "outgoing" and "incoming" edges. A `Digraph` is also a
//!     `Graph`, which basically means ignoring the direction
//!     information of the edges.
//! 3. `Network`: a network is a directed graph, but each edge is
//!    actually a pair of edges: the normally directed edge and its
//!    reverse edge. Edge and reverse edge are considered equal for
//!    all purposes of a digraph (e.g. source and sink node are always
//!    source and sink of the forward edge), but the additional
//!    "reverse" information can be obtained by the methods of
//!    `Network`. Furthermore, if the network is an `IndexNetwork`, a
//!    `BiEdgeVec` can be used to store different values for edges and
//!    the reverse edges (in contrast, an `EdgeVec` always contains
//!    the same value for an edge and its reverse edge).

pub use vec::{IndexBiEdgeSlice, IndexEdgeSlice, IndexNodeSlice};
pub use vec::{IndexBiEdgeVec, IndexEdgeVec, IndexNodeVec};

/// A node in a graph.
pub trait Node: Copy + Eq {}

/// A node in a graph with a direct index.
pub trait NumberedNode: Node {
    fn index(&self) -> usize;
}

/// An edge in a graph.
pub trait Edge: Copy + Eq {}

/// An edge in a graph with a direct index.
pub trait NumberedEdge: Edge {
    fn index(&self) -> usize;
}

/// An edge in a graph with a direct biindex.
pub trait BiNumberedEdge: Edge {
    fn biindex(&self) -> usize;
}

/// Trait for a general undirected graph.
pub trait Graph<'a>
where
    Self: Sized,
{
    /// Type of a node.
    type Node: 'a + Node;

    /// Type of an edge.
    type Edge: 'a + Edge;

    /// Type of an iterator over all nodes.
    type NodeIter: 'a + Iterator<Item = Self::Node>;

    /// Type of an iterator over all edges.
    type EdgeIter: 'a + Iterator<Item = Self::Edge>;

    /// Type of an iterator over incident edges.
    type NeighIter: 'a + Iterator<Item = (Self::Edge, Self::Node)>;

    /// Return the number of nodes.
    fn num_nodes(&self) -> usize;

    /// Return the number of edges.
    fn num_edges(&self) -> usize;

    /// Return the nodes connected by an edge.
    ///
    /// The order of the nodes is undefined.
    fn enodes(&'a self, e: Self::Edge) -> (Self::Node, Self::Node);

    /// Return an iterator over all nodes.
    fn nodes(&'a self) -> Self::NodeIter;

    /// Return an iterator over all edges.
    ///
    /// This iterator traverses only the forward edges.
    fn edges(&'a self) -> Self::EdgeIter;

    /// Return an iterator over the edges adjacent to some node.
    ///
    /// This iterator traverses only the forward edges.
    fn neighs(&'a self, u: Self::Node) -> Self::NeighIter;
}

/// Trait for a general directed graph.
///
/// This trait adds a few additional methods to explicitely access the
/// direction information of an edge. In particular, the direction
/// information can be used in the following ways:
///
///  - The `src` and `snk` methods return the source and sink nodes of
///    an edge.
///  - The iterators `outedges` and `inedges` iterate only over edges
///    leaving or entering a certain node, respectively.
pub trait Digraph<'a>: Graph<'a> {
    /// Type of an iterator over the forward edges leaving a node.
    type OutEdgeIter: 'a + Iterator<Item = (Self::Edge, Self::Node)>;

    /// Type of an iterator over the backward edges entering a node.
    type InEdgeIter: 'a + Iterator<Item = (Self::Edge, Self::Node)>;

    /// Return the source node of an edge.
    fn src(&'a self, e: Self::Edge) -> Self::Node;

    /// Return the sink node of an edge.
    fn snk(&'a self, e: Self::Edge) -> Self::Node;

    /// Return an iterator over the outgoing edges of a node.
    ///
    /// The iterator returns only forward edges.
    fn outedges(&'a self, u: Self::Node) -> Self::OutEdgeIter;

    /// Return an iterator over the incoming edges of a node.
    ///
    /// The iterator returns only backward edges.
    fn inedges(&'a self, u: Self::Node) -> Self::InEdgeIter;
}

/// A network.
///
/// A network is a digraph with an additional property: each edge is
/// represented by a pair of edges, the edge and its reverse edge. The
/// methods of this trait provide access to the information, if an
/// edge is a forward or backward edge: `is_reverse`, `is_forward`,
/// `is_backward`. The reverse edge can be obtained by `reverse`. Note
/// that an edge is equal to its reverse edge, i.e. `e ==
/// g.reverse(e)`, so they can only be distinguished by the above
/// methods. In particular, `src` and `snk` always refer to the source
/// and sink node of the *forward* edge. Therefore, a forward edge
/// leaves its source node whereas its reverse edge virtually enters
/// its source node. In order to get the "virtual" source and sink,
/// use `bisrc` and `bisnk` methods.
///
/// As an additional requirement, the iterators must satisfy the following rules:
///
///  - `edges` iterates over forward edges,
///  - `outedges` iterates over forward edges,
///  - `inedges` iterates over backward edges,
///  - `neighs` iterates over outgoing forward and incoming backward edges.
pub trait Network<'a>: Digraph<'a> {
    /// Return true if e is the reverse edge of f.
    fn is_reverse(&self, e: Self::Edge, f: Self::Edge) -> bool {
        e == f && self.is_forward(e) != self.is_forward(f)
    }

    /// Return the reverse edge of e.
    fn reverse(&'a self, e: Self::Edge) -> Self::Edge;

    /// Return true if e is a forward edge.
    fn is_forward(&self, e: Self::Edge) -> bool;

    /// Return the forward edge of e.
    ///
    /// This method returns e if e is already a forward edge,
    /// otherwise it returns the reverse edge of e.
    fn forward(&'a self, e: Self::Edge) -> Self::Edge {
        if self.is_forward(e) {
            e
        } else {
            self.reverse(e)
        }
    }

    /// Return true if e is a backward edge.
    fn is_backward(&self, e: Self::Edge) -> bool {
        !self.is_forward(e)
    }

    /// Return the backward edge of e.
    ///
    /// This method returns e if e is already a backward edge,
    /// otherwise it returns the reverse edge of e.
    fn backward(&'a self, e: Self::Edge) -> Self::Edge {
        if self.is_backward(e) {
            e
        } else {
            self.reverse(e)
        }
    }

    /// Return the source of the directed edge e.
    ///
    /// If e is a forward edge, this is the same as `src` otherwise
    /// its `snk`.
    fn bisrc(&'a self, e: Self::Edge) -> Self::Node {
        if self.is_forward(e) {
            self.src(e)
        } else {
            self.snk(e)
        }
    }

    /// Return the sink of the directed edge e.
    ///
    /// If e is a forward edge, this is the same as `snk` otherwise
    /// its `src`.
    fn bisnk(&'a self, e: Self::Edge) -> Self::Node {
        if self.is_forward(e) {
            self.snk(e)
        } else {
            self.src(e)
        }
    }
}

/// Associates nodes and edges with unique ids.
pub trait IndexGraph<'a>: Graph<'a> {
    /// Return a unique id associated with a node.
    fn node_id(&self, u: Self::Node) -> usize;

    /// Return the node associated with the given id.
    ///
    /// The method panics if the id is invalid.
    fn id2node(&'a self, id: usize) -> Self::Node;

    /// Return a unique id associated with an edge.
    ///
    /// The returned id is the same for the edge and its reverse edge.
    fn edge_id(&self, e: Self::Edge) -> usize;

    /// Return the edge associated with the given id.
    ///
    /// The method returns the forward edge.
    ///
    /// The method panics if the id is invalid.
    fn id2edge(&'a self, id: usize) -> Self::Edge;
}

/// A `Digraph` that is also an `IndexGraph`.
pub trait IndexDigraph<'a>: IndexGraph<'a> + Digraph<'a> {}

impl<'a, T> IndexDigraph<'a> for T
where
    T: IndexGraph<'a> + Digraph<'a>,
{
}

/// Associates edges with unique ids for forward and backward edge.
///
/// There are no guarantees on the relation between edge and node ids.
pub trait IndexNetwork<'a>: IndexGraph<'a> + Network<'a> {
    /// Return a unique id associated with a directed edge.
    ///
    /// The returned id must be different for the edge and its reverse
    /// edge.
    fn biedge_id(&self, e: Self::Edge) -> usize;

    /// Return the edge associated with the given id.
    ///
    /// The method panics if the id is invalid.
    fn id2biedge(&'a self, id: usize) -> Self::Edge;
}

/// Marker trait for graphs with directly numbered nodes and edges.
pub trait NumberedGraph<'a>: Graph<'a>
where
    <Self as Graph<'a>>::Node: NumberedNode,
    <Self as Graph<'a>>::Edge: NumberedEdge,
{
}

impl<'a, G> NumberedGraph<'a> for G
where
    G: Graph<'a>,
    G::Node: NumberedNode,
    G::Edge: NumberedEdge,
{
}

/// Marker trait for digraphs with directly numbered nodes and edges.
pub trait NumberedDigraph<'a>: NumberedGraph<'a> + Digraph<'a>
where
    <Self as Graph<'a>>::Node: NumberedNode,
    <Self as Graph<'a>>::Edge: NumberedEdge,
{
}

impl<'a, G> NumberedDigraph<'a> for G
where
    G: Digraph<'a> + NumberedGraph<'a>,
    G::Node: NumberedNode,
    G::Edge: NumberedEdge,
{
}

/// Marker trait for networks with directly numbered nodes and edges.
pub trait NumberedNetwork<'a>: NumberedDigraph<'a> + Network<'a>
where
    <Self as Graph<'a>>::Node: NumberedNode,
    <Self as Graph<'a>>::Edge: NumberedEdge + BiNumberedEdge,
{
}

impl<'a, G> NumberedNetwork<'a> for G
where
    G: Network<'a> + NumberedDigraph<'a>,
    G::Node: NumberedNode,
    G::Edge: NumberedEdge + BiNumberedEdge,
{
}

impl<'a, G> Graph<'a> for &'a 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).num_nodes()
    }

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

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

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

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

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

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

    type InEdgeIter = G::InEdgeIter;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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