map_graph.hpp

/*
 * map_graph.hpp
 *
 *  Created on: Nov 21, 2014
 *      Author: Pietro Incardona
 *
 *
 *  Graph structure that store a CSR graph format
 *
 *  This Graph format is suppose to have a list of vertex that store an index x that indicate where
 *  in the adjacency list we have the list of all the neighborhood vertex, plus an adjacency list
 *  that store all the neighborhood for each vertex:
 *
 *  In reality inside Graph_CSR
 *
 *  VertexList store the Vertex index that indicate the end of the neighborhood list,
 *  the start is indicated by i * v_slot (id of the vertex, v_slot maximum number of
 *  neighborhood for a vertex)
 *
 *  EdgeList store for each vertex at position i * v_slot (id of the vertex, v_slot maximum
 *  number of neighborhood for a vertex) the list of all the neighborhood of the vertex i
 *
 *  Example
 *
 *  Suppose an undirected graph of 4 vertex
 *
 *  1 -> 2 3 4
 *  2 -> 1
 *  3 -> 4 1
 *  4 -> 1 3
 *
 *  suppose that v_slot is 4 ( each vertex has less tha 4 neighborhood  )
 *
 *  we will have
 *
 *  Vertex list 3 5 10 14
 *  Edge list   2 3 4 0 1 0 0 0 4 1 0 0 1 3 0 0
 *
 *  Vertex properties and edge properties are stored in a separate structure
 *
 */

#ifndef MAP_GRAPH_HPP_
#define MAP_GRAPH_HPP_

#include "Vector/map_vector.hpp"
#ifdef METIS_GP
#include "metis_util.hpp"
#endif

#define NO_EDGE -1

class no_edge
{
public:
    typedef boost::fusion::vector<> type;
    typedef typename memory_traits_inte<type>::type memory_int;
    typedef typename memory_traits_lin<type>::type memory_lin;

    type data;

    static const unsigned int max_prop = 0;
};

template<typename V, typename E, template<typename, typename, typename, unsigned int> class VertexList, template<typename, typename, typename, unsigned int> class EdgeList, typename Memory,
        typename grow_p>
class Graph_CSR;

class e_map
{
public:
    typedef boost::fusion::vector<size_t, size_t> type;
    typedef typename memory_traits_inte<type>::type memory_int;
    typedef typename memory_traits_lin<type>::type memory_lin;

    type data;

    static const unsigned int vid = 0;
    static const unsigned int eid = 1;
    static const unsigned int max_prop = 2;

    // Setter method

    inline void setvid(size_t vid_)
    {
        boost::fusion::at_c<0>(data) = vid_;
    }
    ;
    inline void seteid(size_t eid_)
    {
        boost::fusion::at_c<1>(data) = eid_;
    }
    ;
};

class edge_key
{
public:

    // Actual source node
    size_t pos;

    //Actual target node
    size_t pos_e;

    void begin()
    {
        pos = 0;
        pos_e = 0;
    }

    size_t & source()
    {
        return pos;
    }

    size_t & target_t()
    {
        return pos_e;
    }
};

template<typename Graph>
class edge_iterator
{
    const Graph & g;

    // Actual edge key
    edge_key ek;

public:

    edge_iterator(const Graph & g) :
            g(g)
    {
        ek.begin();
    }

    edge_iterator & operator++()
    {
        // Check if reach the end of the edge list
        if (ek.pos_e + 1 >= g.getNChilds(ek.pos))
        {
            // increment the node position and reset
            ek.pos++;
            ek.pos_e = 0;

            // skip every vertex without edges
            while (ek.pos < g.getNVertex() && g.getNChilds(ek.pos) == 0)
            {
                ek.pos++;
            }
        }
        else
        {
            // increment the edge position
            ek.pos_e++;
        }

        return *this;
    }

    bool isNext()
    {
        if (ek.pos < g.getNVertex())
        {

            return true;
        }

        return false;
    }

    edge_key get()
    {
        return ek;
    }

    size_t source()
    {
        return ek.pos;
    }

    size_t target()
    {
        return g.getChild(ek.pos, ek.pos_e);
    }
};

template<typename V, typename E = no_edge, template<typename, typename, typename, unsigned int> class VertexList = openfpm::vector,
        template<typename, typename, typename, unsigned int> class EdgeList = openfpm::vector, typename Memory = HeapMemory, typename grow_p = openfpm::grow_policy_double>
class Graph_CSR
{
    size_t v_slot;

    VertexList<V, Memory, grow_p, openfpm::vect_isel<V>::value> v;

    VertexList<size_t, Memory, grow_p, openfpm::vect_isel<size_t>::value> v_l;

    EdgeList<E, Memory, grow_p, openfpm::vect_isel<E>::value> e;

    EdgeList<e_map, Memory, grow_p, openfpm::vect_isel<e_map>::value> e_l;

    EdgeList<E, Memory, grow_p, openfpm::vect_isel<E>::value> e_invalid;

    template<typename CheckPolicy = NoCheck> inline size_t addEdge_(size_t v1, size_t v2)
    {
        // If v1 and v2 does not satisfy some criteria return
        if (CheckPolicy::valid(v1, v.size()) == false)
            return NO_EDGE;
        if (CheckPolicy::valid(v2, v.size()) == false)
            return NO_EDGE;

        // get the number of adjacent vertex
        size_t id_x_end = v_l.template get<0>(v1);

#ifdef DEBUG
        // Check that v1 and v2 exist

        if (v1 >= v.size() || v2 >= v.size())
        {
            std::cerr << "Error graph: trying to create an edge between vertex that does not exist" << "\n";
        }

        // Check that the edge does not already exist

        for (size_t s = 0; s < id_x_end; s++)
        {
            if (e_l.template get<e_map::vid>(v1 * v_slot + s) == v2)
            {
                std::cerr << "Error graph: the edge already exist" << "\n";
            }
        }
#endif

        // Check if there is space for another edge

        if (id_x_end >= v_slot)
        {
            // Unfortunately there is not space we need to reallocate memory
            // Reallocate with double slot

            // Create an new Graph

            Graph_CSR<V, E, VertexList, EdgeList> g_new(2 * v_slot, v.size());

            // Copy the graph

            for (size_t i = 0; i < v.size(); i++)
            {
                // copy the property from the old graph

                g_new.v.set(i, v, 2 * i);
            }

            // swap the new graph with the old one

            swap(g_new);
        }

        // Here we are sure than v and e has enough slots to store a new edge
        // Check that e_l has enough space to store new edge
        // should be always e.size == e_l.size

        if (id_x_end >= e_l.size())
        {
            // Resize the basic structure

            e_l.resize(v.size() * v_slot);
        }

        // add in e_l the adjacent vertex for v1 and fill the edge id
        e_l.template get<e_map::vid>(v1 * v_slot + id_x_end) = v2;
        e_l.template get<e_map::eid>(v1 * v_slot + id_x_end) = e.size();

        // add an empty edge
        e.resize(e.size() + 1);

        // Increment the ending point
        ++v_l.template get<0>(v1);

        // return the created edge
        return e.size() - 1;
    }

public:

    typedef V V_type;

    typedef E E_type;

    typedef typename VertexList<V, Memory, grow_p, openfpm::vect_isel<V>::value>::container V_container;

    typedef typename EdgeList<E, Memory, grow_p, openfpm::vect_isel<E>::value>::container E_container;

    Graph_CSR<V, E, VertexList, EdgeList, Memory, grow_p> duplicate()
    {
        Graph_CSR<V, E, VertexList, EdgeList, Memory, grow_p> dup;

        dup.v_slot = v_slot;


        dup.v.swap(v.duplicate());
        dup.v_l.swap(v_l.duplicate());
        dup.e.swap(e.duplicate());
        dup.e_l.swap(e_l.duplicate());
        dup.e_invalid.swap(e_invalid.duplicate());

        return dup;
    }

    Graph_CSR() :
            Graph_CSR(0, 16)
    {
    }

    Graph_CSR(size_t n_vertex) :
            Graph_CSR(n_vertex, 16)
    {
    }

    Graph_CSR(size_t n_vertex, size_t n_slot)
    :v_slot(n_slot)
    {
        v.resize(n_vertex);
        v_l.resize(n_vertex);
        v_l.fill(0);
        e_invalid.resize(1);
    }

    Graph_CSR(Graph_CSR<V, E, VertexList, EdgeList, Memory> && g)
    {
        size_t vs_tmp = v_slot;
        v_slot = g.v_slot;
        g.v_slot = vs_tmp;
        swap(g);
    }

    template<unsigned int i> auto vertex_p(size_t id) -> decltype( v.template get<i>(id) )
    {
        return v.template get<i>(id);
    }

    template<unsigned int i> auto vertex_p(grid_key_dx<1> id) -> decltype( v.template get<i>(id) )
    {
        return v.template get<i>(id);
    }

    auto vertex(size_t id) -> decltype( v.get(id) )
    {
        return v.get(id);
    }

    auto vertex(grid_key_dx<1> id) -> decltype( v.get(id.get(0)) )
    {
        return v.get(id.get(0));
    }

    auto vertex(openfpm::vector_key_iterator id) -> decltype( v.get(0) )
    {
        return v.get(id.get());
    }

    auto vertex(size_t id) const -> const decltype( v.get(id) )
    {
        return v.get(id);
    }

    auto vertex(grid_key_dx<1> id) const -> const decltype( v.get(id.get(0)) )
    {
        return v.get(id.get(0));
    }

    auto vertex(openfpm::vector_key_iterator id) const -> const decltype( v.get(0) )
    {
        return v.get(id.get());
    }

    template<unsigned int i> auto edge_p(grid_key_dx<1> id) -> decltype ( e.template get<i>(id) )
    {
        return e.template get<i>(id);
    }

    template<unsigned int i> auto edge_p(size_t id) -> decltype ( e.template get<i>(id) )
    {
        return e.template get<i>(id);
    }

    auto edge(grid_key_dx<1> id) -> decltype ( e.get(id.get(0)) )
    {
        return e.get(id.get(0));
    }

    auto edge(edge_key ek) -> decltype ( e.get(0) )
    {
        return e.get(e_l.template get<e_map::eid>(ek.pos * v_slot + ek.pos_e));
    }

    auto edge(size_t id) -> decltype ( e.get(id) )
    {
        return e.get(id);
    }

    auto edge(grid_key_dx<1> id) const -> const decltype ( e.get(id.get(0)) )
    {
        return e.get(id.get(0));
    }

    auto edge(edge_key ek) const -> const decltype ( e.get(0) )
    {
        return e.get(e_l.template get<e_map::eid>(ek.pos * v_slot + ek.pos_e));
    }

    auto edge(size_t id) const -> const decltype ( e.get(id) )
    {
        return e.get(id);
    }

    inline size_t getNChilds(size_t c) const
    {
        // Get the number of childs

        return v_l.template get<0>(c);
    }

    inline size_t getNChilds(typename VertexList<V, Memory, grow_p, openfpm::vect_isel<V>::value>::iterator_key & c)
    {
        // Get the number of childs

        return v_l.template get<0>(c.get());
    }

    inline auto getChildEdge(size_t v, size_t v_e) -> decltype(e.get(0))
    {
#ifdef DEBUG
        if (e >= v_l.template get<0>(v*v_slot))
        {
            std::cerr << "Error node " << v << " does not have edge " << v_e << "\n";
        }

        if (e.size() >= e_l.template get<e_map::eid>(v * v_slot + v_e))
        {
            std::cerr << "Error edge " << v << " does not have edge "<< v_e << "\n";
        }
#endif

        // Get the edge id
        return e.get(e_l.template get<e_map::eid>(v * v_slot + v_e));
    }

    inline size_t getChild(size_t v, size_t i) const
    {
#ifdef DEBUG
        if (i >= v_l.template get<0>(v) )
        {
            std::cerr << "Error " << __FILE__ << " line: " << __LINE__ << "    vertex " << v << " does not have edge " << i << "\n";
        }

        if (e.size() <= e_l.template get<e_map::eid>(v * v_slot + i))
        {
            std::cerr << "Error " << __FILE__ << " " << __LINE__ << " edge " << v << " does not have edge "<< i << "\n";
        }
#endif

        // Get the edge id
        return e_l.template get<e_map::vid>(v * v_slot + i);
    }

    inline size_t getChild(typename VertexList<V, Memory, grow_p, openfpm::vect_isel<V>::value>::iterator_key & v, size_t i)
    {
#ifdef DEBUG
        if (i >= v_l.template get<0>(v.get()) )
        {
            std::cerr << "Error " << __FILE__ << " line: " << __LINE__ << "    vertex " << v.get() << " does not have edge " << i << "\n";
        }

        if (e.size() <= e_l.template get<e_map::eid>(v.get() * v_slot + i))
        {
            std::cerr << "Error " << __FILE__ << " " << __LINE__ << " edge " << v.get() << " does not have edge "<< i << "\n";
        }
#endif

        // Get the edge id
        return e_l.template get<e_map::vid>(v.get() * v_slot + i);
    }

    inline void addVertex(const V & vrt)
    {
        v.add(vrt);

        // Set the number of adjacent vertex for this vertex to 0

        v_l.add(0ul);

        // Add a slot for the vertex adjacency list

        e_l.resize(e_l.size() + v_slot);
    }

    inline void addVertex()
    {
        v.add();

        // Set the number of adjacent vertex for this vertex to 0

        v_l.add(0ul);

        // Add a slot for the vertex adjacency list

        e_l.resize(e_l.size() + v_slot);
    }

    template<typename CheckPolicy = NoCheck> inline auto addEdge(size_t v1, size_t v2, const E & ed) -> decltype(e.get(0))
    {
        long int id_x_end = addEdge_<CheckPolicy>(v1, v2);

        // If there is not edge return an invalid edge, is a kind of stub object
        if (id_x_end == NO_EDGE)
            return e_invalid.get(0);

        // add in e_l the edge properties
        e.set(id_x_end, ed);

        return e.get(id_x_end);
    }

    template<typename CheckPolicy = NoCheck> inline auto addEdge(size_t v1, size_t v2) -> decltype(e.get(0))
    {
        long int id_x_end = addEdge_<CheckPolicy>(v1, v2);
        // If there is not edge return an invalid edge, is a kind of stub object
        if (id_x_end == NO_EDGE)
            return e_invalid.get(0);

        return e.get(id_x_end);
    }

    inline void swap(Graph_CSR<V, E, VertexList, EdgeList> & g)
    {
        // switch the memory

        g.v.swap(v);
        g.e.swap(e);
        g.v_l.swap(v_l);
        g.e_l.swap(e_l);
        g.e_invalid.swap(e_invalid);
    }

    inline auto getVertexIterator() const -> decltype(v.getIterator())
    {
        return v.getIterator();
    }

    inline edge_iterator<Graph_CSR<V, E, VertexList, EdgeList, Memory>> getEdgeIterator() const
    {
        return edge_iterator<Graph_CSR<V, E, VertexList, EdgeList, Memory>>(*this);
    }

    inline size_t getNVertex() const
    {
        return v.size();
    }

    inline size_t getNEdge() const
    {
        return e.size();
    }
};

template<typename V, typename E>
class Graph_CSR_s: public Graph_CSR<V, E>
{

};

#endif /* MAP_GRAPH_HPP_ */