1/*
2 * DistGraphFactory.hpp
3 *
4 * Created on: Dec 03, 2015
5 * Author: Antonio Leo
6 */
7
8#ifndef DISTGRAPHFACTORYOLD_HPP_
9#define DISTGRAPHFACTORYOLD_HPP_
10
11#include "VCluster/VCluster.hpp"
12#include "Vector/map_vector.hpp"
13#include "Graph/map_graph.hpp"
14#include "Grid/grid_sm.hpp"
15#include "Space/Shape/Box.hpp"
16#include "Space/Shape/HyperCube.hpp"
17#include "parmetis.h"
18
19/*! \brief This class work as a functor
20 *
21 * For each number in the boost::mpl::vector (for example 3 6) set the properties of the vertex at the
22 * specified id (3 6) with pos[d] * spacing[d] with d running from 0 to 1, pos[d] the position id of the vertex
23 * spacing the grid spacing
24 *
25 * Example
26 *
27 * if we give a grid_key of dimension 2 4x4 the expression "pos[d] * spacing[d]"
28 * will assume the value
29 *
30 * (0.0 0.0) (0.25 0.0) ...... (1.0 0.0)
31 * (0.0 0.25)................. (1.0 0.25)
32 * ....................................
33 * (0.0 1.0).................. (1.0 1.0)
34 *
35 * and the properties 3 6 will be filled with the numbers 0.0 0.0 ....... 1.0 1.0
36 * progressively
37 *
38 * \tparam dim Dimensionality of the cartesian grid
39 * \tparam dT type of the domain
40 * \tparam G_v vertex type object
41 * \tparam v boost::mpl::vector containing all the index to fill
42 * \tparam is_stub when is true, produce a trivial operator(),
43 * to use when v is an empty vector to avoid compilation error
44 *
45 */
46
47template<unsigned int dim, typename dT, typename G_v, typename v, int impl>
48class fill_prop_v
49{
50 //! Reference to an array containing the spacing
51 const dT (&szd)[dim];
52
53 //! grid_key_dx Reference containing the actual position
54 grid_key_dx<dim> & gk;
55
56 //! Vertex object to fill
57 G_v & g_v;
58
59 //! grid info
60 const grid_sm<dim, void> & gs;
61
62public:
63
64 //! Fill the object from where to take the properties
65 fill_prop_v(G_v & g_v, const dT (&szd)[dim], grid_key_dx<dim> & gk, const grid_sm<dim, void> & gs) :
66 szd(szd), gk(gk), g_v(g_v), gs(gs)
67 {
68 }
69
70 //! It call the function for each property we want to copy
71 template<typename T>
72 void operator()(T& t) const
73 {
74 typedef typename boost::fusion::result_of::at<v, boost::mpl::int_<T::value>>::type t_val;
75
76 g_v.template get<t_val::value>() = gk.get(T::value) * szd[T::value];
77 }
78};
79
80
81/*! \brief This class work as a functor
82 *
83 * For each number in the boost::mpl::vector (for example 3 6) set the properties of the vertex at the
84 * specified id (3 6) with pos[d] * spacing[d] with d running from 0 to 1, pos[d] the position id of the vertex
85 * spacing the grid spacing
86 *
87 * Example
88 *
89 * if we give a grid_key of dimension 2 4x4 the expression "pos[d] * spacing[d]"
90 * will assume the value
91 *
92 * (0.0 0.0) (0.25 0.0) ...... (1.0 0.0)
93 * (0.0 0.25)................. (1.0 0.25)
94 * ....................................
95 * (0.0 1.0).................. (1.0 1.0)
96 *
97 * and the properties 3 6 will be filled with the numbers 0.0 0.0 ....... 1.0 1.0
98 * progressively
99 *
100 * \tparam dim Dimensionality of the cartesian grid
101 * \tparam dT type of the domain
102 * \tparam G_v vertex type object
103 * \tparam v boost::mpl::vector containing all the index to fill
104 *
105 */
106
107template<unsigned int dim, typename dT, typename G_v, typename v>
108class fill_prop_v<dim, dT, G_v, v, 0>
109{
110
111public:
112
113 //! Fill the object from where to take the properties
114 fill_prop_v(G_v & g_v, const dT (&szd)[dim], grid_key_dx<dim> & gk, const grid_sm<dim, void> & gs)
115 {
116 }
117
118 //! It call the function for each property we want to copy
119 template<typename T>
120 void operator()(T& t) const
121 {
122 }
123};
124
125/*! \brief This class work as a functor
126 *
127 * For each number in the boost::mpl::vector (for example 3 6) set the properties of the vertex at the
128 * specified id (3 6) with pos[d] * spacing[d] with d running from 0 to 1, pos[d] the position id of the vertex
129 * spacing the grid spacing
130 *
131 * Example
132 *
133 * if we give a grid_key of dimension 2 4x4 the expression "pos[d] * spacing[d]"
134 * will assume the value
135 *
136 * (0.0 0.0) (0.25 0.0) ...... (1.0 0.0)
137 * (0.0 0.25)................. (1.0 0.25)
138 * ....................................
139 * (0.0 1.0).................. (1.0 1.0)
140 *
141 * and the properties 3 6 will be filled with the numbers 0.0 0.0 ....... 1.0 1.0
142 * progressively
143 *
144 * \tparam dim Dimensionality of the cartesian grid
145 * \tparam dT type of the domain
146 * \tparam G_v vertex type object
147 * \tparam v boost::mpl::vector containing all the index to fill
148 *
149 */
150
151template<unsigned int dim, typename dT, typename G_v, typename v>
152class fill_prop_v<dim, dT, G_v, v, 2>
153{
154
155 //! Reference to an array containing the spacing
156 const dT (&szd)[dim];
157
158 //! grid_key_dx Reference containing the actual position
159 grid_key_dx<dim> & gk;
160
161 //! Vertex object to fill
162 G_v & g_v;
163
164 //! grid info
165 const grid_sm<dim, void> & gs;
166
167public:
168
169 //! Fill the object from where to take the properties
170 fill_prop_v(G_v & g_v, const dT (&szd)[dim], grid_key_dx<dim> & gk, const grid_sm<dim, void> & gs)
171 :szd(szd), gk(gk), g_v(g_v), gs(gs)
172 {
173 }
174
175 //! It call the function for each property we want to copy
176 template<typename T>
177 void operator()(T& t) const
178 {
179 typedef typename boost::fusion::result_of::at<v, boost::mpl::int_<0>>::type t_val;
180 typedef typename boost::mpl::at<typename G_v::T_type::type,t_val>::type s_type;
181
182 for (size_t i = 0 ; i < std::extent<s_type>::value ; i++)
183 g_v.template get<t_val::value>()[i] = 0.0;
184
185 for (size_t i = 0 ; i < dim ; i++)
186 g_v.template get<t_val::value>()[i] = gk.get(i) * static_cast<float>(szd[i]);
187 }
188};
189
190/*! \brief Operator for vector and scalar property
191 *
192 * \tparam i Size of the property
193 * \tparam p Type of the property
194 * \tparam Graph Graph
195 * \tparam pos Array of properties
196 */
197template<int i, typename p, typename Graph, int ... pos>
198struct fill_prop_v_by_type
199{
200
201 typedef typename boost::mpl::at<p, boost::mpl::int_<0>>::type v_element;
202 typedef typename boost::mpl::at<typename Graph::V_type::type, v_element>::type pos_prop_type;
203
204 enum
205 {
206 value = ((sizeof...(pos) != 0) * (std::is_array<pos_prop_type>::value + 1))
207 };
208
209};
210
211/*! \brief Operator for vector and scalar property in the case there are no properties
212 *
213 * \tparam i Size of the property
214 * \tparam p Type of the property
215 * \tparam Graph Graph
216 * \tparam pos Array of properties
217 */
218template<typename p, typename Graph, int ... pos>
219struct fill_prop_v_by_type<0, p, Graph, pos...>
220{
221 enum
222 {
223 value = 0
224 };
225
226};
227
228/*! \brief Graph constructor function specialization
229 *
230 * On C++ partial function specialization is not allowed, so we need a class to do it
231 *
232 * \see CartesianGraphFactory method construct
233 *
234 */
235
236template<unsigned int dim, typename Graph, int se, typename T, unsigned int dim_c, int ... pos>
237class DistGraph_constr_impl
238{
239public:
240 //! Construct Cartesian graph
241 static Graph construct(const size_t (&sz)[dim], Box<dim, T> dom)
242 {
243 Vcluster<> &v_cl = create_vcluster();
244
245 // Calculate the size of the hyper-cubes on each dimension
246 T szd[dim];
247
248 for (size_t i = 0; i < dim; i++)
249 {
250 szd[i] = (dom.getHigh(i) - dom.getLow(i)) / sz[i];
251 }
252
253 //! Construct an hyper-cube of dimension dim
254
255 HyperCube<dim> hc;
256
257 // Construct a grid info
258
259 grid_sm<dim, void> g(sz);
260
261 //! Get the processor id
262 size_t p_id = v_cl.getProcessUnitID();
263
264 //! Get the number of processing units
265 size_t Np = v_cl.getProcessingUnits();
266
267 //! Division of vertices in Np graphs
268 //! Put (div+1) vertices in mod graphs
269 //! Put div vertices in the rest of the graphs
270 size_t mod_v = g.size() % Np;
271 size_t div_v = g.size() / Np;
272
273 //! Distribution vector
274 openfpm::vector<idx_t> vtxdist(v_cl.getProcessingUnits() + 1);
275
276 for (int i = 0; i <= Np; i++)
277 {
278 if (i < mod_v)
279 vtxdist.get(i) = (div_v + 1) * (i);
280 else
281 vtxdist.get(i) = (div_v) * (i) + mod_v;
282 }
283
284 //! Get size of this processor graph
285 size_t gp_size = vtxdist.get(p_id + 1) - vtxdist.get(p_id);
286
287 //! Graph to construct
288 Graph gp(gp_size);
289
290 //! Store the decomposition vector inside the distributed graph
291 gp.initDistributionVector(vtxdist);
292
293 /******************
294 *
295 * Create the edges and fill spatial
296 * information properties
297 *
298 ******************/
299
300 //! Construct a key iterator
301 grid_key_dx_iterator<dim> k_it(g);
302
303 //! Local iterator of the graph
304 size_t local_it = 0;
305
306 //! Iterate through all the elements
307
308 while (k_it.isNext())
309 {
310 size_t v_id = g.LinId(k_it.get());
311
312 if (v_id < vtxdist.get(p_id + 1) && v_id >= vtxdist.get(p_id))
313 {
314
315 grid_key_dx<dim> key = k_it.get();
316
317 // Vertex object
318
319 auto obj = gp.vertex(local_it);
320
321 typedef typename to_boost_vmpl<pos...>::type p;
322
323 // vertex spatial properties functor
324
325 fill_prop_v<dim, T, decltype(gp.vertex(local_it)), typename to_boost_vmpl<pos...>::type, fill_prop_v_by_type<sizeof...(pos), p, Graph, pos...>::value> flp(obj, szd, key, g);
326
327 // fill properties
328
329 boost::mpl::for_each<boost::mpl::range_c<int, 0, sizeof...(pos)> >(flp);
330
331 // set map global to local in the graph, needed because vertex is already created without addVertex method
332
333 gp.setGlobalMap(v_id, local_it, v_id);
334
335 // Get the combinations of dimension d
336
337 for (size_t d = dim - 1; d >= dim_c; d--)
338 {
339 // create the edges for that dimension
340
341 std::vector<comb<dim>> c = hc.getCombinations_R(d);
342
343 // for each combination calculate a safe linearization and create an edge
344
345 for (size_t j = 0; j < c.size(); j++)
346 {
347 // Calculate the element size
348
349 T ele_sz = 0;
350
351 // for each dimension multiply and reduce
352
353 for (size_t s = 0; s < dim; s++)
354 {
355 ele_sz += szd[s] * abs(c[j][s]);
356 }
357
358 // Calculate the end point vertex id
359 // Calculate the start point id
360
361 size_t start_v = local_it;
362 size_t end_v = g.template LinId<CheckExistence>(key, c[j].getComb());
363
364 // check if the end_v is valid globally
365 if (end_v < g.size())
366 {
367 // Add an edge and set the the edge property to the size of the face (communication weight)
368 gp.template addEdge<NoCheck>(start_v, end_v).template get<se>() = ele_sz;
369 }
370 }
371 }
372 ++local_it;
373 }
374 ++k_it;
375 }
376
377 return gp;
378 }
379};
380
381/*! \brief Graph constructor function specialization
382 *
383 * On C++ partial function specialization is not allowed, so we need a class to do it
384 * This specialization handle the case when we have NO_EDGE option active
385 *
386 * \see CartesianGraphFactory method construct
387 *
388 */
389
390template<unsigned int dim, typename Graph, typename T, unsigned int dim_c, int ... pos>
391class DistGraph_constr_impl<dim, Graph, NO_EDGE, T, dim_c, pos...>
392{
393public:
394 //! Construct Cartesian graph
395 static Graph construct(const size_t (&sz)[dim], Box<dim, T> dom)
396 {
397 Vcluster<> &v_cl = create_vcluster();
398
399 // Calculate the size of the hyper-cubes on each dimension
400
401 T szd[dim];
402
403 for (size_t i = 0; i < dim; i++)
404 {
405 szd[i] = (dom.getHigh(i) - dom.getLow(i)) / sz[i];
406 }
407
408 //! Construct an hyper-cube of dimension dim
409
410 HyperCube<dim> hc;
411
412 // Construct a grid info
413
414 grid_sm<dim, void> g(sz);
415
416 //! Get the processor id
417 size_t p_id = v_cl.getProcessUnitID();
418
419 //! Get the number of processing units
420 size_t Np = v_cl.getProcessingUnits();
421
422 //! Division of vertices in Np graphs
423 //! Put (div+1) vertices in mod graphs
424 //! Put div vertices in the rest of the graphs
425 size_t mod_v = g.size() % Np;
426 size_t div_v = g.size() / Np;
427
428 //! Distribution vector
429 openfpm::vector<idx_t> vtxdist(v_cl.getProcessingUnits() + 1);
430
431 for (size_t i = 0; i <= Np; i++)
432 {
433 if (i < mod_v)
434 vtxdist.get(i) = (div_v + 1) * (i);
435 else
436 vtxdist.get(i) = (div_v) * (i) + mod_v;
437 }
438
439 size_t gp_size = vtxdist.get(p_id + 1) - vtxdist.get(p_id);
440
441 //! Graph to construct
442 Graph gp(gp_size);
443
444 //! Store the decomposition vector inside the distributed graph
445 gp.initDistributionVector(vtxdist);
446
447 /******************
448 *
449 * Create the edges and fill spatial
450 * information properties
451 *
452 ******************/
453
454 //! Construct a key iterator
455 grid_key_dx_iterator<dim> k_it(g);
456
457 //! Local iterator of the graph
458 size_t local_it = 0;
459
460 //! Iterate through all the elements
461
462 while (k_it.isNext())
463 {
464 size_t v_id = g.LinId(k_it.get());
465
466 if (v_id < (size_t)vtxdist.get(p_id + 1) && v_id >= (size_t)vtxdist.get(p_id))
467 {
468 grid_key_dx<dim> key = k_it.get();
469
470 // Vertex object
471 auto obj = gp.vertex(local_it);
472
473 typedef typename to_boost_vmpl<pos...>::type p;
474
475 // vertex spatial properties functor
476
477 fill_prop_v<dim, T, decltype(gp.vertex(local_it)), typename to_boost_vmpl<pos...>::type, fill_prop_v_by_type<sizeof...(pos), p, Graph, pos...>::value> flp(obj, szd, key, g);
478
479 // fill properties
480
481 boost::mpl::for_each<boost::mpl::range_c<int, 0, sizeof...(pos)> >(flp);
482
483 // set map global to local in the graph, needed because vertex is already created without addVertex method
484
485 gp.setGlobalMap(v_id, local_it, v_id);
486
487 // Get the combinations of dimension d
488
489 for (size_t d = dim - 1; d >= dim_c; d--)
490 {
491 // create the edges for that dimension
492
493 std::vector<comb<dim>> c = hc.getCombinations_R(d);
494
495 // for each combination calculate a safe linearization and create an edge
496
497 for (size_t j = 0; j < c.size(); j++)
498 {
499 // Calculate the element size
500
501 T ele_sz = 0;
502
503 // for each dimension multiply and reduce
504
505 for (size_t s = 0; s < dim; s++)
506 {
507 ele_sz += szd[s] * abs(c[j][s]);
508 }
509
510 // Calculate the end point vertex id
511 // Calculate the start point id
512
513 size_t start_v = local_it;
514 size_t end_v = g.template LinId<CheckExistence>(key, c[j].getComb());
515
516 // check if the end_v is valid globally
517 if (end_v < g.size())
518 {
519 // Add an edge and set the the edge property to the size of the face (communication weight)
520 gp.addEdge(start_v, end_v, v_id, end_v);
521 }
522 }
523 }
524 ++local_it;
525 }
526 ++k_it;
527 }
528 return gp;
529 }
530};
531
532/*! \brief This class construct a cartesian graph
533 *
534 * This class construct a cartesian graph
535 *
536 * \param dim dimensionality of the cartesian grid
537 *
538 */
539
540template<unsigned int dim, typename Graph>
541class DistGraphFactory
542{
543
544public:
545
546 /*! \brief Construct a cartesian graph, with V and E edge properties
547 *
548 * Each vertex is a subspace (Hyper-cube) of dimension dim, each vertex is
549 * connected with an edge if two vertex (Hyper-cube) share a element of dimension grater than
550 * dim_c. One property can be used to store the contact size or the d-dimensional
551 * surface in common between two connected hyper-cube.
552 *
553 * \param sz Vector that store the size of the grid on each dimension
554 * \param dom Box enclosing the physical domain
555 *
556 * \tparam se Indicate which properties fill with the contact size. The
557 * contact size is the point, line , surface, d-dimensional object size
558 * in contact (in common) between two hyper-cube. NO_EDGE indicate
559 * no property will store this information
560 * \tparam T type of the domain like (int real complex ... )
561 * \tparam dim_c Connectivity dimension
562 * \tparam pos... (optional)one or more integer indicating the spatial properties
563 *
564 */
565 template<int se, typename T, unsigned int dim_c, int ... pos>
566 static Graph construct(const size_t (&sz)[dim], Box<dim, T> dom)
567 {
568 return DistGraph_constr_impl<dim, Graph, se, T, dim_c, pos...>::construct(sz, dom);
569 }
570};
571
572#endif /* DISTGRAPHFACTORY_HPP_ */
573