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

//! Extend a graph with attributes.
//!
//! 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 struct `Attributed` in this module can be used to automate the
//! tedious task of implementing the traits.
//!
//! For a different approach, see the `wrapped` module.

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

use std::ops::{Deref, DerefMut};
use std::marker::PhantomData;

/// An attributed graph.
///
/// This trait adds three attributes to a graph:
///
/// 1. attributes for the graph itself via `attr` and `attr_mut`.
/// 2. attributes for the nodes via `node` and `node_mut`.
/// 3. attributes for the edges via `node` and `node_mut`.
///
/// Furthermore, if you need to mutate some of the attributes, the
/// `split` method, splits the graph into two references: one for pure
/// read-only graph access and one for mutable access to the
/// attributes. This allows to mutate the attributes while ensuring
/// that the graph structure remains unchanged (and thus no nodes or
/// edges may be added.)
pub trait AttributedGraph<'a> {
    type Graph : Graph<'a>;

    type Attributes : Attributes<Node=<Self::Graph as Graph<'a>>::Node,
                                 Edge=<Self::Graph as Graph<'a>>::Edge>;

    /// Return a read-only graph reference and a mutable attributes reference.
    fn split(&'a mut self) -> (&Self::Graph, Self::Attributes);

    /// Return the graph attributes.
    fn attr(&'a self) -> &'a <Self::Attributes as Attributes>::GraphAttr;

    /// Return the graph attributes.
    fn attr_mut(&'a mut self) -> &'a mut <Self::Attributes as Attributes>::GraphAttr;

    /// Return the attributes of a node.
    fn node(&'a self, u: <Self::Graph as Graph<'a>>::Node) -> &'a <Self::Attributes as Attributes>::NodeAttr;

    /// Return the attributes of a node.
    fn node_mut(&'a mut self, u: <Self::Graph as Graph<'a>>::Node) -> &'a mut <Self::Attributes as Attributes>::NodeAttr;

    /// Return the attributes of an edge.
    fn edge(&'a self, e: <Self::Graph as Graph<'a>>::Edge) -> &'a <Self::Attributes as Attributes>::EdgeAttr;

    /// Return the attributes of an edge.
    fn edge_mut(&'a mut self, e: <Self::Graph as Graph<'a>>::Edge) -> &'a mut <Self::Attributes as Attributes>::EdgeAttr;
}

/// An attributed network.
///
/// This trait adds another type of attributes to a graph: attributes
/// associated with each forward and backward edge of a network (i.e.
/// with so called "biedges").
pub trait AttributedNetwork<'a>: AttributedGraph<'a>
    where Self::Graph: Network<'a>,
          Self::Attributes: 'a + NetworkAttributes<Node=<<Self as AttributedGraph<'a>>::Graph as Graph<'a>>::Node,
                                                   Edge=<<Self as AttributedGraph<'a>>::Graph as Graph<'a>>::Edge>
{
    /// Return the attributes of a biedge.
    fn biedge(&'a self, e: <Self::Graph as Graph<'a>>::Edge)
              -> &'a <Self::Attributes as NetworkAttributes>::BiEdgeAttr;

    /// Return the attributes of a biedge.
    fn biedge_mut(&'a mut self, e: <Self::Graph as Graph<'a>>::Edge)
              -> &'a mut <Self::Attributes as NetworkAttributes>::BiEdgeAttr;
}

/// This trait provides (mutable) access to the attributes of an attributed graph.
///
/// A structure implementing this trait is returned as the second
/// value by the `split` method of an attributed graph.
pub trait Attributes {
    /// Type of nodes of the associated graph.
    type Node : Node;
    /// Type of edges of the associated graph.
    type Edge : Edge;
    /// Type of graph attributes.
    type GraphAttr;
    /// Type of node attributes.
    type NodeAttr;
    /// Type of edge attributes.
    type EdgeAttr;

    /// Return the graph attributes.
    fn attr(&self) -> &Self::GraphAttr;

    /// Return the graph attributes.
    fn attr_mut(&mut self) -> &mut Self::GraphAttr;

    /// Return the attributes of a node.
    fn node(&self, u: Self::Node) -> &Self::NodeAttr;

    /// Return the attributes of a node.
    fn node_mut(&mut self, u: Self::Node) -> &mut Self::NodeAttr;

    /// Return the attributes of an edge.
    fn edge(&self, e: Self::Edge) -> &Self::EdgeAttr;

    /// Return the attributes of an edge.
    fn edge_mut(&mut self, e: Self::Edge) -> &mut Self::EdgeAttr;
}

/// This trait provides (mutable) access to the attributes of a network.
///
/// A structure implementing this trait is returned as the second
/// value by the `split` method of an attributed network.
pub trait NetworkAttributes : Attributes {
    /// Type of biedge attributes.
    type BiEdgeAttr;

    /// Return the attributes of a biedge.
    fn biedge(&self, e: Self::Edge) -> &Self::BiEdgeAttr;

    /// Return the attributes of a biedge.
    fn biedge_mut(&mut self, e: Self::Edge) -> &mut Self::BiEdgeAttr;
}

/// Wrapper to attach attributes with a graph.
///
/// This is a wrapper struct that adds additional attributes to an
/// arbitrary graph. The type parameters are
///
/// - 'Gx` the type of graph attributes.
/// - 'Nx` the type of node attributes.
/// - 'Ex` the type of edge attributes.
/// - 'Ax` the type of biedge attributes.
///
/// The attributed graph implements `Graph`, `Digraph` and `Network` if the
/// the wrapped graph does.
///
/// # Example
///
/// ```
/// use rs_graph::{Graph, LinkedListGraph, classes};
/// use rs_graph::{Attributes, Attributed, AttributedGraph};
///
/// #[derive(Default)]
/// struct NodeAttr {
///     balance: f64,
/// }
///
/// #[derive(Default)]
/// struct EdgeAttr {
///     flow: f64,
/// }
///
/// type MyGraph = Attributed<LinkedListGraph, (), NodeAttr, EdgeAttr>;
/// let mut g: MyGraph = classes::complete_bipartite(3,4);
///
/// {
///     let (g, mut attr) = g.split();
///     for u in g.nodes() {
///         attr.node_mut(u).balance = 42.0;
///     }
///     for e in g.edges() {
///         attr.edge_mut(e).flow = 1.5;
///     }
/// }
///
/// assert!(g.nodes().all(|u| g.node(u).balance == 42.0));
/// assert!(g.edges().all(|e| g.edge(e).flow == 1.5));
/// ```

pub struct Attributed<G, Gx=(), Nx=(), Ex=(), Ax=()> {
    graph: G,
    attrs: AttributedAttrs<Gx, Nx, Ex, Ax>,
}

/// The default implementation of attributes.
///
/// The node, edge and biedge attributes are stored in vectors.
#[derive(Default)]
pub struct AttributedAttrs<Gx, Nx, Ex, Ax> {
    attr: Gx,
    nattrs: Vec<Nx>,
    eattrs: Vec<Ex>,
    aattrs: Vec<Ax>,
}

impl<Gx, Nx, Ex, Ax> AttributedAttrs<Gx, Nx, Ex, Ax>
    where Gx: Default,
          Nx: Default,
          Ex: Default,
          Ax: Default,
{
    fn with_size(n: usize, m: usize) -> Self {
        AttributedAttrs {
            attr: Gx::default(),
            nattrs: (0..n).map(|_| Default::default()).collect(),
            eattrs: (0..m).map(|_| Default::default()).collect(),
            aattrs: (0..m*2).map(|_| Default::default()).collect(),
        }
    }
}

/// Accessor for graph attributes.
pub struct GraphAttrs<'a, G, Gx, Nx, Ex, Ax>
    where G: 'a + Graph<'a>,
          Gx: 'a, Nx: 'a, Ex: 'a, Ax: 'a
{
    graph: &'a G,
    attrs: &'a mut AttributedAttrs<Gx, Nx, Ex, Ax>,
}

impl<'a, G, Gx, Nx, Ex, Ax> Attributes for GraphAttrs<'a, G, Gx, Nx, Ex, Ax>
    where G: IndexGraph<'a>
{
    type Node = G::Node;
    type Edge = G::Edge;
    type GraphAttr = Gx;
    type NodeAttr = Nx;
    type EdgeAttr = Ex;

    fn attr(&self) -> &Self::GraphAttr { &self.attrs.attr }

    fn attr_mut(&mut self) -> &mut Self::GraphAttr { &mut self.attrs.attr }

    fn node(&self, u: Self::Node) -> &Self::NodeAttr {
        &self.attrs.nattrs[self.graph.node_id(u)]
    }

    fn node_mut(&mut self, u: Self::Node) -> &mut Self::NodeAttr {
        &mut self.attrs.nattrs[self.graph.node_id(u)]
    }

    fn edge(&self, e: Self::Edge) -> &Self::EdgeAttr {
        &self.attrs.eattrs[self.graph.edge_id(e)]
    }

    fn edge_mut(&mut self, e: Self::Edge) -> &mut Self::EdgeAttr {
        &mut self.attrs.eattrs[self.graph.edge_id(e)]
    }
}

impl<'a, G, Gx, Nx, Ex, Ax> Deref for GraphAttrs<'a, G, Gx, Nx, Ex, Ax>
    where G: IndexGraph<'a>
{
    type Target = Gx;
    fn deref(&self) -> &Gx {
        &self.attrs.attr
    }
}

impl<'a, G, Gx, Nx, Ex, Ax> DerefMut for GraphAttrs<'a, G, Gx, Nx, Ex, Ax>
    where G: IndexGraph<'a>
{
    fn deref_mut(&mut self) -> &mut Gx {
        &mut self.attrs.attr
    }
}

impl<'a, G, Gx, Nx, Ex, Ax> NetworkAttributes for GraphAttrs<'a, G, Gx, Nx, Ex, Ax>
    where G: IndexNetwork<'a>
{
    type BiEdgeAttr = Ax;

    fn biedge(&self, e: Self::Edge) -> &Self::BiEdgeAttr {
        &self.attrs.aattrs[self.graph.biedge_id(e)]
    }

    fn biedge_mut(&mut self, e: Self::Edge) -> &mut Self::BiEdgeAttr {
        &mut self.attrs.aattrs[self.graph.biedge_id(e)]
    }
}

/// Default builder for an attributes graph.
///
/// This builder requires the attributes to be default constructable.
/// All attributes will be initialized with these default values.
pub struct AttributedBuilder<B, Gx, Nx, Ex, Ax>(B, PhantomData<(Gx, Nx, Ex, Ax)>);

impl<'b, B, G, Gx, Nx, Ex, Ax> Builder for AttributedBuilder<B, Gx, Nx, Ex, Ax>
    where B: Builder<Graph=G>,
          G: Graph<'b>,
          Gx: Default,
          Nx: Default,
          Ex: Default,
          Ax: Default,
{
    type Graph = Attributed<G, Gx, Nx, Ex, Ax>;
    type Node = B::Node;
    type Edge = B::Edge;

    fn with_capacities(nnodes: usize, nedges: usize) -> Self {
        AttributedBuilder(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 node_id(&self, u: Self::Node) -> usize {
        self.0.node_id(u)
    }

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

    fn to_graph(self) -> Attributed<G, Gx, Nx, Ex, Ax>
    {
        let graph = self.0.to_graph();
        let attrs = AttributedAttrs::with_size(graph.num_nodes(), graph.num_edges());
        Attributed {graph, attrs,}
    }
}

impl<'a, G, Gx, Nx, Ex, Ax> Graph<'a> for Attributed<G, Gx, Nx, Ex, Ax>
    where G: Graph<'a>,
          Gx: Default,
          Nx: Default,
          Ex: Default,
          Ax: Default,
{
    type Node = <G as Graph<'a>>::Node;
    type Edge = <G as Graph<'a>>::Edge;
    type NodeIter = <G as Graph<'a>>::NodeIter;
    type EdgeIter = <G as Graph<'a>>::EdgeIter;
    type NeighIter = <G as Graph<'a>>::NeighIter;
    type Builder = AttributedBuilder<G::Builder, Gx, Nx, Ex, Ax>;

    fn num_nodes(&self) -> usize { self.graph.num_nodes() }
    fn num_edges(&self) -> usize { self.graph.num_edges() }
    fn enodes(&'a self, e: Self::Edge) -> (Self::Node, Self::Node) { self.graph.enodes(e) }
    fn nodes(&'a self) -> Self::NodeIter { self.graph.nodes() }
    fn edges(&'a self) -> Self::EdgeIter { self.graph.edges() }
    fn neighs(&'a self, u: Self::Node) -> Self::NeighIter { self.graph.neighs(u) }
}

impl<'a, G, Gx, Nx, Ex, Ax> Digraph<'a> for Attributed<G, Gx, Nx, Ex, Ax>
    where G: Digraph<'a>,
          Gx: Default,
          Nx: Default,
          Ex: Default,
          Ax: Default,
{
    type OutEdgeIter = G::OutEdgeIter;
    type InEdgeIter = G::InEdgeIter;

    fn src(&'a self, e: Self::Edge) -> Self::Node { self.graph.src(e) }
    fn snk(&'a self, e: Self::Edge) -> Self::Node { self.graph.snk(e) }
    fn outedges(&'a self, u: Self::Node) -> Self::OutEdgeIter { self.graph.outedges(u) }
    fn inedges(&'a self, u: Self::Node) -> Self::InEdgeIter { self.graph.inedges(u) }
}

impl<'a, G, Gx, Nx, Ex, Ax> Network<'a> for Attributed<G, Gx, Nx, Ex, Ax>
    where G: Network<'a>,
          Gx: Default,
          Nx: Default,
          Ex: Default,
          Ax: Default,
{
    fn is_reverse(&self, e: Self::Edge, f: Self::Edge) -> bool { self.graph.is_reverse(e, f) }
    fn reverse(&'a self, e: Self::Edge) -> Self::Edge { self.graph.reverse(e) }
    fn is_forward(&self, e: Self::Edge) -> bool { self.graph.is_forward(e) }
    fn forward(&'a self, e: Self::Edge) -> Self::Edge { self.graph.forward(e) }
    fn is_backward(&self, e: Self::Edge) -> bool { self.graph.is_backward(e) }
    fn backward(&'a self, e: Self::Edge) -> Self::Edge { self.graph.backward(e) }
}

impl<'a, G, Gx, Nx, Ex, Ax> IndexGraph<'a> for Attributed<G, Gx, Nx, Ex, Ax>
    where G: IndexGraph<'a>,
          Gx: Default,
          Nx: Default,
          Ex: Default,
          Ax: Default,
{
    fn node_id(&self, u: Self::Node) -> usize { self.graph.node_id(u) }
    fn id2node(&'a self, id: usize) -> Self::Node { self.graph.id2node(id) }
    fn edge_id(&self, e: Self::Edge) -> usize { self.graph.edge_id(e) }
    fn id2edge(&'a self, id: usize) -> Self::Edge { self.graph.id2edge(id) }
}

impl<'a, G, Gx, Nx, Ex, Ax> IndexNetwork<'a> for Attributed<G, Gx, Nx, Ex, Ax>
    where G: IndexNetwork<'a>,
          Gx: Default,
          Nx: Default,
          Ex: Default,
          Ax: Default,
{
    fn biedge_id(&self, e: Self::Edge) -> usize { self.graph.biedge_id(e) }
    fn id2biedge(&'a self, id: usize) -> Self::Edge { self.graph.id2biedge(id) }
}

impl<'a, G, Gx, Nx, Ex, Ax> AttributedGraph<'a> for Attributed<G, Gx, Nx, Ex, Ax>
    where G: 'a + IndexGraph<'a>,
          Gx: 'a + Default,
          Nx: 'a + Default,
          Ex: 'a + Default,
          Ax: 'a + Default,
{
    type Graph = G;
    type Attributes = GraphAttrs<'a, G, Gx, Nx, Ex, Ax>;

    fn split(&'a mut self) -> (&G, Self::Attributes) {
        (&self.graph, GraphAttrs{ graph: &self.graph, attrs: &mut self.attrs })
    }

    fn attr(&self) -> &Gx {
        &self.attrs.attr
    }

    fn attr_mut(&mut self) -> &mut Gx {
        &mut self.attrs.attr
    }

    fn node(&self, u: G::Node) -> &Nx {
        &self.attrs.nattrs[self.graph.node_id(u)]
    }

    fn node_mut(&mut self, u: G::Node) -> &mut Nx {
        &mut self.attrs.nattrs[self.graph.node_id(u)]
    }

    fn edge(&self, e: G::Edge) -> &Ex {
        &self.attrs.eattrs[self.graph.edge_id(e)]
    }

    fn edge_mut(&mut self, e: G::Edge) -> &mut Ex {
        &mut self.attrs.eattrs[self.graph.edge_id(e)]
    }
}


impl<'a, G, Gx, Nx, Ex, Ax> AttributedNetwork<'a> for Attributed<G, Gx, Nx, Ex, Ax>
    where G: 'a + IndexNetwork<'a>,
          Gx: 'a + Default,
          Nx: 'a + Default,
          Ex: 'a + Default,
          Ax: 'a + Default,
{
    fn biedge(&self, e: G::Edge) -> &Ax {
        &self.attrs.aattrs[self.graph.biedge_id(e)]
    }

    fn biedge_mut(&mut self, e: G::Edge) -> &mut Ax {
        &mut self.attrs.aattrs[self.graph.biedge_id(e)]
    }
}