rs-graph 0.6.3

/*
 * 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/>
 */

//! 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 normal 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).

use builder::Builder;

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

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

/// 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)>;

    /// The default builder to construct this graph.
    type Builder: Builder<Graph=Self>;

    /// 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;
}