1/*
2 * dist_map_graph.hpp
3 *
4 * Created on: Dec 10, 2015
5 * Author: Antonio Leo
6 *
7 *
8 * The distributed graph, is a graph distributed across processors, each processor store part of the graph
9 *
10 * ## Dictionary
11 *
12 * * local vertex id, is the index of the vertex in the local graph
13 * * vertex id is the "unique" index in the distribution vector (vtxdist)
14 * * global id is the "unique" topological id of the vertex, it never change
15 *
16 *
17 *
18 * Graph structure that store a CSR graph format
19 *
20 * This Graph format is suppose to have a list of vertex that store an index x that indicate where
21 * in the adjacency list we have the list of all the neighborhood vertex, plus an adjacency list
22 * that store all the neighborhood for each vertex:
23 *
24 * In reality inside DistGraph_CSR
25 *
26 * VertexList store the Vertex index that indicate the end of the neighborhood list,
27 * the start is indicated by i * v_slot (id of the vertex, v_slot maximum number of
28 * neighborhood for a vertex)
29 *
30 * EdgeList store for each vertex at position i * v_slot (id of the vertex, v_slot maximum
31 * number of neighborhood for a vertex) the list of all the neighborhood of the vertex i
32 *
33 * Example
34 *
35 * Suppose an undirected graph of 4 vertex
36 *
37 * 1 -> 2 3 4
38 * 2 -> 1
39 * 3 -> 4 1
40 * 4 -> 1 3
41 *
42 * suppose that v_slot is 4 ( each vertex has less tha 4 neighborhood )
43 *
44 * we will have
45 *
46 * Vertex list 3 5 10 14
47 * Edge list 2 3 4 0 1 0 0 0 4 1 0 0 1 3 0 0
48 *
49 * Vertex properties and edge properties are stored in a separate structure
50 *
51 * ## Dictionary
52 *
53 * The distributed
54 *
55 * * local vertex id is the index of the vertex in
56 *
57 */
58
59#ifndef DIST_MAP_GRAPH_HPP_
60#define DIST_MAP_GRAPH_HPP_
61
62#include "Vector/map_vector.hpp"
63#include "Graph/map_graph.hpp"
64#include <unordered_map>
65#include "Packer_Unpacker/Packer.hpp"
66#include "Packer_Unpacker/Unpacker.hpp"
67#include "VCluster/VCluster.hpp"
68
69#define NO_EDGE -1
70#define DIST_GRAPH_ERROR 7001
71
72template<typename V, typename E,
73 typename Memory,
74 typename layout_v,
75 typename layout_e,
76 template<typename> class layout_v_base,
77 template<typename> class layout_e_base,
78 typename grow_p>
79class DistGraph_CSR;
80
81class v_info
82{
83public:
84 typedef boost::fusion::vector<size_t, size_t> type;
85
86 type data;
87
88 static const unsigned int id = 0;
89 static const unsigned int gid = 1;
90 static const unsigned int max_prop = 2;
91
92 v_info()
93 {
94 }
95
96 inline void setid(size_t id_)
97 {
98 boost::fusion::at_c<0>(data) = id_;
99 }
100
101 inline void setgid(size_t gid_)
102 {
103 boost::fusion::at_c<1>(data) = gid_;
104 }
105
106 template<unsigned int id> inline auto get() -> decltype(boost::fusion::at_c < id > (data))
107 {
108 return boost::fusion::at_c<id>(data);
109 }
110
111 template<unsigned int id> inline auto get() const -> const decltype(boost::fusion::at_c < id > (data))
112 {
113 return boost::fusion::at_c<id>(data);
114 }
115
116 template<unsigned int dim, typename Mem> inline v_info(const encapc<dim, v_info, Mem> & p)
117 {
118 this->operator=(p);
119 }
120
121 template<unsigned int dim, typename Mem> inline v_info & operator=(const encapc<dim, v_info, Mem> & p)
122 {
123 boost::fusion::at_c<0>(data) = p.template get<0>();
124 boost::fusion::at_c<1>(data) = p.template get<1>();
125
126 return *this;
127 }
128
129 static bool noPointers()
130 {
131 return true;
132 }
133};
134
135class e_info
136{
137public:
138 typedef boost::fusion::vector<size_t, size_t> type;
139
140 type data;
141
142 static const unsigned int sgid = 0;
143 static const unsigned int dgid = 1;
144 static const unsigned int max_prop = 2;
145
146 e_info()
147 {
148 }
149
150 template<unsigned int id> inline auto get() -> decltype(boost::fusion::at_c < id > (data))
151 {
152 return boost::fusion::at_c<id>(data);
153 }
154
155 template<unsigned int id> inline auto get() const -> const decltype(boost::fusion::at_c < id > (data))
156 {
157 return boost::fusion::at_c<id>(data);
158 }
159
160 template<unsigned int dim, typename Mem> inline e_info(const encapc<dim, e_info, Mem> & p)
161 {
162 this->operator=(p);
163 }
164
165 template<unsigned int dim, typename Mem> inline e_info & operator=(const encapc<dim, e_info, Mem> & p)
166 {
167 boost::fusion::at_c<0>(data) = p.template get<0>();
168 boost::fusion::at_c<1>(data) = p.template get<1>();
169
170 return *this;
171 }
172
173 static bool noPointers()
174 {
175 return true;
176 }
177};
178
179/*! \brief Structure that store a graph in CSR format or basically in compressed adjacency matrix format
180 *
181 * \param V each vertex will encapsulate have this type
182 * \param E each edge will encapsulate this type
183 * \param device Type of device / basicaly it select the layout
184 * for device_cpu is (x_1, p1_1, p2_1, p3_1 ....), ... ( x_n, p1_1, p2_1, p3_1, ...)
185 * for device_gpu is (x_1, ... , x_n) ... (p1_n, ... pn_n)
186 * where x_1 is the index where it end the list of the neighborhood list and pj_k is
187 * the property j for the vertex j. Basically in the first case one array will store
188 * index and property of each vertex, in the second case several array will store
189 * index and property
190 *
191 * \param VertexList structure that store the list of Vertex
192 * \param EdgeList structure that store the list of edge
193 *
194 * \warning This graph is suitable only when we know the graph structure and we build
195 * the graph adding vertexes and edges, removing vertex and edge is EXTREMLY expensive
196 *
197 * ### Example on creating graph, moving vertices and redistribution
198 * \snippet dist_graph_unit_tests.hpp
199 *
200 */
201
202template<typename V, typename E = no_edge,
203 typename Memory = HeapMemory,
204 typename layout_v = typename memory_traits_lin<V>::type,
205 typename layout_e = typename memory_traits_lin<E>::type,
206 template <typename> class layout_v_base = memory_traits_lin,
207 template <typename> class layout_e_base = memory_traits_lin,
208 typename grow_p = openfpm::grow_policy_double>
209class DistGraph_CSR
210{
211 //! Vcluster communication object
212 Vcluster<> & vcl;
213
214 //! Distribution vector
215 openfpm::vector<idx_t> vtxdist;
216
217 //! Fixed distribution vector, it never changes, it maintains always the first decomposition and topology
218 openfpm::vector<idx_t> fvtxdist;
219
220 //! number of slot per vertex
221 size_t v_slot;
222
223 //! Structure that store the vertex properties
224 openfpm::vector<V, Memory,layout_v_base,grow_p, openfpm::vect_isel<V>::value> v;
225
226 //! Structure that store the vertex id and global id
227 openfpm::vector<v_info, Memory, memory_traits_lin, grow_p, openfpm::vect_isel<v_info>::value> v_m;
228
229 //! Structure that store the number of adjacent vertex in e_l for each vertex
230 openfpm::vector<size_t, Memory, layout_v_base, grow_p, openfpm::vect_isel<size_t>::value> v_l;
231
232 //! Structure that store the edge properties
233 openfpm::vector<E, Memory, layout_e_base, grow_p, openfpm::vect_isel<E>::value> e;
234
235 //! Structure that store the edge properties
236 openfpm::vector<e_info, Memory, layout_e_base, grow_p, openfpm::vect_isel<e_info>::value> e_m;
237
238 //! Structure that store for each vertex the adjacent the vertex id and edge id (for property into e)
239 openfpm::vector<e_map, Memory, layout_e_base, grow_p, openfpm::vect_isel<e_map>::value> e_l;
240
241 //! invalid edge element, when a function try to create an in valid edge this object is returned
242 openfpm::vector<E, Memory, layout_e_base, grow_p, openfpm::vect_isel<E>::value> e_invalid;
243
244 //! Map to access to the global vertex id given the vertex id
245 std::unordered_map<size_t, size_t> id2glb;
246
247 //! Map to access the vertex id given the global vertex id
248 std::unordered_map<size_t, size_t> glb2id;
249
250 //! Map to access the local vertex id given the global one
251 std::unordered_map<size_t, size_t> glb2loc;
252
253 //! Struct containing the (sub)graph to send
254 struct SendGraphPack
255 {
256 //! vertex send buffer
257 openfpm::vector<V> send_v;
258 //! vertex info send buffer
259 openfpm::vector<v_info> send_v_m;
260 //! edge send buffer
261 openfpm::vector<E> send_e;
262 //! edge info send buffer
263 openfpm::vector<e_info> send_e_m;
264 //! For each edge contain the child vertex id
265 openfpm::vector<size_t> send_el;
266 //! For each vertex contain the number of children
267 openfpm::vector<size_t> send_es;
268 //! Indicates if the pack is empty or not
269 bool isEmpty = true;
270 };
271
272 //! Pack storing that data to send to other processors
273 openfpm::vector<SendGraphPack> sgp;
274
275 //! Array containing the sent vertices and that will be deleted from the graph
276 openfpm::vector<size_t> v_td;
277
278 //! Structure needed to get vertex position by global id
279 typedef struct
280 {
281 //! vertex id
282 size_t id;
283 // processor containing the vertex
284 size_t pid;
285 } GlobalVInfo;
286
287 //!TODO update description from pdf
288 // Map of GlobalVInfo containing informations of vertices of the INITIAL distribution contained in this processor
289 // ex. if this will contain the first 4 vertices of the distribution (0,1,2,3) it will maintain informations only about these vertices
290 // The key is the vertex global id
291 std::unordered_map<size_t, GlobalVInfo> glbi_map;
292
293 //! Queue of vertex requests
294 openfpm::vector<openfpm::vector<size_t>> vr_queue;
295
296 //! Map containing the ghost vertices of this graph, if bool is false the ghost will be deleted in the next vertices exchange
297 std::unordered_map<size_t, bool> ghs_map;
298
299 //! Structure to store a add request of an edge
300 typedef struct
301 {
302 //! source vertex
303 size_t v1;
304 //! target vertex
305 size_t v2;
306 //! source vertex global index
307 size_t v1n;
308 //! destination vertex global index
309 size_t v2n;
310 } EdgeReq;
311
312 //! Queue of requests to add edges
313 openfpm::vector<EdgeReq> e_queue;
314
315 /*! \brief add edge on the graph
316 *
317 * add edge on the graph
318 *
319 * \param v1 start vertex
320 * \param v2 end vertex
321 *
322 * \return the index of the edge created
323 *
324 */
325 template<typename CheckPolicy = NoCheck> inline size_t addEdge_(size_t v1, size_t v2)
326 {
327 // If v1 and v2 does not satisfy some criteria return
328 if (CheckPolicy::valid(v1, v.size()) == false)
329 {return (size_t)NO_EDGE;}
330 if (CheckPolicy::valid(v2, v.size()) == false)
331 {return (size_t)NO_EDGE;}
332
333 // get the number of adjacent vertex
334 size_t id_x_end = v_l.template get<0>(v1);
335
336#ifdef DEBUG
337
338 // Check that the edge does not already exist
339
340 for (size_t s = 0; s < id_x_end; s++)
341 {
342 if (e_l.template get<e_map::vid>(v1 * v_slot + s) == v2)
343 {
344 std::cerr << "Error graph: the edge already exist\n";
345 }
346 }
347#endif
348
349 // Check if there is space for another edge
350
351 if (id_x_end >= v_slot)
352 {
353 // Unfortunately there is not space we need to reallocate memory
354 // Reallocate with double slot
355
356 // Create an new Graph
357 DistGraph_CSR<V, E> g_new(2 * v_slot, v.size());
358
359 // Copy the graph
360 for (size_t i = 0; i < v.size(); i++)
361 {
362 // copy the property from the old graph
363 g_new.v.set(i, v, 2 * i);
364 }
365
366 // swap the new graph with the old one
367 swap(g_new);
368 }
369
370 // Here we are sure than v and e has enough slots to store a new edge
371 // Check that e_l has enough space to store new edge
372 // should be always e.size == e_l.size
373
374 if (id_x_end >= e_l.size())
375 {
376 // Resize the basic structure
377 e_l.resize(v.size() * v_slot);
378 }
379
380 // add in e_l the adjacent vertex for v1 and fill the edge id
381 e_l.template get<e_map::vid>(v1 * v_slot + id_x_end) = v2;
382 e_l.template get<e_map::eid>(v1 * v_slot + id_x_end) = e.size();
383
384 // add an empty edge
385 e.resize(e.size() + 1);
386 e_m.resize(e_m.size() + 1);
387
388 // Increment the ending point
389 ++v_l.template get<0>(v1);
390
391 // return the created edge
392 return e.size() - 1;
393 }
394
395 /*! \brief Callback to set the size of the receiving vector
396 *
397 * \param msg_i Index of the message
398 * \param total_msg Total number of messages
399 * \param total_p Total number of processors to communicate with
400 * \param i Processor id
401 * \param ri Request id
402 * \param ptr Void pointer parameter for additional data to pass to the call-back
403 */
404 static void * gr_receive(size_t msg_i, size_t total_msg, size_t total_p, size_t i, size_t ri, size_t tag, void * ptr)
405 {
406 openfpm::vector<HeapMemory> *v = static_cast<openfpm::vector<HeapMemory> *>(ptr);
407
408 v->get(i).allocate(msg_i);
409
410 return v->get(i).getPointer();
411
412 }
413
414 /*! \brief Callback of the sendrecv to set the size of the array received
415 *
416 * \param msg_i Index of the message
417 * \param total_msg Total number of messages
418 * \param total_p Total number of processors to communicate with
419 * \param i Processor id
420 * \param ri Request id
421 * \param ptr Void pointer parameter for additional data to pass to the call-back
422 */
423 static void * on_receive(size_t msg_i, size_t total_msg, size_t total_p, size_t i, size_t ri, size_t tag, void * ptr)
424 {
425 openfpm::vector<openfpm::vector<size_t>> *v = static_cast<openfpm::vector<openfpm::vector<size_t>> *>(ptr);
426
427 v->get(i).resize(msg_i / sizeof(size_t));
428
429 return &(v->get(i).get(0));
430 }
431
432 /*! \brief Init communication structures
433 *
434 */
435 void resetExchange()
436 {
437 if (sgp.size() == vcl.getProcessingUnits())
438 {
439 for (size_t p = 0; p < vcl.getProcessingUnits(); ++p)
440 {
441 sgp.get(p).send_v.clear();
442 sgp.get(p).send_v_m.clear();
443 sgp.get(p).send_e.clear();
444 sgp.get(p).send_e_m.clear();
445 sgp.get(p).send_es.clear();
446 sgp.get(p).send_el.clear();
447 sgp.get(p).isEmpty = true;
448 }
449 }
450 else
451 {
452 sgp.resize(vcl.getProcessingUnits());
453
454 for (size_t p = 0; p < vcl.getProcessingUnits(); ++p)
455 {
456 openfpm::vector<V> s_v;
457 openfpm::vector<v_info> s_v_m;
458 openfpm::vector<E> s_e;
459 openfpm::vector<e_info> s_e_m;
460 openfpm::vector<size_t> s_el;
461 openfpm::vector<size_t> s_es;
462
463 sgp.get(p).send_v = s_v;
464 sgp.get(p).send_v_m = s_v_m;
465 sgp.get(p).send_e = s_e;
466 sgp.get(p).send_e_m = s_e_m;
467 sgp.get(p).send_es = s_es;
468 sgp.get(p).send_el = s_el;
469 sgp.get(p).isEmpty = true;
470 }
471 }
472 }
473
474 /*! \brief Remove from this graph the vertices that have been sent
475 *
476 */
477 void deleteMovedVertices()
478 {
479 // Prepare new graph
480 DistGraph_CSR recv_g;
481
482 // Reset maps
483 glb2loc.clear();
484 glb2id.clear();
485 id2glb.clear();
486
487 size_t local_i = 0;
488
489 // Add previous vertices without the sent ones
490 for (size_t i = 0; i < this->getNVertex(); ++i)
491 {
492 if (!isToDelete(i))
493 {
494 recv_g.add_vertex(this->vertex(i), this->getVertexId(i), this->getVertexGlobalId(i));
495
496 for (size_t j = 0; j < this->getNChilds(i); j++)
497 {
498 recv_g.addEdge(local_i, this->getChild(i, j), this->getChildEdge(i, j), this->getChildInfo(i, j));
499 }
500 ++local_i;
501 }
502 }
503
504 recv_g.fvtxdist = fvtxdist;
505
506 // Swap temporary graph with the main one
507 swap(recv_g);
508
509 // Clear vertex to delete array
510 v_td.clear();
511 }
512
513 /*! \brief Check it the vertex i must be deleted or not
514 *
515 * \param i vertex
516 * \return true if to delete, false otherwise
517 */
518 bool isToDelete(size_t i)
519 {
520
521 for (size_t j = 0; j < v_td.size(); ++j)
522 {
523 if (i == v_td.get(j))
524 return true;
525 }
526 return false;
527 }
528
529 /*! \brief Get the processor of the the given vertex id, CAN be used BEFORE re-mapping starts
530 *
531 * \param v id of the vertex
532 * \return process id
533 */
534 size_t getVProcessor(size_t v)
535 {
536 for (size_t i = 1; i < vtxdist.size() - 1; ++i)
537 {
538 if (v < vtxdist.get(i))
539 {
540 return i - 1;
541 }
542 }
543 return vcl.getProcessingUnits() - 1;
544 }
545
546 /*! \brief Send and receive vertices and update current graph
547 *
548 * \tparam Remove the sent sub-graph
549 *
550 */
551 template<bool addAsGhosts>
552 void exchangeVertices()
553 {
554 // If the exchange is not to retrieve ghost vertices delete the vertices this processor is sending
555 if (!addAsGhosts)
556 deleteMovedVertices();
557
558 openfpm::vector<size_t> prc;
559 openfpm::vector<size_t> size;
560 openfpm::vector<void *> ptr;
561 openfpm::vector<HeapMemory> packs(vcl.getProcessingUnits());
562 openfpm::vector<HeapMemory *> to_release;
563 openfpm::vector<ExtPreAlloc<HeapMemory> *> to_release_ext;
564
565 // Total number of vertex to send
566 size_t nvts = 0;
567 for (size_t i = 0; i < vcl.getProcessingUnits(); i++)
568 {
569 nvts += sgp.get(i).send_v.size();
570 }
571
572 // For each processor
573 for (size_t i = 0; i < vcl.getProcessingUnits(); i++)
574 {
575 // if nothing to send continue
576 if (sgp.get(i).isEmpty)
577 continue;
578
579 // process to communicate with TODO remove pc
580 size_t pc = i;
581
582 size_t vp_size = sgp.get(pc).send_v.size();
583
584 size_t req = 0;
585
586 // prepare slot for number of vertices
587 Packer<size_t, HeapMemory>::packRequest(req);
588
589 for (size_t j = 0; j < vp_size; j++)
590 {
591 // prepare slot for vertex
592 Packer<V, HeapMemory>::packRequest(req);
593
594 // prepare slot info for vertex
595 Packer<v_info, HeapMemory>::packRequest(req);
596
597 // prepare slot for the number of children
598 Packer<size_t, HeapMemory>::packRequest(req);
599
600 // prepare slots for the children
601 for (size_t k = 0; k < sgp.get(pc).send_es.get(j); k++)
602 {
603 // prepare slot for edge
604 Packer<E, HeapMemory>::packRequest(req);
605
606 // prepare slot for edge info
607 Packer<e_info, HeapMemory>::packRequest(req);
608
609 // prepare slot for edge target id
610 Packer<size_t, HeapMemory>::packRequest(req);
611 }
612 }
613
614 // allocate the memory
615 HeapMemory & pmem = *(new HeapMemory());
616// pmem.allocate(req);
617 ExtPreAlloc<HeapMemory> & mem = *(new ExtPreAlloc<HeapMemory>(req, pmem));
618 mem.incRef();
619
620 to_release.add(&pmem);
621 to_release_ext.add(&mem);
622
623 Pack_stat sts;
624 size_t e_it = 0;
625
626 // Pack total size
627 Packer<size_t, HeapMemory>::pack(mem, vp_size, sts);
628
629 for (size_t j = 0; j < vp_size; j++)
630 {
631 // Pack the vertex
632 Packer<decltype(sgp.get(pc).send_v.get(0)), HeapMemory>::pack(mem, sgp.get(pc).send_v.get(j), sts);
633
634 // Pack the vertex info
635 Packer<decltype(sgp.get(pc).send_v_m.get(0)), HeapMemory>::pack(mem, sgp.get(pc).send_v_m.get(j), sts);
636
637 // Pack size of the children
638 Packer<size_t, HeapMemory>::pack(mem, sgp.get(pc).send_es.get(j), sts);
639
640 // Pack children
641 for (size_t k = 0; k < sgp.get(pc).send_es.get(j); k++)
642 {
643 // Pack the edge
644 Packer<decltype(sgp.get(pc).send_e.get(0)), HeapMemory>::pack(mem, sgp.get(pc).send_e.get(e_it), sts);
645
646 // Pack the edge info
647 Packer<decltype(sgp.get(pc).send_e_m.get(0)), HeapMemory>::pack(mem, sgp.get(pc).send_e_m.get(e_it), sts);
648
649 // Pack the edge target id
650 Packer<size_t, HeapMemory>::pack(mem, sgp.get(pc).send_el.get(e_it), sts);
651
652 ++e_it;
653 }
654 }
655
656 prc.add(i);
657 size.add(pmem.size());
658 ptr.add(mem.getPointerBase());
659 }
660
661 // Exchange informations through processors
662 vcl.sendrecvMultipleMessagesNBX(prc.size(), (size_t *)size.getPointer(), (size_t *)prc.getPointer(), (void **)ptr.getPointer(), gr_receive, &packs, NONE);
663
664 for (int i = 0 ; i < to_release_ext.size(); i++)
665 {
666 to_release_ext.get(i)->decRef();
667 delete to_release_ext.get(i);
668
669 delete to_release.get(i);
670 }
671
672 for (size_t i = 0; i < vcl.getProcessingUnits(); i++)
673 {
674
675 if (i != vcl.getProcessUnitID() && packs.get(i).size() > 0)
676 {
677 Unpack_stat ps;
678
679 ExtPreAlloc<HeapMemory> mem(packs.get(i).size(), packs.get(i));
680
681 // unpack total number of vertex
682 size_t r_size;
683 Unpacker<size_t, HeapMemory>::unpack(mem, r_size, ps);
684
685 // take previous last item
686 size_t prev = getNVertex();
687
688 for (size_t j = prev; j < prev + r_size; j++)
689 {
690 // unpack the vertex
691 V v_n;
692 Unpacker<V, HeapMemory>::unpack(mem, v_n, ps);
693
694 v_info vm;
695 Unpacker<v_info, HeapMemory>::unpack(mem, vm, ps);
696
697 add_vertex(v_n, vm.template get<v_info::id>(), vm.template get<v_info::gid>());
698
699 if (addAsGhosts)
700 ghs_map.insert( { vm.template get<v_info::gid>(), false });
701
702 // unpack size of children
703 size_t s;
704 Unpacker<size_t, HeapMemory>::unpack(mem, s, ps);
705
706 // prepare slots for the children
707 for (size_t k = 0; k < s; k++)
708 {
709 // unpack edge
710 E e_n;
711 Unpacker<E, HeapMemory>::unpack(mem, e_n, ps);
712
713 // unpack edge
714 e_info e_i;
715 Unpacker<e_info, HeapMemory>::unpack(mem, e_i, ps);
716
717 // unpack vertex id of the edge target
718 size_t el_n;
719 Unpacker<size_t, HeapMemory>::unpack(mem, el_n, ps);
720
721 // add the edge //HERE ERROR modify to add globals
722 addEdge(j, el_n, e_n, e_i);
723 }
724 }
725 }
726 }
727
728 // After the exchange reset all the structures needed for it
729 resetExchange();
730 }
731
732 /*! \brief Update the distribution vector vtxdist
733 *
734 */
735 void updateVtxdist()
736 {
737 // Prepare vtxdist
738 vtxdist.resize(vcl.getProcessingUnits() + 1);
739
740 // Set first element to 0, always the same
741 vtxdist.get(0) = 0;
742
743 // Prepare array that will contain the sizes of all the graphs
744 openfpm::vector<size_t> recv(vcl.getProcessingUnits());
745
746 // Set the local size
747 size_t tv = getNVertex();
748
749 // Sent and receive the size of each subgraph
750 vcl.allGather(tv, recv);
751 vcl.execute();
752
753 // Set the value for this processor
754 recv.get(vcl.getProcessUnitID()) = getNVertex();
755
756 // Update vtxdist
757 for (size_t i = 1; i <= recv.size(); ++i)
758 {
759 vtxdist.get(i) = recv.get(i - 1) + vtxdist.get(i - 1);
760 }
761 }
762
763 /*! \brief Re-map received vertices in order to have ordered vertex ids
764 *
765 */
766 void remap()
767 {
768 size_t p_id = vcl.getProcessUnitID();
769
770 typedef struct
771 {
772 // new vertex id
773 size_t id;
774 // processor rank that contain the vertex
775 size_t pid;
776 } IdnProc;
777
778 // Map that will contain the couples to update the global info map in this processor
779 // The key is the (old vertex id)
780 std::unordered_map<size_t, IdnProc> on_toup;
781
782 // For each processor old, new couples
783 openfpm::vector<openfpm::vector<size_t>> on_info(vcl.getProcessingUnits());
784
785 std::map<size_t, size_t> old_glob2loc(glb2loc.begin(), glb2loc.end());
786 size_t j = vtxdist.get(p_id);
787 size_t i = 0, k = 0;
788
789 // Reset maps of vertices ids
790 id2glb.clear();
791 glb2id.clear();
792 glb2loc.clear();
793
794 // Fix sending couples gid, newid and remove on_toup updating glbi_map here and after receive
795 for (auto it : old_glob2loc)
796 {
797 // The couple to the final map, needed to update the vertices in this sub-graph
798 IdnProc nidpid = { j, p_id };
799 on_toup.insert( { v_m.get(it.second).template get<v_info::id>(), nidpid });
800
801 // fill the re-mapping information for each processors that need it
802 on_info.get(getInfoProc(it.first)).add(v_m.get(it.second).template get<v_info::id>());
803 on_info.get(getInfoProc(it.first)).add(j);
804
805 // Re-map the vertex
806 map_v(j, v_m.get(it.second).template get<v_info::gid>(), it.second);
807
808 j++;
809 i++;
810 k += 2;
811 }
812
813 // Prepare structures to send the old-new couples
814 openfpm::vector<size_t> prc;
815 openfpm::vector<size_t> size;
816 openfpm::vector<void *> ptr;
817
818 // Array that will contain the couples, divided per processor
819 openfpm::vector<openfpm::vector<size_t>> on_vs(vcl.getProcessingUnits());
820
821 fillSendRecvStructs<size_t>(on_info, prc, size, ptr);
822
823 // Send on_info
824 vcl.sendrecvMultipleMessagesNBX(prc.size(), (size_t *)size.getPointer(), (size_t *)prc.getPointer(), (void **)ptr.getPointer(), on_receive, &on_vs, NONE);
825
826 // Insert in the on_toup map the received couples
827 for (size_t i = 0; i < vcl.getProcessingUnits(); i++)
828 {
829 if (i != vcl.getProcessUnitID() && on_vs.get(i).size() > 0) // redundant check 2nd arg in if
830 {
831 for (size_t j = 0; j < on_vs.get(i).size() - 1; j += 2) // -1 is useless
832 {
833 IdnProc nidpid = { on_vs.get(i).get(j + 1), i };
834 on_toup.insert( { on_vs.get(i).get(j), nidpid });
835 }
836 }
837 }
838
839 // Update the glbi_map with the new ids and the processor info
840 for (auto k : glbi_map)
841 {
842 auto search = on_toup.find(glbi_map.at(k.first).id); // fix with (k.second).id
843 if (search != on_toup.end())
844 {
845 GlobalVInfo t = { (search->second).id, (search->second).pid };
846 glbi_map.at(k.first) = t;
847 }
848 }
849
850 // Vector of vertices global id I need info
851 openfpm::vector<openfpm::vector<size_t>> vni(vcl.getProcessingUnits());
852
853 // Map of re-mapping info
854 std::unordered_map<size_t, size_t> rmi_m(vcl.getProcessingUnits()); // TODO elimin
855
856 // Check which vertices I need to ask info about
857 for (size_t i = 0; i < getNVertex(); ++i)
858 {
859 for (size_t j = 0; j < getNChilds(i); ++j)
860 {
861 // Here we get the global vertex id of all the children
862 size_t vid = getChildDstGid(i, j);
863 // We check which processor has the information about this vertex
864 size_t pid = getInfoProc(vid);
865
866 // if the vertex info is not in this processor I have to make a request to the right processor
867 if (!vertexIsInThisGraph(vid) && pid != vcl.getProcessUnitID())
868 {
869 // add to requests
870 vni.get(pid).add(vid);
871 }
872 else if (pid == vcl.getProcessUnitID())
873 {
874 // if info is in this processor add it in the map
875 rmi_m.insert( { vid, glbi_map.at(vid).id });
876 }
877 else if (vertexIsInThisGraph(vid)) // check if it is needed, probably not because the glbi_map is update
878 {
879 // if the vertex is in this graph, add the new id in the map
880 rmi_m.insert( { vid, glb2id.at(vid) });
881 }
882 }
883 }
884
885 // Array that will contain the requests from the other processors
886 openfpm::vector<openfpm::vector<size_t>> req_rmi(vcl.getProcessingUnits());
887
888 // Fill the structures for sendrecvMultipleMessagesNBX function
889 fillSendRecvStructs<size_t>(vni, prc, size, ptr);
890
891 // Send and receive requests
892 vcl.sendrecvMultipleMessagesNBX(prc.size(), (size_t *)size.getPointer(), (size_t *)prc.getPointer(), (void **)ptr.getPointer(), on_receive, &req_rmi, NONE);
893
894 // Re-mapping info map
895 openfpm::vector<openfpm::vector<size_t>> rmi(vcl.getProcessingUnits());
896
897 // Array that will contain the response to previous requests
898 openfpm::vector<openfpm::vector<size_t>> resp_rmi(vcl.getProcessingUnits());
899
900 // Prepare re-mapping info response
901 for (size_t i = 0; i < req_rmi.size(); ++i)
902 {
903 for (size_t j = 0; j < req_rmi.get(i).size(); ++j)
904 {
905 resp_rmi.get(i).add(glbi_map.at(req_rmi.get(i).get(j)).id);
906 }
907 }
908
909 // Fill the structures for sendrecvMultipleMessagesNBX function
910 fillSendRecvStructs<size_t>(resp_rmi, prc, size, ptr);
911
912 // Send responses
913 vcl.sendrecvMultipleMessagesNBX(prc.size(), (size_t *)size.getPointer(), (size_t *)prc.getPointer(), (void **)ptr.getPointer(), on_receive, &rmi, NONE);
914
915 // Add received info into re-mapping info map
916 for (size_t i = 0; i < rmi.size(); ++i)
917 {
918 for (size_t j = 0; j < rmi.get(i).size(); ++j)
919 {
920 rmi_m.insert( { vni.get(i).get(j), rmi.get(i).get(j) });
921 }
922 }
923
924 // Finally re-map the edges
925 for (size_t i = 0; i < getNVertex(); ++i)
926 {
927 for (size_t s = 0; s < getNChilds(i); s++)
928 {
929 e_l.template get<e_map::vid>(i * v_slot + s) = rmi_m.at(getChildDstGid(i, s));
930 }
931 }
932 }
933
934 /*! \brief Initialize the fixed structure for global mapping. See glbiv for details.
935 *
936 */
937 void initGlbimap()
938 {
939 size_t pid = vcl.getProcessUnitID();
940
941 for (size_t i = 0; i < getNVertex(); ++i)
942 {
943 GlobalVInfo info;
944 info.id = v_m.get(i).template get<v_info::id>();
945 info.pid = pid;
946 glbi_map.insert( { v_m.get(i).template get<v_info::gid>(), info });
947 }
948 }
949
950 /*! \brief Get the processor id of the processor containing the vertex with global id vid
951 *
952 * \param vid vertex to know info about
953 * \return the processor id
954 */
955 size_t getInfoProc(size_t vid)
956 {
957 for (size_t i = 0; i < fvtxdist.size() - 1; ++i)
958 {
959 if (vid >= (size_t)fvtxdist.get(i) && vid < (size_t)fvtxdist.get(i + 1))
960 {
961 return i;
962 }
963 }
964 return vcl.getProcessingUnits() - 1;
965 }
966
967 /*! \brief Fill the prc, size and ptr structures with the data of vec
968 *
969 * \tparam type of the data inside vec
970 *
971 * \param vec vector of the data
972 * \param prc processor array of sendrecv function
973 * \param size size array of sendrecv function
974 * \param ptr pointers array of sendrecv function
975 */
976 template<typename T>
977 void fillSendRecvStructs(openfpm::vector<openfpm::vector<T>> &vec, openfpm::vector<size_t> &prc, openfpm::vector<size_t> &size, openfpm::vector<void *> &ptr)
978 {
979 // Reset sendrecv structures
980 prc.clear();
981 size.clear();
982 ptr.clear();
983
984 for (size_t i = 0; i < vec.size(); ++i)
985 {
986 if (vec.get(i).size() > 0 && i != vcl.getProcessUnitID())
987 {
988 prc.add(i);
989 size.add(vec.get(i).size() * sizeof(T));
990 ptr.add(vec.get(i).getPointer());
991 }
992 }
993 }
994
995public:
996
997 //! Vertex typedef
998 typedef V V_type;
999
1000 //! Edge typedef
1001 typedef E E_type;
1002
1003 //! Object container for the vertex, for example can be encap<...> (map_grid or openfpm::vector)
1004 typedef typename openfpm::vector<V, Memory, layout_v_base, grow_p, openfpm::vect_isel<V>::value>::container V_container;
1005
1006 //! Object container for the edge, for example can be encap<...> (map_grid or openfpm::vector)
1007 typedef typename openfpm::vector<E, Memory, layout_e_base, grow_p, openfpm::vect_isel<E>::value>::container E_container;
1008
1009 /*! \brief It duplicate the graph
1010 *
1011 * \return a graph duplicate of the first
1012 *
1013 */
1014
1015 DistGraph_CSR<V, E, Memory, layout_v, layout_e,layout_v_base,layout_e_base, grow_p> duplicate() const
1016 {
1017 DistGraph_CSR<V, E, Memory, layout_v, layout_e,layout_v_base,layout_e_base, grow_p> dup;
1018
1019 dup.v_slot = v_slot;
1020
1021 // duplicate all the structures
1022
1023 dup.v.swap(v.duplicate());
1024 dup.v_m.swap(v_m.duplicate());
1025 dup.v_l.swap(v_l.duplicate());
1026 dup.glb2id = glb2id;
1027 dup.id2glb = id2glb;
1028 dup.glb2loc = glb2loc;
1029 dup.e.swap(e.duplicate());
1030 dup.e_m.swap(e_m.duplicate());
1031 dup.e_l.swap(e_l.duplicate());
1032 dup.e_invalid.swap(e_invalid.duplicate());
1033 dup.vtxdist.swap(vtxdist.duplicate());
1034 dup.fvtxdist.swap(fvtxdist.duplicate());
1035 return dup;
1036 }
1037
1038 /*! \brief Constructor
1039 *
1040 * Constructor
1041 *
1042 */
1043 DistGraph_CSR(const DistGraph_CSR & dg) :
1044 vcl(create_vcluster())
1045 {
1046 this->operator=(dg);
1047 }
1048
1049 /*! \brief Constructor
1050 *
1051 * Constructor
1052 *
1053 */
1054 DistGraph_CSR(DistGraph_CSR && dg)
1055 :vcl(create_vcluster())
1056 {
1057 this->operator=(dg);
1058 }
1059
1060 /*! \brief Constructor
1061 *
1062 * Constructor
1063 *
1064 */
1065 DistGraph_CSR() :
1066 DistGraph_CSR(0, 16)
1067 {
1068 }
1069
1070 /*! \brief Constructor
1071 *
1072 * Constructor
1073 *
1074 */
1075 DistGraph_CSR(size_t n_vertex) :
1076 DistGraph_CSR(n_vertex, 16)
1077 {
1078 }
1079
1080 /*! \brief Constructor
1081 *
1082 * Constructor
1083 *
1084 */
1085 DistGraph_CSR(size_t n_vertex, size_t n_slot) :
1086 vcl(create_vcluster()), v_slot(n_slot)
1087 {
1088 // Creating n_vertex into the graph
1089 v.resize(n_vertex);
1090 // Creating n_vertex info objects into the graph
1091 v_m.resize(n_vertex);
1092 // Creating n_vertex adjacency list counters
1093 v_l.resize(n_vertex);
1094 // no edge set the counter to zero
1095 v_l.fill(0);
1096 // create one invalid edge
1097 e_invalid.resize(1);
1098 // init communication structures
1099 resetExchange();
1100 }
1101
1102 /*! \brief Operator to access the decomposition vector
1103 *
1104 * \param v vector that will contain the decomposition
1105 */
1106 void getDecompositionVector(openfpm::vector<idx_t> &v)
1107 {
1108 v.resize(vtxdist.size());
1109
1110 for (size_t i = 0; i < vtxdist.size(); ++i)
1111 {
1112 v.get(i) = vtxdist.get(i);
1113 }
1114 }
1115
1116 /*! \brief Operator to access the decomposition vector
1117 *
1118 * \return a pointer to the distribution vector
1119 */
1120 openfpm::vector<idx_t>* getVtxdist()
1121 {
1122 return &vtxdist;
1123 }
1124
1125 /*! \brief Operator to access the decomposition vector
1126 *
1127 * \param v vector that contains the decomposition
1128 */
1129 void initDistributionVector(openfpm::vector<idx_t> &v)
1130 {
1131 vtxdist.resize(vcl.getProcessingUnits() + 1);
1132 fvtxdist.resize(vcl.getProcessingUnits() + 1);
1133
1134 for (size_t i = 0; i < vtxdist.size(); ++i)
1135 {
1136 vtxdist.get(i) = v.get(i);
1137 fvtxdist.get(i) = v.get(i);
1138 }
1139 }
1140
1141 /*! \brief Initialize the vtxdist and the fvtxdist
1142 *
1143 */
1144 void initDistributionVector()
1145 {
1146 updateVtxdist();
1147
1148 fvtxdist.resize(vcl.getProcessingUnits() + 1);
1149
1150 for (size_t i = 0; i < vtxdist.size(); ++i)
1151 {
1152 fvtxdist.get(i) = vtxdist.get(i);
1153 }
1154 }
1155
1156 /*! \brief Copy constructor
1157 *
1158 * \param v_cl vcluster
1159 * \param gg distributed graph to copy
1160 *
1161 */
1162 DistGraph_CSR(Vcluster<> & vcl, DistGraph_CSR<V, E, Memory> && g) :
1163 vcl(vcl)
1164 {
1165 swap(g);
1166 }
1167
1168 /*! \brief Copy the graph
1169 *
1170 * \param g distributed graph to copy
1171 *
1172 * \return itself
1173 *
1174 */
1175 DistGraph_CSR<V, E, Memory> & operator=(DistGraph_CSR<V, E, Memory> && g)
1176 {
1177 swap(g);
1178
1179 return *this;
1180 }
1181
1182 /*! \brief Copy the graph
1183 *
1184 * \param g graph to copy
1185 *
1186 * \return itself
1187 *
1188 */
1189 DistGraph_CSR<V, E, Memory> & operator=(const DistGraph_CSR<V, E, Memory> & g)
1190 {
1191 swap(g.duplicate());
1192
1193 return *this;
1194 }
1195
1196 /*! \brief operator to access the vertex
1197 *
1198 * operator to access the vertex
1199 *
1200 * \tparam i property to access
1201 * \param id of the vertex to access
1202 *
1203 * \return a reference to the vertex property
1204 *
1205 */
1206 template<unsigned int i> auto vertex_p(size_t id) -> decltype( v.template get<i>(id) )
1207 {
1208 return v.template get<i>(id);
1209 }
1210
1211 /*! \brief Access the vertex
1212 *
1213 * \tparam i property to access
1214 * \param id of the vertex to access
1215 *
1216 * \return a reference to the vertex property
1217 *
1218 */
1219 template<unsigned int i> auto vertex_p(grid_key_dx<1> id) -> decltype( v.template get<i>(id) )
1220 {
1221 return v.template get<i>(id);
1222 }
1223
1224 /*! \brief Function to access the vertexes
1225 *
1226 * \param id of the vertex to access
1227 *
1228 * \return the vertex
1229 *
1230 */
1231 auto vertex(size_t id) -> decltype( v.get(id) )
1232 {
1233 return v.get(id);
1234 }
1235
1236 /*! \brief operator to access the vertex
1237 *
1238 * operator to access the vertex
1239 *
1240 * \param id of the vertex to access
1241 *
1242 * \return the vertex
1243 *
1244 */
1245 auto vertex(grid_key_dx<1> id) -> decltype( v.get(id.get(0)) )
1246 {
1247 return v.get(id.get(0));
1248 }
1249
1250 /*! \brief operator to access the vertex
1251 *
1252 * operator to access the vertex
1253 *
1254 * \param id of the vertex to access
1255 *
1256 * \return the vertex
1257 *
1258 */
1259 auto vertex(openfpm::vector_key_iterator id) -> decltype( v.get(0) )
1260 {
1261 return v.get(id.get());
1262 }
1263
1264 /*! \brief Function to access the vertexes
1265 *
1266 * \param id of the vertex to access
1267 *
1268 * \return the vertex
1269 *
1270 */
1271 auto vertex(size_t id) const -> const decltype( v.get(id) )
1272 {
1273 return v.get(id);
1274 }
1275
1276 /*! \brief operator to access the vertex
1277 *
1278 * operator to access the vertex
1279 *
1280 * \param id of the vertex to access
1281 *
1282 * \return the vertex
1283 *
1284 */
1285 auto vertex(grid_key_dx<1> id) const -> const decltype( v.get(id.get(0)) )
1286 {
1287 return v.get(id.get(0));
1288 }
1289
1290 /*! \brief operator to access the vertex
1291 *
1292 * operator to access the vertex
1293 *
1294 * \param id of the vertex to access
1295 *
1296 * \return the vertex
1297 *
1298 */
1299 auto vertex(openfpm::vector_key_iterator id) const -> const decltype( v.get(0) )
1300 {
1301 return v.get(id.get());
1302 }
1303
1304 /*! \brief operator to access the vertex info
1305 *
1306 * operator to access the vertex
1307 *
1308 * \param id of the vertex to access
1309 *
1310 * \return the vertex global id
1311 *
1312 */
1313 auto vertex_info(openfpm::vector_key_iterator id) const -> const decltype( v_m.get(0) )
1314 {
1315 return v_m.get(id.get());
1316 }
1317
1318 /*! \brief Function to access the vertexes
1319 *
1320 * \param id GLOBAL id of the vertex to access
1321 *
1322 * \return the vertex
1323 *
1324 */
1325 auto getVertex(size_t id) -> decltype( v.get(id) )
1326 {
1327
1328#ifdef SE_CLASS1
1329
1330 if (glb2loc.find(id) == glb2loc.end())
1331 {
1332 std::cerr << __FILE__ << ":" << __LINE__ << " The vertex with global id " << id << " is not in this sub-graph. Try to call reqVertex(" << id << ") and sync() first.\n";
1333 ACTION_ON_ERROR(DIST_GRAPH_ERROR);
1334 }
1335
1336#endif
1337
1338 return v.get(glb2loc.find(id)->second);
1339 }
1340
1341 /*! \brief Function to access the vertexes
1342 *
1343 * \param id GLOBAL id of the vertex to access
1344 *
1345 * \return the vertex
1346 *
1347 */
1348 auto getVertex(size_t id) const -> const decltype( v.get(0) )
1349 {
1350 try
1351 {
1352 return v.get(glb2loc.at(id));
1353 } catch (const std::out_of_range& oor)
1354 {
1355 std::cerr << "The vertex with global id " << id << " is not in this sub-graph. Try to call reqVertex(" << id << ") and sync() first.\n";
1356 }
1357
1358 return v.get(0);
1359 }
1360
1361 /*! \brief operator to access the vertex position index by id property
1362 *
1363 * operator to access the vertex
1364 *
1365 * \param id id of the vertex to access
1366 *
1367 * \return id of the vertex
1368 *
1369 */
1370 size_t nodeById(size_t id) const
1371 {
1372 try
1373 {
1374 return glb2loc.at(id2glb.at(id));
1375 } catch (const std::out_of_range& oor)
1376 {
1377 std::cout << "Node not found by glb: " << id << std::endl;
1378 }
1379
1380 return 0;
1381 }
1382
1383 /*! /brief Get the first id of the graph
1384 *
1385 * \return the first id of the graph
1386 */
1387 size_t firstId() const
1388 {
1389 return vtxdist.get(vcl.getProcessUnitID());
1390 }
1391
1392 /*! /brief Get the last id of the graph
1393 *
1394 * \return the last id of the graph
1395 */
1396 size_t lastId() const
1397 {
1398 return vtxdist.get(vcl.getProcessUnitID() + 1) - 1;
1399 }
1400
1401 /*! \brief Get the id of a vertex given its index position
1402 *
1403 * \param i position of the vertex
1404 * \return the id of the vertex
1405 */
1406 size_t getVertexId(size_t i) const
1407 {
1408 return v_m.get(i).template get<v_info::id>();
1409 }
1410
1411 /*! \brief Get the id of a vertex given its index position
1412 *
1413 * \param i position of the vertex
1414 * \return the id of the vertex
1415 */
1416 size_t getVertexGlobalId(size_t i) const
1417 {
1418 return v_m.get(i).template get<v_info::gid>();
1419 }
1420
1421 /*! \brief Check if the vertex with GLOBAL id is in this graph
1422 *
1423 * \param id global id of the vertex
1424 * \return true if vertex with gid is in this graph, false otherwise
1425 */
1426 bool vertexIsInThisGraph(size_t id)
1427 {
1428 auto search = glb2id.find(id);
1429
1430 if (search != glb2id.end())
1431 {
1432 return true;
1433 }
1434 else
1435 {
1436 return false;
1437 }
1438 }
1439
1440 /*! \brief operator to update all the hashmap
1441 *
1442 * \param n new vertex id
1443 * \param g global vertex id
1444 * \param l local vertex id
1445 *
1446 * \tparam i id of the property storing the id
1447 *
1448 */
1449 void map_v(size_t n, size_t g, size_t l)
1450 {
1451 id2glb.insert( { n, g });
1452 glb2id.insert( { g, n });
1453 glb2loc.insert( { g, l });
1454 v_m.get(l).template get<v_info::id>() = n;
1455 }
1456
1457 /*! \brief operator to clear the whole graph
1458 *
1459 * operator to clear all
1460 *
1461 */
1462 void clear()
1463 {
1464 v.clear();
1465 v_m.clear();
1466 e.clear();
1467 id2glb.clear();
1468 glb2id.clear();
1469 glb2loc.clear();
1470 v_l.clear();
1471 e_l.clear();
1472 e_invalid.clear();
1473 }
1474
1475 /*! \brief Access the edge
1476 *
1477 * \tparam i property to access
1478 * \param id of the edge to access
1479 *
1480 * \return a reference to the edge property
1481 *
1482 */
1483 template<unsigned int i> auto edge_p(grid_key_dx<1> id) -> decltype ( e.template get<i>(id) )
1484 {
1485 return e.template get<i>(id);
1486 }
1487
1488 /*! \brief Access the edge
1489 *
1490 * \tparam i property to access
1491 * \param id of the edge to access
1492 *
1493 * \return a reference to the edge property
1494 *
1495 */
1496 template<unsigned int i> auto edge_p(size_t id) -> decltype ( e.template get<i>(id) )
1497 {
1498 return e.template get<i>(id);
1499 }
1500
1501 /*! \brief Access the edge
1502 *
1503 * \param id of the edge to access
1504 *
1505 * \return a reference to the edge
1506 *
1507 */
1508 auto edge(grid_key_dx<1> id) const -> const decltype ( e.get(id.get(0)) )
1509 {
1510 return e.get(id.get(0));
1511 }
1512
1513 /*! \brief operator to access the edge
1514 *
1515 * \param ek key of the edge
1516 *
1517 * \return a reference to the edge
1518 *
1519 */
1520 auto edge(edge_key ek) const -> const decltype ( e.get(0) )
1521 {
1522 return e.get(e_l.template get<e_map::eid>(ek.pos * v_slot + ek.pos_e));
1523 }
1524
1525 /*! \brief operator to access the edge
1526 *
1527 * \param ek key of the edge
1528 *
1529 * \param return a reference to the edge
1530 *
1531 */
1532 auto getEdge(edge_key ek) const -> const decltype ( e.get(0) )
1533 {
1534 size_t v;
1535
1536 try
1537 {
1538 v = glb2loc.at(ek.pos);
1539 } catch (const std::out_of_range& oor)
1540 {
1541 std::cout << "The source vertex of this edge is not in this graph.\n";
1542 }
1543
1544 return e.get(e_l.template get<e_map::eid>(v * v_slot + ek.pos_e));
1545 }
1546
1547 /*! \brief operator to access the edge
1548 *
1549 * operator to access the edge
1550 *
1551 * \param id of the edge to access
1552 *
1553 * \return a reference to the edge
1554 *
1555 */
1556 auto edge(size_t id) const -> const decltype ( e.get(id) )
1557 {
1558 return e.get(id);
1559 }
1560
1561 /*! \brief Return the number of children of a vertex
1562 *
1563 * \param c Child id
1564 *
1565 * \return the number of children
1566 *
1567 */
1568 inline size_t getNChilds(size_t c) const
1569 {
1570 return v_l.template get<0>(c);
1571 }
1572
1573 /*! \brief Return the number of childs of a vertex
1574 *
1575 * \param c child id
1576 *
1577 * \return the number of childs
1578 *
1579 */
1580 inline size_t getNChilds(typename openfpm::vector<V, Memory, layout_v_base, grow_p, openfpm::vect_isel<V>::value>::iterator_key & c)
1581 {
1582 return v_l.template get<0>(c.get());
1583 }
1584
1585 /*! \brief Return the number of children of a vertex given its global id
1586 *
1587 * \param v vertex global id
1588 *
1589 * \return the number of children
1590 *
1591 */
1592 inline size_t getNEdge(size_t v) const
1593 {
1594 try
1595 {
1596 v = glb2loc.at(v);
1597 } catch (const std::out_of_range& oor)
1598 {
1599 std::cout << "The source vertex of this edge is not in this graph.\n";
1600 }
1601
1602 return v_l.template get<0>(v);
1603 }
1604
1605 /*! \brief Get the vertex edge
1606 *
1607 * \param v vertex
1608 * \param v_e edge id
1609 *
1610 * \return the edge
1611 *
1612 */
1613 inline auto getChildEdge(size_t v, size_t v_e) -> decltype(e.get(0))
1614 {
1615 return e.get(e_l.template get<e_map::eid>(v * v_slot + v_e));
1616 }
1617
1618 /*! \brief Get the vertex edge info
1619 *
1620 * \param v vertex
1621 * \param v_e edge id
1622 *
1623 * \return the id of the edge
1624 *
1625 */
1626 inline auto getChildInfo(size_t v, size_t v_e) -> decltype(e_m.get(0))
1627 {
1628 return e_m.get(e_l.template get<e_map::eid>(v * v_slot + v_e));
1629 }
1630
1631 /*! \brief Get the vertex edge given the vertex global id as source
1632 *
1633 * \param v vertex global id
1634 * \param v_e edge id
1635 *
1636 * \return the edge
1637 *
1638 */
1639 inline auto getEdge(size_t v, size_t v_e) -> decltype(e.get(0))
1640 {
1641 try
1642 {
1643 v = glb2loc.at(v);
1644 } catch (const std::out_of_range& oor)
1645 {
1646 std::cout << "The source vertex of this edge is not in this graph.\n";
1647 }
1648
1649 return e.get(e_l.template get<e_map::eid>(v * v_slot + v_e));
1650 }
1651
1652 /*! \brief Get the child edge
1653 *
1654 * \param v node
1655 * \param i child at position i
1656 *
1657 * \return the edge id that connect v with the target at position i
1658 *
1659 */
1660 inline size_t getChild(size_t v, size_t i) const
1661 {
1662#ifdef SE_CLASS1
1663 if (i >= v_l.template get<0>(v))
1664 {
1665 std::cerr << "Error " << __FILE__ << " line: " << __LINE__ << " vertex " << v << " does not have edge " << i << " on processor " << vcl.getProcessUnitID() << "\n";
1666 }
1667
1668 if (e.size() <= e_l.template get<e_map::eid>(v * v_slot + i))
1669 {
1670 std::cerr << "Error " << __FILE__ << " " << __LINE__ << " vertex " << v << " does not have edge " << i << " on processor " << vcl.getProcessUnitID() << " (" << e.size() << "<=" << e_l.template get<e_map::eid>(v * v_slot + i) << ")\n";
1671 }
1672#endif
1673 // Get the edge id
1674 return e_l.template get<e_map::vid>(v * v_slot + i);
1675 }
1676
1677 /*! \brief Get the child edge
1678 *
1679 * \param i id of the child
1680 *
1681 * \return the edge id that connect v with the target at position i
1682 *
1683 */
1684 inline size_t getChild(size_t i) const
1685 {
1686 // Get the edge id
1687 return e_l.template get<e_map::vid>(i);
1688 }
1689
1690 /*! \brief Get the child edge
1691 *
1692 * \param v node
1693 * \param i child at position i
1694 *
1695 * \return the target i connected by an edge node, for the node v
1696 *
1697 */
1698 inline size_t getChild(typename openfpm::vector<V, Memory, layout_v_base, grow_p, openfpm::vect_isel<V>::value>::iterator_key & v, size_t i)
1699 {
1700#ifdef DEBUG
1701 if (i >= v_l.template get<0>(v.get()))
1702 {
1703 std::cerr << "Error " << __FILE__ << " line: " << __LINE__ << " vertex " << v.get() << " does not have edge " << i << "\n";
1704 }
1705
1706 if (e.size() <= e_l.template get<e_map::eid>(v.get() * v_slot + i))
1707 {
1708 std::cerr << "Error " << __FILE__ << " " << __LINE__ << " vertex " << v.get() << " does not have edge " << i << "\n";
1709 }
1710#endif
1711
1712 // Get the edge id
1713 return e_l.template get<e_map::vid>(v.get() * v_slot + i);
1714 }
1715
1716 /*! \brief Add vertex vrt with global id and id properties
1717 *
1718 * \param vrt vertex object to add
1719 * \param gid global id, unique in global graph
1720 * \param id id, unique n global graph
1721 */
1722 inline void add_vertex(const V & vrt, size_t id, size_t gid)
1723 {
1724 // Create vertex info object
1725 v_info vm;
1726 vm.template get<v_info::id>() = id;
1727 vm.template get<v_info::gid>() = gid;
1728
1729 // Add the vertex info
1730 v_m.add(vm);
1731
1732 // Add the vertex
1733 v.add(vrt);
1734
1735 // Update id to global map
1736 id2glb.insert( { id, gid });
1737
1738 // Update global id to local index
1739 glb2loc.insert( { gid, v.size() - 1 });
1740
1741 // Update global id to id
1742 glb2id.insert( { gid, id });
1743
1744 // Set the number of adjacent vertex for this vertex to 0
1745 v_l.add(0ul);
1746
1747 // Add a slot for the vertex adjacency list
1748 e_l.resize(e_l.size() + v_slot);
1749 }
1750
1751 /*! \brief Add vertex vrt with global id and id properties
1752 *
1753 * \param vrt vertex object to add
1754 * \param id of the vertex
1755 * \param gid global id, unique in global graph
1756 */
1757 template<unsigned int dim, typename Mem> inline void add_vertex(const encapc<dim, V, Mem> & vrt, size_t id, size_t gid)
1758 {
1759 // Create vertex info object
1760 v_info vm;
1761 vm.template get<v_info::id>() = id;
1762 vm.template get<v_info::gid>() = gid;
1763
1764 // Add the vertex info
1765 v_m.add(vm);
1766
1767 // Add the vertex
1768 v.add(vrt);
1769
1770 // Update id to global map
1771 id2glb.insert( { id, gid });
1772
1773 // Update global id to local index
1774 glb2loc.insert( { gid, v.size() - 1 });
1775
1776 // Update global id to id
1777 glb2id.insert( { gid, id });
1778
1779 // Set the number of adjacent vertex for this vertex to 0
1780 v_l.add(0ul);
1781
1782 // Add a slot for the vertex adjacency list
1783 e_l.resize(e_l.size() + v_slot);
1784 }
1785
1786 /*! \brief Add vertex vrt with global id and id properties
1787 *
1788 * \param vrt vertex object to add
1789 * \param gid global id, unique in global graph
1790 */
1791 inline void add_vertex(const V & vrt, size_t gid)
1792 {
1793 add_vertex(vrt, gid, gid);
1794 }
1795
1796 /*! \brief map global id to local id
1797 *
1798 * \param g global id
1799 * \param l local index
1800 * \param i id
1801 */
1802 void setGlobalMap(size_t g, size_t l, size_t i)
1803 {
1804 v_m.template get<v_info::id>(l) = i;
1805
1806 v_m.template get<v_info::gid>(l) = g;
1807
1808 // Set global id to local index
1809 glb2loc.insert( { g, l });
1810
1811 // Set global id to id
1812 glb2id.insert( { g, i });
1813
1814 // Set id to global map
1815 id2glb.insert( { i, g });
1816 }
1817
1818 inline auto addEdge(size_t v1, size_t v2, size_t srcgid, size_t dstgid) -> decltype(e.get(0))
1819 {
1820 // add an edge
1821 long int id_x_end = addEdge_<NoCheck>(v1, v2);
1822 // If there is not edge return an invalid edge, is a kind of stub object
1823 if (id_x_end == NO_EDGE)
1824 return e_invalid.get(0);
1825
1826 // set source and destination global ids of the edge
1827 e_m.template get<e_info::sgid>(id_x_end) = srcgid;
1828 e_m.template get<e_info::dgid>(id_x_end) = dstgid;
1829
1830 // return the edge to change the properties
1831 return e.get(id_x_end);
1832 }
1833
1834 inline auto addEdge(size_t v1, size_t v2, size_t srcgid, size_t dstgid, const E & ed) -> decltype(e.get(0))
1835 {
1836 // add an edge
1837 long int id_x_end = addEdge_<NoCheck>(v1, v2);
1838 // If there is not edge return an invalid edge, is a kind of stub object
1839 if (id_x_end == NO_EDGE)
1840 return e_invalid.get(0);
1841
1842 // add in e_l the edge properties
1843 e.set(id_x_end, ed);
1844
1845 // set source and destination global ids of the edge
1846 e_m.template get<e_info::sgid>(id_x_end) = srcgid;
1847 e_m.template get<e_info::dgid>(id_x_end) = dstgid;
1848
1849 // return the edge to change the properties
1850 return e.get(id_x_end);
1851 }
1852
1853 template<unsigned int dim, typename Mem, typename Mem1> inline auto addEdge(size_t v1, size_t v2, const encapc<dim, E, Mem> & ed, const encapc<dim, e_info, Mem1> & ei) -> decltype(e.get(0))
1854 {
1855 // add an edge
1856 long int id_x_end = addEdge_<NoCheck>(v1, v2);
1857 // If there is not edge return an invalid edge, is a kind of stub object
1858 if (id_x_end == NO_EDGE)
1859 return e_invalid.get(0);
1860
1861 // set the edge object and the edge info object
1862 e.set(id_x_end, ed);
1863 e_m.set(id_x_end, ei);
1864
1865 // return the edge to change the properties
1866 return e.get(id_x_end);
1867 }
1868
1869 inline auto addEdge(size_t v1, size_t v2, const E & ed, const e_info & ei) -> decltype(e.get(0))
1870 {
1871 // add an edge
1872 long int id_x_end = addEdge_<NoCheck>(v1, v2);
1873 // If there is not edge return an invalid edge, is a kind of stub object
1874 if (id_x_end == NO_EDGE)
1875 return e_invalid.get(0);
1876
1877 // set the edge object and the edge info object
1878 e.set(id_x_end, ed);
1879 e_m.set(id_x_end, ei);
1880
1881 // return the edge to change the properties
1882 return e.get(id_x_end);
1883 }
1884
1885 /*! \brief Get the global id of edge's source vertex
1886 *
1887 * \param v1 source vertex of the edge
1888 * \param s n child of vertex v1
1889 * \return global id of the source vertex
1890 */
1891 size_t getChildSrcGid(size_t v1, size_t s)
1892 {
1893 size_t eid = e_l.template get<e_map::eid>(v1 * v_slot + s);
1894 return e_m.template get<e_info::sgid>(eid);
1895 }
1896
1897 /*! \brief Get the global id of edge's destination vertex
1898 *
1899 * \param v1 source vertex of the edge
1900 * \param s n child of vertex v1
1901 * \return global id of the destination vertex
1902 */
1903 size_t getChildDstGid(size_t v1, size_t s)
1904 {
1905 size_t eid = e_l.template get<e_map::eid>(v1 * v_slot + s);
1906 return e_m.template get<e_info::dgid>(eid);
1907 }
1908
1909 /*! \brief Add an edge between vertices v1 end v2, needs syncEdge() to complete the action
1910 *
1911 * \param v1 source vertex of the edge
1912 * \param v2 destination vertex of the edge
1913 */
1914 template<typename CheckPolicy = NoCheck> inline void add_edge(size_t v1, size_t v2)
1915 {
1916 //if the source vertex is not in this graph, this processor doesn't need to do anything
1917 if (!vertexIsInThisGraph(v1))
1918 {
1919 return;
1920 }
1921
1922 //if the destination vertex is not in this graph, this processor has to request it and add the edge to a queue
1923 if (!vertexIsInThisGraph(v2))
1924 {
1925 reqVertex(v2);
1926 EdgeReq er = { v1, v2, 0, 0 };
1927 e_queue.add(er);
1928
1929 return;
1930 }
1931
1932 // add an edge
1933 long int id_x_end = addEdge_<CheckPolicy>(glb2loc.at(v1), glb2id.at(v2));
1934
1935 // If there is not edge return an invalid edge, is a kind of stub object
1936 if (id_x_end == NO_EDGE)
1937 return;
1938
1939 // set source and destination ids of the edge
1940 e_m.get(id_x_end).template get<e_info::sgid>() = v1;
1941 e_m.get(id_x_end).template get<e_info::dgid>() = v2;
1942 }
1943
1944 /*! \brief Execute a synchronization through processor to finalize the add of the edges requested in the e_queue
1945 *
1946 */
1947 void syncEdge()
1948 {
1949 // retrieve ghosts necessary for edge adding
1950 sync();
1951
1952 // update with real values of edges, we don't add the edge here because it will modify edge's array length
1953 for (size_t i = 0; i < e_queue.size(); ++i)
1954 {
1955 e_queue.get(i).v1n = glb2loc.at(e_queue.get(i).v1);
1956 e_queue.get(i).v2n = glb2id.at(e_queue.get(i).v2);
1957 }
1958
1959 deleteGhosts();
1960
1961 for (auto req : e_queue)
1962 {
1963 // add an edge
1964 long int id_x_end = addEdge_<>(req.v1n, req.v2n);
1965
1966 // If there is not edge return an invalid edge, is a kind of stub object
1967 if (id_x_end == NO_EDGE)
1968 return;
1969
1970 // set source and destination ids of the edge
1971 e_m.get(id_x_end).template get<e_info::sgid>() = req.v1;
1972 e_m.get(id_x_end).template get<e_info::dgid>() = req.v2;
1973 }
1974
1975 e_queue.clear();
1976
1977 }
1978
1979 /*! \brief Swap the memory of g with this graph
1980 *
1981 * Swap the memory of g with this graph, it is basically used
1982 * for move semantic
1983 *
1984 * \param g The source graph
1985 */
1986 inline void swap(DistGraph_CSR<V, E> & g)
1987 {
1988 // switch the memory
1989 v.swap(g.v);
1990 v_m.swap(g.v_m);
1991 e.swap(g.e);
1992 e_m.swap(g.e_m);
1993 v_l.swap(g.v_l);
1994 glb2id.swap(g.glb2id);
1995 id2glb.swap(g.id2glb);
1996 glb2loc.swap(g.glb2loc);
1997 e_l.swap(g.e_l);
1998 e_invalid.swap(g.e_invalid);
1999 vtxdist.swap(g.vtxdist);
2000 fvtxdist.swap(g.fvtxdist);
2001
2002 size_t v_slot_tmp = v_slot;
2003 v_slot = g.v_slot;
2004 g.v_slot = v_slot_tmp;
2005 }
2006
2007 /*! \brief Swap the memory of g with this graph
2008 *
2009 * Swap the memory of g with this graph, it is basically used
2010 * for move semantic
2011 *
2012 * \param g The source graph
2013 */
2014 inline void swap(DistGraph_CSR<V, E> && g)
2015 {
2016 // switch the memory
2017 v.swap(g.v);
2018 v_m.swap(g.v_m);
2019 e.swap(g.e);
2020 e_m.swap(g.e_m);
2021 v_l.swap(g.v_l);
2022 glb2id.swap(g.glb2id);
2023 id2glb.swap(g.id2glb);
2024 glb2loc.swap(g.glb2loc);
2025 e_l.swap(g.e_l);
2026 e_invalid.swap(g.e_invalid);
2027 vtxdist.swap(g.vtxdist);
2028 fvtxdist.swap(g.fvtxdist);
2029
2030 size_t v_slot_tmp = v_slot;
2031 v_slot = g.v_slot;
2032 g.v_slot = v_slot_tmp;
2033 }
2034
2035 /*! \brief Get the vertex iterator
2036 *
2037 * Get the vertex iterator
2038 *
2039 * \return an iterator to iterate through all the vertex
2040 *
2041 */
2042 inline auto getVertexIterator() const -> decltype(v.getIterator())
2043 {
2044 return v.getIterator();
2045 }
2046
2047 /*! \brief Get the vertex iterator
2048 *
2049 * Get the vertex iterator
2050 *
2051 * \return an iterator to iterate through all the edges
2052 *
2053 */
2054 inline edge_iterator<DistGraph_CSR<V, E, Memory>> getEdgeIterator() const
2055 {
2056 return edge_iterator<DistGraph_CSR<V, E, Memory>>(*this);
2057 }
2058
2059 /*! \brief Return the number of the vertices in this subgraph
2060 *
2061 * \return the number of vertex
2062 *
2063 */
2064 inline size_t getNVertex() const
2065 {
2066 return v.size();
2067 }
2068
2069 /*! \brief Return the total number of the vertices
2070 *
2071 * \return the number of vertex
2072 *
2073 */
2074 inline size_t getTotNVertex() const
2075 {
2076 return vtxdist.get(vcl.getProcessingUnits());
2077 }
2078
2079 /*! \brief Return the number of edges
2080 *
2081 * \return the number of edges
2082 *
2083 */
2084 inline size_t getNEdge() const
2085 {
2086 return e.size();
2087 }
2088
2089 /*! \brief Once added all the vertices this function must be called to initialize all the properties, useless if a graph factory is used
2090 *
2091 */
2092 void init()
2093 {
2094 initDistributionVector();
2095
2096 initGlbimap();
2097
2098 remap();
2099 }
2100
2101 /*! \brief Check if a vertex is a ghost vertex (not belonging to this processor)
2102 *
2103 * \param id id of the vertex to check
2104 * \return true if it is a ghost vertex
2105 */
2106 bool isGhost(size_t id)
2107 {
2108 auto search = ghs_map.find(id);
2109
2110 if (search != ghs_map.end())
2111 {
2112 return true;
2113 }
2114 else
2115 {
2116 return false;
2117 }
2118 }
2119
2120 /*! \brief Remove all the ghosts from this graph
2121 *
2122 */
2123 void deleteGhosts()
2124 {
2125 if (ghs_map.size() == 0)
2126 return;
2127
2128 // Prepare new graph
2129 DistGraph_CSR recv_g;
2130
2131 size_t fpos = getNVertex() - ghs_map.size();
2132 size_t epos = 0;
2133
2134 // Reset global to local map
2135 for (auto gh : ghs_map)
2136 {
2137 epos += getNChilds(glb2loc.at(gh.first));
2138 id2glb.erase(glb2id.at(gh.first));
2139 glb2loc.erase(gh.first);
2140 glb2id.erase(gh.first);
2141
2142 }
2143
2144 //resize all structures to delete the ghosts
2145 v.resize(fpos);
2146 v_m.resize(fpos);
2147 v_l.resize(fpos);
2148 e.resize(e.size() - epos);
2149 e_m.resize(e_m.size() - epos);
2150 e_l.resize(fpos * v_slot);
2151
2152 // Clear ghosts map
2153 ghs_map.clear();
2154 }
2155
2156 /*! \brief Prepare to send vertex i from the local processor to the target processor
2157 *
2158 * \tparam toRemove if true the vertex will be deleted from this graph once it has been sent
2159 *
2160 * \param i vertex to send
2161 * \param t target processor
2162 */
2163 template<bool toRemove = true> //TODO make it private and create wrapper in public
2164 void q_move(size_t i, size_t t)
2165 {
2166 // Check if a 'useless' move has been requested
2167 if (t == vcl.getProcessUnitID())
2168 {
2169 std::cerr << "Warning: " << __FILE__ << ":" << __LINE__ << " target processor is equal the local processor\n";
2170 return;
2171 }
2172
2173 // If the array for t processor is empty, set it to not empty
2174 if (sgp.get(t).isEmpty)
2175 sgp.get(t).isEmpty = false;
2176
2177 // Add the vertex to the vertex send buffer
2178 sgp.get(t).send_v.add(vertex(i));
2179
2180 // Add the vertex to the vertex send buffer
2181 sgp.get(t).send_v_m.add(v_m.get(i));
2182
2183 // Add the info about the number of children
2184 sgp.get(t).send_es.add(getNChilds(i));
2185
2186 for (size_t s = 0; s < getNChilds(i); s++)
2187 {
2188 // Add edge value and object to the respective arrays
2189 sgp.get(t).send_e.add(getChildEdge(i, s));
2190 sgp.get(t).send_e_m.add(getChildInfo(i, s));
2191 sgp.get(t).send_el.add(getChild(i, s));
2192 }
2193
2194 // If the vertex has to be removed after the send add its index id to the v_td array
2195 if (toRemove)
2196 v_td.add(i);
2197 }
2198
2199 /*! \brief Check if the move queue is empty
2200 *
2201 * \return true if the move queue is empty
2202 */
2203 bool moveQueueIsEmpty()
2204 {
2205 size_t exs = 0;
2206 for (size_t i = 0; i < vcl.getProcessingUnits(); ++i)
2207 if (sgp.get(i).isEmpty)
2208 exs++;
2209
2210 if (exs == 0)
2211 return true;
2212
2213 return false;
2214 }
2215
2216 /*! \brief Redistribute function that wraps different stages of the redistribution
2217 *
2218 */
2219 void redistribute()
2220 {
2221 if (glbi_map.size() == 0)
2222 initGlbimap();
2223
2224 deleteGhosts();
2225
2226 exchangeVertices<false>();
2227
2228 updateVtxdist();
2229
2230 remap();
2231 }
2232
2233 /*! \brief Put a vertex request in queue
2234 *
2235 * \param gid global id of the vertex to request
2236 */
2237 void reqVertex(size_t gid)
2238 {
2239 // if not initialized, prepare vr_queue
2240 if (vr_queue.size() == 0)
2241 vr_queue.resize(vcl.getProcessingUnits());
2242
2243 if (!vertexIsInThisGraph(gid))
2244 {
2245 vr_queue.get(getInfoProc(gid)).add(gid);
2246 }
2247
2248 }
2249
2250 /*! \brief Execute all vertex requests and add them as ghosts inside this graph, they will be available until a redistribution is executed
2251 *
2252 */
2253 void sync()
2254 {
2255 // If not initialized, prepare global informations map
2256 if (glbi_map.size() == 0)
2257 initGlbimap();
2258
2259 // if not initialized, prepare vr_queue
2260 if (vr_queue.size() == 0) // TODO remove check on size
2261 vr_queue.resize(vcl.getProcessingUnits());
2262
2263 // Arrays that will contain temporary requests and responses during communications TODO move to global private and reset method
2264 openfpm::vector<openfpm::vector<size_t>> resp(vcl.getProcessingUnits());
2265 openfpm::vector<openfpm::vector<size_t>> reqs(vcl.getProcessingUnits());
2266
2267 // Prepare structures for communication
2268 openfpm::vector<size_t> prc;
2269 openfpm::vector<size_t> size;
2270 openfpm::vector<void *> ptr;
2271
2272 // Fill the structures for sendrecvMultipleMessagesNBX function
2273 fillSendRecvStructs<size_t>(vr_queue, prc, size, ptr);
2274
2275 // Send/receive requests for info about needed vertices
2276 vcl.sendrecvMultipleMessagesNBX(prc.size(), (size_t *)size.getPointer(), (size_t *)prc.getPointer(), (void **)ptr.getPointer(), on_receive, &resp, NONE);
2277
2278 // Prepare responses with the containing processors of requested vertices
2279 for (size_t i = 0; i < resp.size(); ++i)
2280 {
2281 reqs.get(i).clear();
2282
2283 for (size_t j = 0; j < resp.get(i).size(); ++j)
2284 {
2285 try
2286 {
2287 reqs.get(i).add(glbi_map.at(resp.get(i).get(j)).pid);
2288 } catch (const std::out_of_range& oor)
2289 {
2290 std::cout << resp.get(i).get(j) << " not found in global info map (proc: " << vcl.getProcessUnitID() << ")\n";
2291 }
2292 }
2293 }
2294
2295 // Fill the structures for sendrecvMultipleMessagesNBX function
2296 fillSendRecvStructs<size_t>(reqs, prc, size, ptr);
2297
2298 // Reset response array TODO clear and resize not needed
2299 resp.clear();
2300 resp.resize(vcl.getProcessingUnits());
2301
2302 // Send/receive responses with the containing processors of requested vertices
2303 vcl.sendrecvMultipleMessagesNBX(prc.size(), (size_t *)size.getPointer(), (size_t *)prc.getPointer(), (void **)ptr.getPointer(), on_receive, &resp, NONE);
2304
2305 // Clear requests array
2306 reqs.clear();
2307 reqs.resize(vcl.getProcessingUnits());
2308
2309 // Prepare vertices requests
2310 for (size_t i = 0; i < vcl.getProcessingUnits(); ++i)
2311 {
2312 // If the info has been retrieved from other processors take it from resp
2313 if (i != vcl.getProcessUnitID())
2314 {
2315 for (size_t j = 0; j < vr_queue.get(i).size(); ++j)
2316 {
2317 reqs.get(resp.get(i).get(j)).add(vr_queue.get(i).get(j));
2318 }
2319 }
2320 // Otherwise take it from the global info map of this processor
2321 else
2322 {
2323 for (size_t j = 0; j < vr_queue.get(i).size(); ++j)
2324 {
2325 reqs.get(glbi_map.at(vr_queue.get(i).get(j)).pid).add(vr_queue.get(i).get(j));
2326 }
2327 }
2328 }
2329
2330 // Fill the structures for sendrecvMultipleMessagesNBX function
2331 fillSendRecvStructs<size_t>(reqs, prc, size, ptr);
2332
2333 // Reset response array
2334 resp.clear();
2335 resp.resize(vcl.getProcessingUnits());
2336
2337 // Send/receive vertices requests
2338 vcl.sendrecvMultipleMessagesNBX(prc.size(), (size_t *)size.getPointer(), (size_t *)prc.getPointer(), (void **)ptr.getPointer(), on_receive, &resp, NONE);
2339
2340 for (size_t i = 0; i < resp.size(); ++i)
2341 {
2342 for (size_t j = 0; j < resp.get(i).size(); ++j)
2343 {
2344 try
2345 {
2346 q_move<false>(glb2loc.at(resp.get(i).get(j)), i);
2347 } catch (const std::out_of_range& oor)
2348 {
2349 std::cout << resp.get(i).get(j) << " not found in global to local map (proc: " << vcl.getProcessUnitID() << ")\n";
2350 }
2351 }
2352 }
2353
2354 // Send and receive vertices, the received ones will be added to the graph as ghosts
2355 exchangeVertices<true>();
2356
2357 // Empty the requests list
2358 vr_queue.clear();
2359 }
2360};
2361
2362/*! \brief Simplified implementation of DistGraph_CSR
2363 *
2364 * Used when DistGraph_CSR is used as a default template argument to avoid 7 arguments
2365 *
2366 * [Example]
2367 *
2368 * template<template<typename,typename> class T=DistGraph_CSR_s>
2369 * class cool_structure
2370 * {
2371 * T<Vertex,Edge> graph
2372 * }
2373 *
2374 * only 2 parameter are needed, if you use DistGraph_CSR you have to define 7 regardless that
2375 * DistGraph_CSR has some default template
2376 *
2377 * template<template<typename,typename> class T=DistGraph_CSR>
2378 * class cool_structure
2379 * {
2380 * T<Vertex,Edge> graph
2381 * }
2382 *
2383 * THIS DO NOT COMPILE
2384 *
2385 */
2386template<typename V, typename E>
2387class DistGraph_CSR_s: public DistGraph_CSR<V, E>
2388{
2389
2390};
2391
2392#endif /* DIST_MAP_GRAPH_HPP_ */
2393