rs-graph 0.7.0

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

//! Graphs embedded in another struct.
//!
//! Sometimes one needs additional attributes associated with the nodes or edges of a graph.
//! The simplest way is to store them in a `NodeVec` or `EdgeVec`. If
//! these attributes are tightly related to the graph, it is convenient to store the graph
//! together with the attributes in a single struct, e.g.
//!
//! ```
//! use rs_graph::linkedlistgraph::*;
//!
//! struct MyGraph {
//!     graph: LinkedListGraph,
//!     balances: Vec<f64>,
//!     bounds: Vec<f64>,
//! }
//! ```
//!
//! The problem is that `MyGraph` itself does not implement the graph
//! traits `Graph`, `Digraph` and so on, and can therefore not used
//! directly for methods that need values of this type.
//!
//! The trait `WrappedGraph` in this module can be used to automate the
//! tedious task of implementing the traits. If `MyGraph` implements
//! `WrappedGraph`, the graph traits are automatically implemented for
//! `MyGraph` by forwarding all methods to the embedded graph.
//!
//! ```
//! # use rs_graph::linkedlistgraph::*;
//! #
//! # struct MyGraph {
//! #     graph: LinkedListGraph,
//! #     balances: Vec<f64>,
//! #     bounds: Vec<f64>,
//! # }
//! #
//!
//! use rs_graph::{Graph, IndexGraph, WrappedGraph};
//! use rs_graph::classes;
//!
//! impl WrappedGraph for MyGraph {
//!     type Graph = LinkedListGraph;
//!     fn from_graph(g: Self::Graph) -> Self {
//!         let n = g.num_nodes();
//!         MyGraph {
//!             graph: g,
//!             balances: vec![0.0; n],
//!             bounds: vec![0.0; n],
//!         }
//!     }
//!
//!     fn as_graph(&self) -> &Self::Graph { &self.graph }
//! }
//!
//! impl MyGraph {
//!     fn balance_mut(&mut self, u: Node) -> &mut f64 {
//!         &mut self.balances[self.graph.node_id(u)]
//!     }
//!
//!     fn bound_mut(&mut self, e: Edge) -> &mut f64 {
//!         &mut self.bounds[self.graph.edge_id(e)]
//!     }
//! }
//!
//! let mut g: MyGraph = classes::path(5);
//! let (s, t) = (g.id2node(0), g.id2node(4));
//! *g.balance_mut(s) = 1.0;
//! *g.balance_mut(t) = -1.0;
//! for e in g.edges() { *g.bound_mut(e) = g.edge_id(e) as f64; }
//! ```
//!
//! For a different approach, see the `attributed` module.

use graph::{Graph, Digraph, Network, IndexGraph, IndexNetwork};
use builder::Builder;

use std::marker::PhantomData;

/// An embedded graph.
///
/// This trait is similar to the combination `From<G> +
/// Deref<Target=G>` but specialized for graphs.
pub trait WrappedGraph {
    /// The embedded graph type.
    type Graph;

    /// Create the embedding structure from a graph.
    fn from_graph(g: Self::Graph) -> Self;

    /// Return a reference to the embedded graph.
    fn as_graph(&self) -> &Self::Graph;
}

/// An embedded, mutable graph.
pub trait WrappedGraphMut: WrappedGraph {
    fn as_mut_graph(&mut self) -> &mut Self::Graph;
}

/// A builder for a wrapped graph.
pub struct WrappedBuilder<G,B>(B, PhantomData<G>) where G: WrappedGraph;

impl<G,B> Builder for WrappedBuilder<G,B>
    where G: WrappedGraph,
          B: Builder<Graph=G::Graph>,
{
    type Graph = G;
    type Node = B::Node;
    type Edge = B::Edge;

    fn new() -> Self {
        WrappedBuilder(B::new(), PhantomData)
    }

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

    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 {
        WrappedGraph::from_graph(self.0.to_graph())
    }
}

impl<'a,T> Graph<'a> for T
    where T: WrappedGraph,
          T::Graph: Graph<'a>
{
    type Node = <T::Graph as Graph<'a>>::Node;
    type Edge = <T::Graph as Graph<'a>>::Edge;
    type NodeIter = <T::Graph as Graph<'a>>::NodeIter;
    type EdgeIter = <T::Graph as Graph<'a>>::EdgeIter;
    type NeighIter = <T::Graph as Graph<'a>>::NeighIter;
    type Builder = WrappedBuilder<T, <T::Graph as Graph<'a>>::Builder>;

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

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

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

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

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

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

impl<'a,T> Digraph<'a> for T
    where T: WrappedGraph,
          T::Graph: Digraph<'a>
{
    type OutEdgeIter = <T::Graph as Digraph<'a>>::OutEdgeIter;
    type InEdgeIter = <T::Graph as Digraph<'a>>::InEdgeIter;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

impl<T> Builder for T
    where T: WrappedGraphMut,
          T::Graph: Builder,
{
    type Graph = T;
    type Node = <T::Graph as Builder>::Node;
    type Edge = <T::Graph as Builder>::Edge;

    fn new() -> Self {
        Self::from_graph(<T::Graph as Builder>::new())
    }

    fn with_capacities(nnodes: usize, nedges: usize) -> Self {
        Self::from_graph(<T::Graph as Builder>::with_capacities(nnodes, nedges))
    }

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

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

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

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

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

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

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