43 #ifndef MAP_GRAPH_HPP_
44 #define MAP_GRAPH_HPP_
46 #include "Vector/map_vector.hpp"
47 #include <unordered_map>
49 #include "metis_util.hpp"
62 typedef boost::fusion::vector<>
type;
70 static inline bool noPointers()
76 template<
typename V,
typename E,
80 template <
typename>
class layout_v_base,
81 template <
typename>
class layout_e_base,
95 typedef boost::fusion::vector<size_t, size_t> type;
99 static const unsigned int vid = 0;
100 static const unsigned int eid = 1;
101 static const unsigned int max_prop = 2;
105 inline void setvid(
size_t vid_)
107 boost::fusion::at_c<0>(data) = vid_;
110 inline void seteid(
size_t eid_)
112 boost::fusion::at_c<1>(data) = eid_;
115 static inline bool noPointers()
168 template<
typename Graph>
200 if (ek.
pos_e + 1 >=
g.getNChilds(ek.
pos))
207 while (ek.
pos <
g.getNVertex() &&
g.getNChilds(ek.
pos) == 0)
231 if (ek.
pos <
g.getNVertex())
301 template<
typename V,
typename E =
no_edge,
339 template<
typename CheckPolicy = NoCheck>
inline size_t addEdge_(
size_t v1,
size_t v2)
342 if (CheckPolicy::valid(v1,
v.
size()) ==
false)
344 if (CheckPolicy::valid(v2,
v.
size()) ==
false)
348 size_t id_x_end =
v_l.template get<0>(v1);
355 std::cout <<
"Warning graph: creating an edge between vertex that does not exist" << std::endl;
360 for (
size_t s = 0; s < id_x_end; s++)
362 if (
e_l.template get<e_map::vid>(v1 *
v_slot + s) == v2)
364 std::cerr <<
"Error graph: the edge already exist" << std::endl;
382 for (
size_t i = 0; i <
v.
size(); i++)
386 g_new.
v.set(i,
v, 2 * i);
406 e_l.template get<e_map::vid>(v1 *
v_slot + id_x_end) = v2;
413 ++
v_l.template get<0>(v1);
471 dup.
v.swap(
v.duplicate());
472 dup.
v_l.swap(
v_l.duplicate());
473 dup.
e.swap(
e.duplicate());
474 dup.
e_l.swap(
e_l.duplicate());
516 v_l.resize(n_vertex);
574 template<
unsigned int i>
auto vertex_p(
size_t id) -> decltype(
v.template get<i>(
id) )
576 return v.template get<i>(id);
590 return v.template get<i>(id);
600 auto vertex(
size_t id) -> decltype(
v.get(
id) )
614 return v.get(
id.
get(0));
626 return v.get(
id.
get());
636 auto vertex(
size_t id)
const ->
const decltype(
v.get(
id) )
652 return v.get(
id.
get(0));
664 return v.get(
id.
get());
691 return e.template get<i>(id);
702 template<
unsigned int i>
auto edge_p(
size_t id) -> decltype (
e.template get<i>(
id) )
704 return e.template get<i>(id);
717 return e.get(
e_l.template get<e_map::eid>(ek.pos *
v_slot + ek.pos_e));
727 auto edge(
size_t id)
const ->
const decltype (
e.get(
id) )
741 return e.get(
id.
get(0));
756 return v_l.template get<0>(c);
770 return v_l.template get<0>(c.get());
784 return e.get(
e_l.template get<e_map::eid>(
v *
v_slot + v_e));
799 if (i >=
v_l.template get<0>(v))
801 std::cerr <<
"Error " << __FILE__ <<
" line: " << __LINE__ <<
" vertex " << v <<
" does not have edge " << i << std::endl;
804 if (i >=
v_l.template get<0>(v))
806 std::cerr <<
"Error " << __FILE__ <<
" " << __LINE__ <<
" vertex " << v <<
" does not have edge "<< i << std::endl;
810 return e_l.template get<e_map::vid>(v *
v_slot + i);
824 if (i >=
v_l.template get<0>(v.get()))
826 std::cerr <<
"Error " << __FILE__ <<
" line: " << __LINE__ <<
" vertex " << v.get() <<
" does not have edge " << i << std::endl;
829 if (
e.
size() <=
e_l.template get<e_map::eid>(v.get() *
v_slot + i))
831 std::cerr <<
"Error " << __FILE__ <<
" " << __LINE__ <<
" vertex " << v.get() <<
" does not have edge "<< i << std::endl;
836 return e_l.template get<e_map::vid>(v.get() *
v_slot + i);
884 template<
typename CheckPolicy = NoCheck>
inline auto addEdge(
size_t v1,
size_t v2,
const E &
ed) -> decltype(
e.get(0))
886 long int id_x_end = addEdge_<CheckPolicy>(v1, v2);
889 if (id_x_end == NO_EDGE)
895 return e.get(id_x_end);
908 template<
typename CheckPolicy = NoCheck>
inline auto addEdge(
size_t v1,
size_t v2) -> decltype(
e.get(0))
911 long int id_x_end = addEdge_<CheckPolicy>(v1, v2);
913 if (id_x_end == NO_EDGE)
917 return e.get(id_x_end);
936 template<
typename CheckPolicy = NoCheck,
int sg
id,
int dg
id>
inline auto addEdge(
size_t v1,
size_t v2,
size_t srcgid,
size_t dstgid) -> decltype(
e.get(0))
939 long int id_x_end = addEdge_<CheckPolicy>(v1, v2);
941 if (id_x_end == NO_EDGE)
945 e.get(id_x_end).template get<sgid>() = srcgid;
946 e.get(id_x_end).template get<dgid>() = dstgid;
949 return e.get(id_x_end);
970 size_t v_slot_tmp = g.
v_slot;
992 size_t v_slot_tmp = g.v_slot;
1007 return v.getIterator();
1070 template<
typename V,
typename E>
auto getVertexIterator() const -> decltype(v.getIterator())
Get the vertex iterator.
Graph_CSR< V, E, Memory > & operator=(const Graph_CSR< V, E, Memory > &g)
Graph_CSR< V, E, Memory, layout_v, layout_e, layout_v_base, layout_e_base, grow_p > duplicate() const
It duplicate the graph.
static const unsigned int max_prop
no properties
void begin()
Reset the counter.
auto addEdge(size_t v1, size_t v2) -> decltype(e.get(0))
add edge on the graph
Transform the boost::fusion::vector into memory specification (memory_traits)
auto vertex(openfpm::vector_key_iterator id) -> decltype(v.get(0))
Fuction to access the vertex.
size_t getNEdge() const
Return the number of edges.
auto edge_p(size_t id) -> decltype(e.template get< i >(id))
Access the edge.
void clear()
operator to clear the whole graph
void addVertex(const V &vrt)
add vertex
edge_iterator< Graph_CSR< V, E, Memory > > getEdgeIterator() const
Get the vertex iterator.
Grow policy define how the vector should grow every time we exceed the size.
grid_key_dx is the key to access any element in the grid
size_t getChild(size_t v, size_t i) const
Get the child vertex id.
Graph_CSR< V, E, Memory > & operator=(Graph_CSR< V, E, Memory > &&g)
openfpm::vector< V, Memory, layout_v, layout_v_base, grow_p, openfpm::vect_isel< V >::value > v
Structure that store the vertex properties.
auto vertex(grid_key_dx< 1 > id) const -> const decltype(v.get(id.get(0)))
Fuction to access the vertex.
openfpm::vector< size_t, Memory, typename layout_v_base< size_t >::type, layout_v_base, grow_p, openfpm::vect_isel< size_t >::value > v_l
Structure that store the number of adjacent vertex in e_l for each vertex.
auto vertex(openfpm::vector_key_iterator id) const -> const decltype(v.get(0))
operator to access the vertex
bool isNext()
Check if there is the next element.
openfpm::vector< E, Memory, layout_e, layout_e_base, grow_p, openfpm::vect_isel< E >::value >::container E_container
Object container for the edge, for example can be encap<...> (map_grid or openfpm::vector) ...
edge_iterator & operator++()
Get the next element.
openfpm::vector< E, Memory, layout_e, layout_e_base, grow_p, openfpm::vect_isel< E >::value > e
Structure that store the edge properties.
size_t v_slot
number of slot per vertex
edge_iterator(const Graph &g)
Constructor.
openfpm::vector< e_map, Memory, typename layout_e_base< e_map >::type, layout_e_base, grow_p, openfpm::vect_isel< e_map >::value > e_l
Structure that store for each vertex the adjacent the vertex id and edge id (for property into e) ...
size_t pos
Actual source node.
size_t source()
Return the source node.
auto vertex_p(size_t id) -> decltype(v.template get< i >(id))
operator to access the vertex
size_t pos_e
Actual target node.
This class allocate, and destroy CPU memory.
auto edge_p(grid_key_dx< 1 > id) -> decltype(e.template get< i >(id))
Access the edge.
auto getChildEdge(size_t v, size_t v_e) -> decltype(e.get(0))
Get the vertex edge.
size_t target()
Return the target node.
bool operator==(const Graph_CSR< V, E, Memory, layout_v, layout_e, layout_v_base, layout_e_base, grow_p > &g) const
Check if two graph exactly match.
auto edge(size_t id) const -> const decltype(e.get(id))
operator to access the edge
size_t getChild(typename openfpm::vector< V, Memory, layout_v, layout_v_base, grow_p >::iterator_key &v, size_t i)
Get the child edge.
void swap(Graph_CSR< V, E > &&g)
swap the memory of g with this graph
auto addEdge(size_t v1, size_t v2, size_t srcgid, size_t dstgid) -> decltype(e.get(0))
add edge on the graph and fill source and destination informations
size_t & target_t()
Return the target of this edge.
It analyze the type given and it select correctly the implementation for vector.
Structure that store a graph in CSR format or basically in compressed adjacency matrix format...
void addVertex()
add an empty vertex
Graph_CSR(size_t n_vertex, size_t n_slot)
Constructor.
auto addEdge(size_t v1, size_t v2, const E &ed) -> decltype(e.get(0))
add edge on the graph
Graph_CSR(size_t n_vertex)
Constructor.
auto vertex(size_t id) const -> const decltype(v.get(id))
Function to access the vertex.
auto vertex(size_t id) -> decltype(v.get(id))
Function to access the vertex.
size_t getNVertex() const
Return the number of the vertex.
void swap(Graph_CSR< V, E > &g)
swap the memory of g with this graph
boost::fusion::vector type
type in case of no edge
Structure used inside GraphCSR an edge.
auto vertex(grid_key_dx< 1 > id) -> decltype(v.get(id.get(0)))
Function to access the vertex.
size_t getNChilds(size_t c) const
Return the number of childs of a vertex.
openfpm::vector< E, Memory, layout_e, layout_e_base, grow_p, openfpm::vect_isel< E >::value > e_invalid
invalid edge element, when a function try to create an in valid edge this object is returned ...
openfpm::vector< V, Memory, layout_v, layout_v_base, grow_p, openfpm::vect_isel< V >::value >::container V_container
Object container for the vertex, for example can be encap<...> (map_grid or openfpm::vector) ...
This class is a container for the memory interface like HeapMemory CudaMemory.
Simplified implementation of Graph_CSR.
size_t getNChilds(typename openfpm::vector< V, Memory, layout_v, layout_v_base, grow_p, openfpm::vect_isel< V >::value >::iterator_key &c)
Return the number of childs of a vertex.
Graph_CSR(Graph_CSR< V, E, Memory > &&g)
Copy constructor.
size_t & source()
Get the source id of this edge.
Implementation of 1-D std::vector like structure.
size_t addEdge_(size_t v1, size_t v2)
add edge on the graph
auto edge(edge_key ek) const -> const decltype(e.get(0))
operator to access the edge
auto edge(grid_key_dx< 1 > id) const -> const decltype(e.get(id.get(0)))
Access the edge.
auto vertex_p(grid_key_dx< 1 > id) -> decltype(v.template get< i >(id))
Access the vertex.