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 | |
72 | template<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> |
79 | class DistGraph_CSR; |
80 | |
81 | class v_info |
82 | { |
83 | public: |
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 | |
135 | class e_info |
136 | { |
137 | public: |
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 | |
202 | template<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> |
209 | class 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 | |
995 | public: |
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 | */ |
2386 | template<typename V, typename E> |
2387 | class DistGraph_CSR_s: public DistGraph_CSR<V, E> |
2388 | { |
2389 | |
2390 | }; |
2391 | |
2392 | #endif /* DIST_MAP_GRAPH_HPP_ */ |
2393 | |