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"
#include <unordered_map>
#ifdef METIS_GP
#include "metis_util.hpp"
#endif
 
#define NO_EDGE -1
 
class no_edge
{
public:
 
    typedef boost::fusion::vector<> type;
 
    type data;
 
    static const unsigned int max_prop = 0;
 
    static inline bool noPointers()
    {
        return true;
    }
};
 
template<typename V, typename E,
         typename Memory,
         template <typename> class layout_v_base,
         template <typename> class layout_e_base,
         typename grow_p>
class Graph_CSR;
 
class e_map
{
public:
    typedef boost::fusion::vector<size_t, size_t> type;
 
    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_;
    }
 
    static inline bool noPointers()
    {
        return true;
    }
};
 
class edge_key
{
public:
 
    size_t pos;
 
    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,
          typename Memory = HeapMemory,
          template<typename> class layout_v_base = memory_traits_lin,
          template<typename> class layout_e_base = memory_traits_lin,
          typename grow_p = openfpm::grow_policy_double>
class Graph_CSR
{
    size_t v_slot;
 
    openfpm::vector<V, Memory, layout_v_base,grow_p, openfpm::vect_isel<V>::value> v;
 
    openfpm::vector<size_t, Memory, layout_v_base,grow_p, openfpm::vect_isel<size_t>::value> v_l;
 
    openfpm::vector<E, Memory, layout_e_base, grow_p, openfpm::vect_isel<E>::value> e;
 
    openfpm::vector<e_map, Memory, layout_e_base , grow_p, openfpm::vect_isel<e_map>::value> e_l;
 
    openfpm::vector<E, Memory, layout_e_base, 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 (size_t)NO_EDGE;
        if (CheckPolicy::valid(v2, v.size()) == false)
            return (size_t)NO_EDGE;
 
        // get the number of adjacent vertex
        size_t id_x_end = v_l.template get<0>(v1);
 
#ifdef SE_CLASS1
        // Check that v1 and v2 exist
 
        if (v1 >= v.size() || v2 >= v.size())
        {
            std::cout << "Warning graph: creating an edge between vertex that does not exist" << std::endl;
        }
 
        // 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" << std::endl;
            }
        }
#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> 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 openfpm::vector<V, Memory, layout_v_base, grow_p, openfpm::vect_isel<V>::value>::container V_container;
 
    typedef typename openfpm::vector<E, Memory, layout_e_base, grow_p, openfpm::vect_isel<E>::value>::container E_container;
 
    bool operator==(const Graph_CSR<V, E, Memory,layout_v_base, layout_e_base, grow_p> & g) const
    {
        bool ret = true;
 
        // Check if they match
 
        ret &= (v_slot == g.v_slot);
        ret &= (v == g.v);
        ret &= (v_l == g.v_l);
        ret &= (e == g.e);
        ret &= (e_l == g.e_l);
 
        return ret;
    }
 
 
    Graph_CSR<V, E, Memory,layout_v_base,layout_e_base, grow_p> duplicate() const
    {
        Graph_CSR<V, E, Memory,layout_v_base,layout_e_base, 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, Memory> && g)
    {
        this->operator=(g);
    }
 
    Graph_CSR<V, E, Memory> & operator=(Graph_CSR<V, E, Memory> && g)
    {
        size_t vs_tmp = v_slot;
        v_slot = g.v_slot;
        g.v_slot = vs_tmp;
        swap(g);
 
        return *this;
    }
 
    Graph_CSR<V, E, Memory> & operator=(const Graph_CSR<V, E, Memory> & g)
    {
        swap(g.duplicate());
 
        v_slot = g.v_slot;
 
        return *this;
    }
 
    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());
    }
 
    void clear()
    {
        v.clear();
        e.clear();
        v_l.clear();
        e_l.clear();
        e_invalid.clear();
    }
 
 
    void destroy()
    {
        v.clear();
        v.shrink_to_fit();
        e.clear();
        e.shrink_to_fit();
        v_l.clear();
        v_l.shrink_to_fit();
        e_l.clear();
        e_l.shrink_to_fit();
        e_invalid.clear();
        e_invalid.shrink_to_fit();
    }
 
    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(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);
    }
 
    auto edge(grid_key_dx<1> id) const -> const decltype ( e.get(id.get(0)) )
    {
        return e.get(id.get(0));
    }
 
    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 openfpm::vector<V, Memory, layout_v_base, 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))
    {
        // 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 SE_CLASS1
        if (i >= v_l.template get<0>(v))
        {
            std::cerr << "Error " << __FILE__ << " line: " << __LINE__ << "    vertex " << v << " does not have edge " << i << std::endl;
        }
 
        if (i >= v_l.template get<0>(v))
        {
            std::cerr << "Error " << __FILE__ << " " << __LINE__ << " vertex " << v << " does not have edge "<< i << std::endl;
        }
#endif
        // Get the target vertex id
        return e_l.template get<e_map::vid>(v * v_slot + i);
    }
 
    inline size_t getChild(typename openfpm::vector<V, Memory, layout_v_base, grow_p>::iterator_key & v, size_t i)
    {
#ifdef SE_CLASS1
        if (i >= v_l.template get<0>(v.get()))
        {
            std::cerr << "Error " << __FILE__ << " line: " << __LINE__ << "    vertex " << v.get() << " does not have edge " << i << std::endl;
        }
 
        if (e.size() <= e_l.template get<e_map::eid>(v.get() * v_slot + i))
        {
            std::cerr << "Error " << __FILE__ << " " << __LINE__ << " vertex " << v.get() << " does not have edge "<< i << std::endl;
        }
#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);
    }
 
    template<typename CheckPolicy = NoCheck, int sgid, int dgid> inline auto addEdge(size_t v1, size_t v2, size_t srcgid, size_t dstgid) -> decltype(e.get(0))
    {
        long int id_x_end = addEdge_<CheckPolicy>(v1, v2);
        if (id_x_end == NO_EDGE)
            return e_invalid.get(0);
 
        e.get(id_x_end).template get<sgid>() = srcgid;
        e.get(id_x_end).template get<dgid>() = dstgid;
 
        return e.get(id_x_end);
    }
 
    inline void swap(Graph_CSR<V, E> & g)
    {
        // switch the memory
 
        v.swap(g.v);
        e.swap(g.e);
        v_l.swap(g.v_l);
        e_l.swap(g.e_l);
        e_invalid.swap(g.e_invalid);
 
        size_t v_slot_tmp = g.v_slot;
        g.v_slot = v_slot;
        v_slot = v_slot_tmp;
    }
 
    inline void swap(Graph_CSR<V, E> && g)
    {
        // switch the memory
 
        v.swap(g.v);
        e.swap(g.e);
        v_l.swap(g.v_l);
        e_l.swap(g.e_l);
        e_invalid.swap(g.e_invalid);
 
        size_t v_slot_tmp = g.v_slot;
        g.v_slot = v_slot;
        v_slot = v_slot_tmp;
    }
 
    inline auto getVertexIterator() const -> decltype(v.getIterator())
    {
        return v.getIterator();
    }
 
    inline edge_iterator<Graph_CSR<V, E, Memory>> getEdgeIterator() const
    {
        return edge_iterator<Graph_CSR<V, E, 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_ */