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

//! A linked-list based graph implementation.
//!
//! This is an efficient default implementation of a graph.
//!
//! `LinkedListGraph` provides directed arc access (i.e. implements
//! `Network`).
//!
//! Node and edge data are stored in an array (Vec), nodes and edges
//! are identified by indices. Forward edges have even indices,
//! backward edges have the odd indices directly following the
//! corresponding forward edge. The external edge index is the edge
//! index shifted right by one bit (the lsb is removed), but a user
//! should not rely on that. The node and edge indices can be
//! retrieved using the `IndexGraph` and `IndexNetwork` traits.
//!
//! `LinkedListGraph` can be constructed (it implements `Builder`),
//! but nodes and edges cannot be removed.

use builder::{Buildable, Builder};
use graph::{self, Digraph, Graph, Network};
use graph::{BiNumberedEdge, NumberedEdge, NumberedNode};
use graph::{IndexGraph, IndexNetwork};

use num::iter::{range, range_step, Range, RangeStep};
use num::traits::{PrimInt, Unsigned};

use std::fmt;
use std::hash::{Hash, Hasher};

/// Node of a linked list graph.
///
/// This is basically a newtype of the node index.
#[derive(PartialEq, Eq, Clone, Copy, Debug, Hash)]
pub struct Node<ID = u32>(ID)
where
    ID: PrimInt + Unsigned;

impl<ID> graph::Node for Node<ID>
where
    ID: PrimInt + Unsigned,
{
}

impl<ID> fmt::Display for Node<ID>
where
    ID: PrimInt + Unsigned + fmt::Display,
{
    fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
        write!(f, "{}", self.0)
    }
}

impl<ID> NumberedNode for Node<ID>
where
    ID: PrimInt + Unsigned,
{
    fn index(&self) -> usize {
        self.0.to_usize().unwrap()
    }
}

/// Edge of a linked list graph.
///
/// This is basically a newtype of the *arc* index. Note that
/// `e == g.reverse(e)`.
#[derive(Eq, Clone, Copy, Debug)]
pub struct Edge<ID = u32>(ID)
where
    ID: PrimInt + Unsigned;

impl<ID> PartialEq for Edge<ID>
where
    ID: PrimInt + Unsigned,
{
    fn eq(&self, other: &Self) -> bool {
        (self.0 >> 1) == (other.0 >> 1)
    }
}

impl<ID> graph::Edge for Edge<ID>
where
    ID: PrimInt + Unsigned,
{
}

impl<ID> fmt::Display for Edge<ID>
where
    ID: PrimInt + Unsigned + fmt::Display,
{
    fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
        write!(
            f,
            "{}{}",
            if (self.0 & ID::one()).is_zero() { "+" } else { "-" },
            self.0 >> 1
        )
    }
}

impl<ID> Hash for Edge<ID>
where
    ID: PrimInt + Unsigned + Hash,
{
    fn hash<H: Hasher>(&self, state: &mut H) {
        (self.0 >> 1).hash(state)
    }
}

impl<ID> NumberedEdge for Edge<ID>
where
    ID: PrimInt + Unsigned,
{
    fn index(&self) -> usize {
        (self.0 >> 1).to_usize().unwrap()
    }
}

impl<ID> BiNumberedEdge for Edge<ID>
where
    ID: PrimInt + Unsigned,
{
    fn biindex(&self) -> usize {
        self.0.to_usize().unwrap()
    }
}

/// The linked list based graph data structure.
#[cfg_attr(feature = "serialize", derive(Serialize, Deserialize))]
pub struct LinkedListGraph<ID = u32> {
    /// List of nodes.
    nodes: Vec<NodeData<ID>>,
    /// List of edges.
    edges: Vec<EdgeData<ID>>,
}

/// Data for a node in a linked list graph.
#[cfg_attr(feature = "serialize", derive(Serialize, Deserialize))]
struct NodeData<ID> {
    /// The first adjacent edge.
    first: ID,
}

/// Data for an edge in the linked list graph.
#[cfg_attr(feature = "serialize", derive(Serialize, Deserialize))]
struct EdgeData<ID> {
    /// The sink node.
    snk: ID,
    /// The next arc adjacent to the source node.
    next: ID,
}

/// An iterator over edges adjacent to some node.
pub struct NeighIter<'a, ID: 'a> {
    edge: ID,
    edges: &'a [EdgeData<ID>],
}

impl<'a, ID> Iterator for NeighIter<'a, ID>
where
    ID: PrimInt + Unsigned,
{
    type Item = (Edge<ID>, Node<ID>);

    fn next(&mut self) -> Option<Self::Item> {
        if self.edge != ID::max_value() {
            let edge = self.edge;
            self.edge = self.edges[edge.to_usize().unwrap()].next;
            Some((Edge(edge), Node(self.edges[edge.to_usize().unwrap()].snk)))
        } else {
            None
        }
    }
}

/// An iterator over all nodes of a linked list graph.
pub struct NodeIter<ID>(Range<ID>);

impl<ID> Iterator for NodeIter<ID>
where
    ID: PrimInt + Unsigned,
{
    type Item = Node<ID>;

    fn next(&mut self) -> Option<Self::Item> {
        self.0.next().map(Node)
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.0.size_hint()
    }
}

/// An iterator over all edges of a linked list graph.
///
/// This iterator only returns the forward edges.
pub struct EdgeIter<ID>(RangeStep<ID>);

impl<ID> Iterator for EdgeIter<ID>
where
    ID: PrimInt + Unsigned,
{
    type Item = Edge<ID>;

    fn next(&mut self) -> Option<Self::Item> {
        self.0.next().map(Edge)
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.0.size_hint()
    }
}

impl<'a, ID> Graph<'a> for LinkedListGraph<ID>
where
    ID: 'a + PrimInt + Unsigned,
{
    type Node = Node<ID>;
    type Edge = Edge<ID>;
    type NodeIter = NodeIter<ID>;
    type EdgeIter = EdgeIter<ID>;
    type NeighIter = NeighIter<'a, ID>;

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

    fn num_edges(&self) -> usize {
        self.edges.len() / 2
    }

    fn enodes(&self, e: Self::Edge) -> (Self::Node, Self::Node) {
        let eid = e.0.to_usize().unwrap();
        (Node(self.edges[eid | 1].snk), Node(self.edges[eid & !1].snk))
    }

    fn nodes(&'a self) -> Self::NodeIter {
        NodeIter(range(ID::zero(), ID::from(self.num_nodes()).unwrap()))
    }

    fn edges(&self) -> Self::EdgeIter {
        EdgeIter(range_step(
            ID::zero(),
            ID::from(self.edges.len()).unwrap(),
            ID::from(2).unwrap(),
        ))
    }

    fn neighs(&'a self, u: Self::Node) -> Self::NeighIter {
        NeighIter {
            edge: self.nodes[u.index()].first,
            edges: &self.edges,
        }
    }
}

/// An iterator over all edges leaving a certain node.
pub struct OutEdgeIter<'a, ID: 'a>(NeighIter<'a, ID>);

impl<'a, ID> Iterator for OutEdgeIter<'a, ID>
where
    ID: 'a + PrimInt + Unsigned,
{
    type Item = (Edge<ID>, Node<ID>);
    fn next(&mut self) -> Option<Self::Item> {
        while let Some((e, v)) = self.0.next() {
            if (e.0 & ID::one()).is_zero() {
                return Some((e, v));
            }
        }
        None
    }
}

/// An iterator over all edges entering a certain node.
pub struct InEdgeIter<'a, ID: 'a>(NeighIter<'a, ID>);

impl<'a, ID> Iterator for InEdgeIter<'a, ID>
where
    ID: 'a + PrimInt + Unsigned,
{
    type Item = (Edge<ID>, Node<ID>);
    fn next(&mut self) -> Option<Self::Item> {
        while let Some((e, v)) = self.0.next() {
            if !(e.0 & ID::one()).is_zero() {
                return Some((e, v));
            }
        }
        None
    }
}

impl<'a, ID> Digraph<'a> for LinkedListGraph<ID>
where
    ID: 'a + PrimInt + Unsigned,
{
    type OutEdgeIter = OutEdgeIter<'a, ID>;

    type InEdgeIter = InEdgeIter<'a, ID>;

    fn src(&self, e: Self::Edge) -> Self::Node {
        Node(self.edges[e.0.to_usize().unwrap() | 1].snk)
    }

    fn snk(&self, e: Self::Edge) -> Self::Node {
        Node(self.edges[e.0.to_usize().unwrap() & !1].snk)
    }

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

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

impl<'a, ID> Network<'a> for LinkedListGraph<ID>
where
    ID: 'a + PrimInt + Unsigned,
{
    fn is_reverse(&self, e: Self::Edge, f: Self::Edge) -> bool {
        e.0 ^ f.0 == ID::one()
    }

    fn reverse(&self, e: Self::Edge) -> Self::Edge {
        Edge(e.0 ^ ID::one())
    }

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

impl<'a, ID> IndexGraph<'a> for LinkedListGraph<ID>
where
    ID: 'a + PrimInt + Unsigned,
{
    fn node_id(&self, u: Self::Node) -> usize {
        u.index()
    }

    fn id2node(&self, id: usize) -> Self::Node {
        assert!(id < self.nodes.len(), "Invalid node id");
        Node(ID::from(id).unwrap())
    }

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

    fn id2edge(&self, id: usize) -> Self::Edge {
        assert!(id << 1 < self.edges.len(), "Invalid edge id");
        Edge(ID::from(id << 1).unwrap())
    }
}

impl<'a, ID> IndexNetwork<'a> for LinkedListGraph<ID>
where
    ID: 'a + PrimInt + Unsigned,
{
    fn id2biedge(&self, id: usize) -> Self::Edge {
        assert!(id < self.edges.len(), "Invalid biedge id");
        Edge(ID::from(id).unwrap())
    }

    fn biedge_id(&self, a: Self::Edge) -> usize {
        a.0.to_usize().unwrap()
    }
}

impl<ID> Builder for LinkedListGraph<ID>
where
    ID: PrimInt + Unsigned,
{
    type Graph = Self;
    type Node = Node<ID>;
    type Edge = Edge<ID>;

    fn with_capacities(nnodes: usize, nedges: usize) -> Self {
        LinkedListGraph {
            nodes: Vec::with_capacity(nnodes),
            edges: Vec::with_capacity(nedges),
        }
    }

    fn reserve(&mut self, nnodes: usize, nedges: usize) {
        self.nodes.reserve(nnodes);
        self.edges.reserve(nedges);
    }

    fn add_node(&mut self) -> Self::Node {
        assert!(
            self.nodes.len() + 1 < ID::max_value().to_usize().unwrap(),
            "Node capacity exceeded"
        );
        let id = self.nodes.len();
        self.nodes.push(NodeData { first: ID::max_value() });
        Node(ID::from(id).unwrap())
    }

    fn add_edge(&mut self, u: Self::Node, v: Self::Node) -> Self::Edge {
        assert!(
            self.edges.len() + 2 < ID::max_value().to_usize().unwrap(),
            "Edge capacity exceeded"
        );
        let eid = ID::from(self.edges.len()).unwrap();
        let uid = u.0.to_usize().unwrap();
        let vid = v.0.to_usize().unwrap();
        self.edges.push(EdgeData {
            snk: v.0,
            next: self.nodes[uid].first,
        });
        self.edges.push(EdgeData {
            snk: u.0,
            next: self.nodes[vid].first,
        });
        self.nodes[uid].first = eid;
        self.nodes[vid].first = eid + ID::one();
        Edge(eid)
    }

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

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

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

impl<ID> Buildable for LinkedListGraph<ID>
where
    ID: PrimInt + Unsigned,
{
    type Builder = Self;
}

impl<ID> LinkedListGraph<ID>
where
    ID: PrimInt + Unsigned,
{
    pub fn new() -> LinkedListGraph<ID> {
        LinkedListGraph {
            nodes: vec![],
            edges: vec![],
        }
    }
}

impl<ID> Default for LinkedListGraph<ID>
where
    ID: PrimInt + Unsigned,
{
    fn default() -> Self {
        LinkedListGraph::new()
    }
}

#[cfg(test)]
mod tests {
    use classes::*;
    use std::cmp::{max, min};
    use {Digraph, Graph, IndexGraph, LinkedListGraph, Network};
    use {NodeVec, NumberedEdge, NumberedNode};

    #[test]
    fn test_nodevec() {
        let v = vec![1, 2, 3];
        let v: NodeVec<_> = v.into();
        let g = cycle::<LinkedListGraph>(5);
        let u = g.id2node(0);
        println!("{} {}", v[u], v.len());
    }

    #[test]
    fn test_graph() {
        const N: usize = 7;
        let g = cycle::<LinkedListGraph>(N);

        assert_eq!(g.num_nodes(), N);
        assert_eq!(g.num_edges(), N);

        let mut balances = idxnodevec![&g; 0];

        for u in g.nodes() {
            balances[u] = u.index();
        }

        for u in g.nodes() {
            assert_eq!(balances[u], u.index());
        }

        for u in g.nodes() {
            let mut neighs: Vec<_> = g.neighs(u).collect();

            for &(e, v) in &neighs {
                assert!((g.enodes(e) == (u, v)) || (g.enodes(e) == (v, u)));
            }

            neighs.sort_by_key(|&(_, u)| u.index());

            let x = (u.index() + N - 1) % N;
            let y = (u.index() + 1) % N;
            assert_eq!(
                neighs.iter().map(|&(_, v)| v).collect::<Vec<_>>(),
                vec![g.id2node(min(x, y)), g.id2node(max(x, y))]
            );
        }
    }

    #[test]
    fn test_edge_vec() {
        let g = cycle::<LinkedListGraph>(7);

        let mut x = idxedgevec![&g; 0];
        for (i, e) in g.edges().enumerate() {
            x[e] = i;
        }

        for u in g.nodes() {
            for (e, _) in g.neighs(u) {
                assert_eq!(x[e], e.index());
            }
        }
    }

    #[test]
    fn test_digraph() {
        for g in [cycle::<LinkedListGraph>(7), peterson(), hypercube(5)].into_iter() {
            for u in g.nodes() {
                for (e, v) in g.outedges(u) {
                    assert_eq!(u, g.src(e));
                    assert_eq!(v, g.snk(e));
                }
                for (e, v) in g.inedges(u) {
                    assert_eq!(v, g.src(e));
                    assert_eq!(u, g.snk(e));
                }
            }
        }
    }

    #[test]
    fn test_network() {
        for g in [cycle::<LinkedListGraph>(7), peterson(), hypercube(5)].into_iter() {
            for u in g.nodes() {
                for (e, _) in g.outedges(u) {
                    assert!(g.is_forward(e));
                }
                for (e, _) in g.inedges(u) {
                    assert!(g.is_backward(e));
                }
                for (e, _) in g.neighs(u) {
                    assert_eq!(g.is_forward(e), u == g.src(e));
                }
            }

            for e in g.edges() {
                assert!(g.is_forward(e));
                assert_eq!(e, e);
                assert_eq!(e, g.reverse(e));
                assert!(g.is_reverse(e, g.reverse(e)));
                assert!(g.is_reverse(g.reverse(e), e));
                assert!(!g.is_reverse(e, e));
                assert!(g.is_forward(g.forward(e)));
                assert!(g.is_backward(g.backward(e)));
            }
        }
    }

    #[cfg(feature = "serialize")]
    mod serialize {
        extern crate serde_json;
        use super::*;

        #[test]
        fn test_serde() {
            let g = peterson::<LinkedListGraph>();

            let serialized = serde_json::to_string(&g).unwrap();

            println!("serialized = {}", serialized);

            let h: LinkedListGraph = serde_json::from_str(&serialized).unwrap();

            assert_eq!(g.num_nodes(), h.num_nodes());
            assert_eq!(g.num_edges(), h.num_edges());
            for e in g.edges() {
                let f = h.id2edge(g.edge_id(e));
                assert_eq!(g.node_id(g.src(e)), h.node_id(h.src(f)));
                assert_eq!(g.node_id(g.snk(e)), h.node_id(h.snk(f)));
            }
        }

        #[test]
        fn test_serialize() {
            use Builder;
            let mut g = LinkedListGraph::<u32>::new();

            let nodes = g.add_nodes(5);
            g.add_edge(nodes[0], nodes[1]);
            g.add_edge(nodes[0], nodes[2]);
            g.add_edge(nodes[1], nodes[4]);
            g.add_edge(nodes[2], nodes[3]);

            let serialized = serde_json::to_string(&g).unwrap();
            let g2: LinkedListGraph<u32> = serde_json::from_str(&serialized).unwrap();

            assert_eq!(g.num_nodes(), g2.num_nodes());
            let mut edges = g2
                .edges()
                .map(|e| {
                    let (u, v) = g2.enodes(e);
                    let (u, v) = (IndexGraph::node_id(&g2, u), IndexGraph::node_id(&g2, v));
                    (min(u, v), max(u, v))
                })
                .collect::<Vec<_>>();
            edges.sort();
            assert_eq!(edges, vec![(0, 1), (0, 2), (1, 4), (2, 3)]);
        }
    }
}