Zoltan2
Loading...
Searching...
No Matches
Zoltan2_AlgPuLP.hpp
Go to the documentation of this file.
1// @HEADER
2//
3// ***********************************************************************
4//
5// Zoltan2: A package of combinatorial algorithms for scientific computing
6// Copyright 2012 Sandia Corporation
7//
8// Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
9// the U.S. Government retains certain rights in this software.
10//
11// Redistribution and use in source and binary forms, with or without
12// modification, are permitted provided that the following conditions are
13// met:
14//
15// 1. Redistributions of source code must retain the above copyright
16// notice, this list of conditions and the following disclaimer.
17//
18// 2. Redistributions in binary form must reproduce the above copyright
19// notice, this list of conditions and the following disclaimer in the
20// documentation and/or other materials provided with the distribution.
21//
22// 3. Neither the name of the Corporation nor the names of the
23// contributors may be used to endorse or promote products derived from
24// this software without specific prior written permission.
25//
26// THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
27// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
29// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
30// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
31// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
32// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
33// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
34// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
35// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
36// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
37//
38// Questions? Contact Karen Devine (kddevin@sandia.gov)
39// Erik Boman (egboman@sandia.gov)
40// Siva Rajamanickam (srajama@sandia.gov)
41//
42// ***********************************************************************
43//
44// @HEADER
45#ifndef _ZOLTAN2_ALGPULP_HPP_
46#define _ZOLTAN2_ALGPULP_HPP_
47
49#include <Zoltan2_Algorithm.hpp>
51#include <Zoltan2_Util.hpp>
52#include <Zoltan2_TPLTraits.hpp>
53
57
59#ifndef HAVE_ZOLTAN2_PULP
60
61namespace Zoltan2 {
62// Error handling for when PuLP is requested
63// but Zoltan2 not built with PuLP.
64
65template <typename Adapter>
66class AlgPuLP : public Algorithm<Adapter>
67{
68public:
69 typedef typename Adapter::base_adapter_t base_adapter_t;
70 AlgPuLP(const RCP<const Environment> &/* env */,
71 const RCP<const Comm<int> > &/* problemComm */,
72 const RCP<const base_adapter_t> &/* adapter */
73 )
74 {
75 throw std::runtime_error(
76 "BUILD ERROR: PuLP requested but not compiled into Zoltan2.\n"
77 "Please set CMake flag TPL_ENABLE_PuLP:BOOL=ON.");
78 }
79
82 static void getValidParameters(ParameterList & /* pl */)
83 {
84 // No parameters needed in this error-handling version of AlgPuLP
85 }
86};
87
88}
89#endif
90
93
94#ifdef HAVE_ZOLTAN2_PULP
95
96namespace Zoltan2 {
97
98extern "C" {
99// TODO: XtraPuLP
100#ifndef HAVE_ZOLTAN2_MPI
101#include "pulp.h"
102#else
103#include "xtrapulp.h"
104#endif
105}
106
107
108template <typename Adapter>
109class AlgPuLP : public Algorithm<Adapter>
110{
111public:
112 typedef typename Adapter::base_adapter_t base_adapter_t;
113 typedef typename Adapter::lno_t lno_t;
114 typedef typename Adapter::gno_t gno_t;
115 typedef typename Adapter::offset_t offset_t;
116 typedef typename Adapter::scalar_t scalar_t;
117 typedef typename Adapter::part_t part_t;
118 typedef typename Adapter::user_t user_t;
119 typedef typename Adapter::userCoord_t userCoord_t;
120
131 AlgPuLP(const RCP<const Environment> &env__,
132 const RCP<const Comm<int> > &problemComm__,
133 const RCP<const IdentifierAdapter<user_t> > &adapter__) :
134 env(env__), problemComm(problemComm__), adapter(adapter__)
135 {
136 std::string errStr = "cannot build GraphModel from IdentifierAdapter, ";
137 errStr += "PuLP requires Graph, Matrix, or Mesh Adapter";
138 throw std::runtime_error(errStr);
139 }
140
141 AlgPuLP(const RCP<const Environment> &env__,
142 const RCP<const Comm<int> > &problemComm__,
143 const RCP<const VectorAdapter<user_t> > &adapter__) :
144 env(env__), problemComm(problemComm__), adapter(adapter__)
145 {
146 std::string errStr = "cannot build GraphModel from VectorAdapter, ";
147 errStr += "PuLP requires Graph, Matrix, or Mesh Adapter";
148 throw std::runtime_error(errStr);
149 }
150
151 AlgPuLP(const RCP<const Environment> &env__,
152 const RCP<const Comm<int> > &problemComm__,
153 const RCP<const GraphAdapter<user_t,userCoord_t> > &adapter__) :
154 env(env__), problemComm(problemComm__), adapter(adapter__)
155 {
156 modelFlag_t flags;
157 flags.reset();
158
159 buildModel(flags);
160 }
161
162 AlgPuLP(const RCP<const Environment> &env__,
163 const RCP<const Comm<int> > &problemComm__,
164 const RCP<const MatrixAdapter<user_t,userCoord_t> > &adapter__) :
165 env(env__), problemComm(problemComm__), adapter(adapter__)
166 {
167 modelFlag_t flags;
168 flags.reset();
169
170 const ParameterList &pl = env->getParameters();
171 const Teuchos::ParameterEntry *pe;
172
173 std::string defString("default");
174 std::string objectOfInterest(defString);
175 pe = pl.getEntryPtr("objects_to_partition");
176 if (pe)
177 objectOfInterest = pe->getValue<std::string>(&objectOfInterest);
178
179 if (objectOfInterest == defString ||
180 objectOfInterest == std::string("matrix_rows") )
181 flags.set(VERTICES_ARE_MATRIX_ROWS);
182 else if (objectOfInterest == std::string("matrix_columns"))
184 else if (objectOfInterest == std::string("matrix_nonzeros"))
186
187 buildModel(flags);
188 }
189
190 AlgPuLP(const RCP<const Environment> &env__,
191 const RCP<const Comm<int> > &problemComm__,
192 const RCP<const MeshAdapter<user_t> > &adapter__) :
193 env(env__), problemComm(problemComm__), adapter(adapter__)
194 {
195 modelFlag_t flags;
196 flags.reset();
197
198 const ParameterList &pl = env->getParameters();
199 const Teuchos::ParameterEntry *pe;
200
201 std::string defString("default");
202 std::string objectOfInterest(defString);
203 pe = pl.getEntryPtr("objects_to_partition");
204 if (pe)
205 objectOfInterest = pe->getValue<std::string>(&objectOfInterest);
206
207 if (objectOfInterest == defString ||
208 objectOfInterest == std::string("mesh_nodes") )
209 flags.set(VERTICES_ARE_MESH_NODES);
210 else if (objectOfInterest == std::string("mesh_elements"))
212
213 buildModel(flags);
214 }
215
218 static void getValidParameters(ParameterList & pl)
219 {
220 pl.set("pulp_vert_imbalance", 1.1, "vertex imbalance tolerance, ratio of "
221 "maximum load over average load",
223
224 pl.set("pulp_edge_imbalance", 1.1, "edge imbalance tolerance, ratio of "
225 "maximum load over average load",
227
228 pl.set("pulp_imbalance", 1.1, "multiweight imbalance tolerance, ratio of "
229 "maximum load over average load",
231
232 // bool parameter
233 pl.set("pulp_lp_init", false, "perform label propagation-based "
234 "initialization", Environment::getBoolValidator() );
235
236 // bool parameter
237 pl.set("pulp_minimize_maxcut", false, "perform per-part max cut "
238 "minimization", Environment::getBoolValidator() );
239
240 // bool parameter
241 pl.set("pulp_verbose", false, "verbose output",
243
244 // bool parameter
245 pl.set("pulp_do_repart", false, "perform repartitioning",
247
248 pl.set("pulp_seed", 0, "set pulp seed", Environment::getAnyIntValidator());
249 }
250
251 void partition(const RCP<PartitioningSolution<Adapter> > &solution);
252
253private:
254
255 void buildModel(modelFlag_t &flags);
256
257 int* scale_weights( size_t n, int nWgt,
258 ArrayView<StridedData<lno_t, scalar_t> > fwgts);
259
260 const RCP<const Environment> env;
261 const RCP<const Comm<int> > problemComm;
262 const RCP<const base_adapter_t> adapter;
263 RCP<const GraphModel<base_adapter_t> > model;
264};
265
266
268template <typename Adapter>
269void AlgPuLP<Adapter>::buildModel(modelFlag_t &flags)
270{
271 const ParameterList &pl = env->getParameters();
272 const Teuchos::ParameterEntry *pe;
273
274 std::string defString("default");
275 std::string symParameter(defString);
276 pe = pl.getEntryPtr("symmetrize_graph");
277 if (pe){
278 symParameter = pe->getValue<std::string>(&symParameter);
279 if (symParameter == std::string("transpose"))
281 else if (symParameter == std::string("bipartite"))
282 flags.set(SYMMETRIZE_INPUT_BIPARTITE); }
283
284 bool sgParameter = false;
285 pe = pl.getEntryPtr("subset_graph");
286 if (pe)
287 sgParameter = pe->getValue(&sgParameter);
288 if (sgParameter)
289 flags.set(BUILD_SUBSET_GRAPH);
290
291 flags.set(REMOVE_SELF_EDGES);
292 flags.set(GENERATE_CONSECUTIVE_IDS);
293#ifndef HAVE_ZOLTAN2_MPI
294 flags.set(BUILD_LOCAL_GRAPH);
295#endif
296 this->env->debug(DETAILED_STATUS, " building graph model");
297 this->model = rcp(new GraphModel<base_adapter_t>(this->adapter, this->env,
298 this->problemComm, flags));
299 this->env->debug(DETAILED_STATUS, " graph model built");
300}
301
302/*
303NOTE:
304 Assumes installed PuLP library is version pulp-0.2
305 Assumes installed XtraPuLP library is version xtrapulp-0.3
306*/
307template <typename Adapter>
309 const RCP<PartitioningSolution<Adapter> > &solution
310)
311{
312 HELLO;
313
314 size_t numGlobalParts = solution->getTargetGlobalNumberOfParts();
315
316 int num_parts = (int)numGlobalParts;
317 //TPL_Traits<int, size_t>::ASSIGN(num_parts, numGlobalParts, env);
318
319 //#ifdef HAVE_ZOLTAN2_MPI
320 // TODO: XtraPuLP
321
322 int ierr = 0;
323 int np = problemComm->getSize();
324
325 // Get number of vertices and edges
326 const size_t modelVerts = model->getLocalNumVertices();
327 const size_t modelEdges = model->getLocalNumEdges();
328 int num_verts = (int)modelVerts;
329 long num_edges = (long)modelEdges;
330 //TPL_Traits<int, size_t>::ASSIGN(num_verts, modelVerts, env);
331 //TPL_Traits<long, size_t>::ASSIGN(num_edges, modelEdges, env);
332
333 // Get vertex info
334 ArrayView<const gno_t> vtxIDs;
335 ArrayView<StridedData<lno_t, scalar_t> > vwgts;
336 size_t nVtx = model->getVertexList(vtxIDs, vwgts);
337 int nVwgts = model->getNumWeightsPerVertex();
338
339
340#ifndef HAVE_ZOLTAN2_MPI
341 // PuLP current only supports a single vertex weight
342 if (nVwgts > 1) {
343 std::cerr << "Warning: NumWeightsPerVertex is " << nVwgts
344 << " but PuLP allows only one weight. "
345 << " Zoltan2 will use only the first weight per vertex."
346 << std::endl;
347 }
348
349 std::unique_ptr<int[]> vertex_weights;
350 long vertex_weights_sum = 0;
351 if (nVwgts) {
352 nVwgts = 1;
353 vertex_weights = std::unique_ptr<int[]>(scale_weights(nVtx, nVwgts, vwgts));
354
355 for (int i = 0; i < num_verts; ++i)
356 vertex_weights_sum += (long)vertex_weights[i];
357 } else {
358 vertex_weights = std::unique_ptr<int[]>(nullptr);
359 }
360#else
361 // XtraPuLP supports an arbitrary number of vertex weights
362 std::unique_ptr<int[]> vertex_weights;
363 if (nVwgts) {
364 vertex_weights = std::unique_ptr<int[]>(scale_weights(nVtx, nVwgts, vwgts));
365 } else {
366 vertex_weights = std::unique_ptr<int[]>(nullptr);
367 }
368#endif
369
370 // Get edge info
371 ArrayView<const gno_t> adjs;
372 ArrayView<const offset_t> offsets;
373 ArrayView<StridedData<lno_t, scalar_t> > ewgts;
374 size_t nEdge = model->getEdgeList(adjs, offsets, ewgts);
375 int nEwgts = model->getNumWeightsPerEdge();
376 if (nEwgts > 1) {
377 std::cerr << "Warning: NumWeightsPerEdge is " << nEwgts
378 << " but PuLP/XtraPuLP allows only one weight. "
379 << " Zoltan2 will use only the first weight per edge."
380 << std::endl;
381 }
382
383 std::unique_ptr<int[]> edge_weights;
384 if (nEwgts) {
385 nEwgts = 1;
386 edge_weights = std::unique_ptr<int[]>(scale_weights(nEdge, nEwgts, ewgts));
387 if (!nVwgts) {
388 // For XtraPulp, we need to fill vertex_weights array if we have
389 // any edge weights.
390 vertex_weights = std::unique_ptr<int[]>(new int[nVtx]);
391 nVwgts = 1;
392 for (size_t i = 0; i < nVtx; ++i) {
393 vertex_weights[i] = 1;
394 }
395 }
396 } else if (nVwgts) {
397 // For XtraPulp, we need to fill edge_weights array if we have
398 // any vertex weights.
399 edge_weights = std::unique_ptr<int[]>(new int[nEdge]);
400 for (size_t i = 0; i < nEdge; ++i) {
401 edge_weights[i] = 1;
402 }
403 } else {
404 edge_weights = std::unique_ptr<int[]>(nullptr);
405 }
406
407#ifndef HAVE_ZOLTAN2_MPI
408 // Create PuLP's graph structure
409 int* out_edges = nullptr;
410 long* out_offsets = nullptr;
413
414 pulp_graph_t g = {num_verts, num_edges,
415 out_edges, out_offsets,
416 vertex_weights.get(), edge_weights.get(),
417 vertex_weights_sum};
418
419#else
420 // Create XtraPuLP's graph structure
421 unsigned long* out_edges = nullptr;
422 unsigned long* out_offsets = nullptr;
425
426 const size_t modelVertsGlobal = model->getGlobalNumVertices();
427 const size_t modelEdgesGlobal = model->getGlobalNumEdges();
428 unsigned long num_verts_global = (unsigned long)modelVertsGlobal;
429 unsigned long num_edges_global = (unsigned long)modelEdgesGlobal;
430
431 unsigned long* global_ids = nullptr;
433
434 ArrayView<size_t> vtxDist;
435 model->getVertexDist(vtxDist);
436 unsigned long* verts_per_rank = new unsigned long[np+1];
437 for (int i = 0; i < np+1; ++i)
438 verts_per_rank[i] = vtxDist[i];
439
440 dist_graph_t g;
441 create_xtrapulp_dist_graph(&g, num_verts_global, num_edges_global,
442 (unsigned long)num_verts, (unsigned long)num_edges,
443 out_edges, out_offsets, global_ids, verts_per_rank,
444 nVwgts, vertex_weights.get(), edge_weights.get());
445#endif
446
447
448 // Create array for PuLP to return results in.
449 // Or write directly into solution parts array
450 ArrayRCP<part_t> partList(new part_t[num_verts], 0, num_verts, true);
451 int* parts = nullptr;
452 if (num_verts && (sizeof(int) == sizeof(part_t))) {
453 // Can write directly into the solution's memory
454 parts = (int *)partList.getRawPtr();
455 }
456 else {
457 // Can't use solution memory directly; will have to copy later.
458 parts = new int[num_verts];
459 }
460
461 // TODO
462 // Implement target part sizes
463
464 // Grab options from parameter list
465 const Teuchos::ParameterList &pl = env->getParameters();
466 const Teuchos::ParameterEntry *pe;
467
468 // figure out which parts of the algorithm we're going to run
469 // Default to PuLP with BFS init
470 // PuLP - do_edge_min = false, do_maxcut_min = false
471 // PuLP-M - do_edge_bal = true, do_maxcut_min = false
472 // PuLP-MM - do_edge_bal = true/false, do_maxcut_min = true
473 // PuLP-MC - do_edge_bal = false, do_maxcut_min = true/false
474 bool do_lp_init = false;
475 bool do_bfs_init = true;
476 bool do_edge_bal = false;
477 bool do_repart = false;
478 bool do_maxcut_min = false;
479 bool verbose_output = false;
480
481 // Do label propagation initialization instead of bfs?
482 pe = pl.getEntryPtr("pulp_lp_init");
483 if (pe) do_lp_init = pe->getValue(&do_lp_init);
484 if (do_lp_init) do_bfs_init = false;
485
486 // Now look at additional objective
487 pe = pl.getEntryPtr("pulp_minimize_maxcut");
488 if (pe) {
489 do_maxcut_min = pe->getValue(&do_maxcut_min);
490 // If we're doing the secondary objective,
491 // set the additional constraint as well
492 if (do_maxcut_min) do_edge_bal = true;
493 }
494
495 pe = pl.getEntryPtr("pulp_do_repart");
496 if (pe) {
497 do_repart = pe->getValue(&do_repart);
498 if (do_repart) {
499 // Do repartitioning with input parts
500 // TODO: read in current parts
501 // for (int i = 0; i < num_verts; ++i)
502 // parts[i] = something;
503 do_bfs_init = false;
504 do_lp_init = false;
505 std::string errStr = "repartitioning within (Xtra)PuLP is ";
506 errStr += "currently unsupported.";
507 throw std::runtime_error(errStr);
508 }
509 }
510
511 // Now grab vertex and edge imbalances, defaults at 10%
512 double vert_imbalance = 1.1;
513 double edge_imbalance = 1.1;
514 double imbalance = 1.1;
515
516 pe = pl.getEntryPtr("pulp_vert_imbalance");
517 if (pe) vert_imbalance = pe->getValue<double>(&vert_imbalance);
518 pe = pl.getEntryPtr("pulp_edge_imbalance");
519 if (pe) {
520 edge_imbalance = pe->getValue<double>(&edge_imbalance);
521 // if manually set edge imbalance, add do_edge_bal flag to true
522 do_edge_bal = true;
523 }
524 pe = pl.getEntryPtr("pulp_imbalance");
525 if (pe) imbalance = pe->getValue<double>(&imbalance);
526
527 if (vert_imbalance < 1.0)
528 throw std::runtime_error("pulp_vert_imbalance must be '1.0' or greater.");
529 if (edge_imbalance < 1.0)
530 throw std::runtime_error("pulp_edge_imbalance must be '1.0' or greater.");
531 if (imbalance < 1.0)
532 throw std::runtime_error("pulp_imbalance must be '1.0' or greater.");
533
534 // verbose output?
535 // TODO: fully implement verbose flag throughout PuLP
536 pe = pl.getEntryPtr("pulp_verbose");
537 if (pe) verbose_output = pe->getValue(&verbose_output);
538
539 // using pulp seed?
540 int pulp_seed = rand();
541 pe = pl.getEntryPtr("pulp_seed");
542 if (pe) pulp_seed = pe->getValue(&pulp_seed);
543
544
545 if (verbose_output) {
546 printf("procid: %d, n: %i, m: %li, vb: %f, eb: %f, imb: %f, p: %i\n",
547 problemComm->getRank(),
548 num_verts, num_edges,
549 vert_imbalance, edge_imbalance, imbalance, num_parts);
550 }
551
552 // Call partitioning; result returned in parts array
553#ifndef HAVE_ZOLTAN2_MPI
554 // Create PuLP's partitioning data structure
555 pulp_part_control_t ppc = {vert_imbalance, edge_imbalance,
556 do_lp_init, do_bfs_init, do_repart,
557 do_edge_bal, do_maxcut_min,
558 verbose_output, pulp_seed};
559
560 ierr = pulp_run(&g, &ppc, parts, num_parts);
561
562 env->globalInputAssertion(__FILE__, __LINE__, "pulp_run",
563 !ierr, BASIC_ASSERTION, problemComm);
564#else
565 // Create XtraPuLP's partitioning data structure
566 std::unique_ptr<double[]> constraints;
567 if (nVwgts > 0) {
568 constraints = std::unique_ptr<double[]>(new double[nVwgts]);
569 for (int i = 0; i < nVwgts; ++i) {
570 constraints[i] = imbalance;
571 }
572 } else {
573 constraints = std::unique_ptr<double[]>(nullptr);
574 }
575
576
577 pulp_part_control_t ppc = {
578 vert_imbalance, edge_imbalance,
579 constraints.get(), nVwgts,
580 do_lp_init, do_bfs_init, do_repart,
581 do_edge_bal, do_maxcut_min,
582 verbose_output, pulp_seed};
583
584 ierr = xtrapulp_run(&g, &ppc, parts, num_parts);
585
586 env->globalInputAssertion(__FILE__, __LINE__, "xtrapulp_run",
587 !ierr, BASIC_ASSERTION, problemComm);
588#endif
589
590
591 // Load answer into the solution if necessary
592 if ( (sizeof(int) != sizeof(part_t)) || (num_verts == 0) ) {
593 for (int i = 0; i < num_verts; i++)
594 partList[i] = parts[i];
595 delete [] parts;
596 }
597
598 solution->setParts(partList);
599
600 env->memory("Zoltan2-(Xtra)PuLP: After creating solution");
601
602 // Clean up copies made due to differing data sizes.
603#ifndef HAVE_ZOLTAN2_MPI
606#else
610#endif
611
612
613//#endif // DO NOT HAVE_MPI
614}
615
617// Scale and round scalar_t weights (typically float or double) to
618// PuLP int
619// subject to sum(weights) <= max_wgt_sum.
620// Scale only if deemed necessary.
621//
622// Note that we use ceil() instead of round() to avoid
623// rounding to zero weights.
624// Based on Zoltan's scale_round_weights, mode 1
625//
626// Modified from scale_weights() in Zoltan2_AlgParMETIS.hpp
627template <typename Adapter>
628int* AlgPuLP<Adapter>::scale_weights(
629 size_t nVtx, int nWgt,
630 ArrayView<StridedData<typename Adapter::lno_t,
631 typename Adapter::scalar_t> > fwgts
632)
633{
634 const double INT_EPSILON = 1e-5;
635
636 int *iwgts = new int[nVtx*nWgt];
637 int *nonint_local = new int[nWgt+nWgt];
638 int *nonint = nonint_local + nWgt;
639
640 double *sum_wgt_local = new double[nWgt*4];
641 double *max_wgt_local = sum_wgt_local + nWgt;
642 double *sum_wgt = max_wgt_local + nWgt;
643 double *max_wgt = sum_wgt + nWgt;
644
645 for (int i = 0; i < nWgt; i++) {
646 nonint_local[i] = 0;
647 sum_wgt_local[i] = 0.0;
648 max_wgt_local[i] = 0.0;
649 }
650
651 // Compute local sums of the weights
652 // Check whether all weights are integers
653 for (int j = 0; j < nWgt; j++) {
654 for (size_t i = 0; i < nVtx; i++) {
655 double fw = double(fwgts[j][i]);
656 if (!nonint_local[j]) {
657 int tmp = (int) floor(fw + .5); /* Nearest int */
658 if (fabs((double)tmp-fw) > INT_EPSILON) {
659 nonint_local[j] = 1;
660 }
661 }
662 sum_wgt_local[j] += fw;
663 if (fw > max_wgt_local[j]) max_wgt_local[j] = fw;
664 }
665 }
666
667 Teuchos::reduceAll<int,int> (*problemComm, Teuchos::REDUCE_MAX, nWgt,
668 nonint_local, nonint);
669 Teuchos::reduceAll<int,double>(*problemComm, Teuchos::REDUCE_SUM, nWgt,
670 sum_wgt_local, sum_wgt);
671 Teuchos::reduceAll<int,double>(*problemComm, Teuchos::REDUCE_MAX, nWgt,
672 max_wgt_local, max_wgt);
673
674 const double max_wgt_sum = double(std::numeric_limits<int>::max()/8);
675 for (int j = 0; j < nWgt; j++) {
676 double scale = 1.;
677
678 // Scaling needed if weights are not integers or weights'
679 // range is not sufficient
680 if (nonint[j] || (max_wgt[j]<=INT_EPSILON) || (sum_wgt[j]>max_wgt_sum)) {
681 /* Calculate scale factor */
682 if (sum_wgt[j] != 0.) scale = max_wgt_sum/sum_wgt[j];
683 }
684
685 /* Convert weights to positive integers using the computed scale factor */
686 for (size_t i = 0; i < nVtx; i++)
687 iwgts[i*nWgt+j] = (int) ceil(double(fwgts[j][i])*scale);
688 }
689
690 delete [] nonint_local;
691 delete [] sum_wgt_local;
692
693 return iwgts;
694}
695
696
697} // namespace Zoltan2
698
699#endif // HAVE_ZOLTAN2_PULP
700
702
703
704#endif
705
Zoltan2::BasicUserTypes< zscalar_t, zlno_t, zgno_t > user_t
Definition Metric.cpp:74
Defines the GraphModel interface.
Defines the PartitioningSolution class.
#define HELLO
Traits class to handle conversions between gno_t/lno_t and TPL data types (e.g., ParMETIS's idx_t,...
A gathering of useful namespace methods.
AlgPuLP(const RCP< const Environment > &, const RCP< const Comm< int > > &, const RCP< const base_adapter_t > &)
Adapter::base_adapter_t base_adapter_t
static void getValidParameters(ParameterList &)
Set up validators specific to this algorithm.
Algorithm defines the base class for all algorithms.
virtual void partition(const RCP< PartitioningSolution< Adapter > > &)
Partitioning method.
Adapter::scalar_t scalar_t
static RCP< Teuchos::BoolParameterEntryValidator > getBoolValidator()
Exists to make setting up validators less cluttered.
static RCP< Teuchos::AnyNumberParameterEntryValidator > getAnyDoubleValidator()
Exists to make setting up validators less cluttered.
static RCP< Teuchos::AnyNumberParameterEntryValidator > getAnyIntValidator()
Exists to make setting up validators less cluttered.
Created by mbenlioglu on Aug 31, 2020.
std::bitset< NUM_MODEL_FLAGS > modelFlag_t
@ BASIC_ASSERTION
fast typical checks for valid arguments
@ VERTICES_ARE_MATRIX_ROWS
use matrix rows as graph vertices
@ VERTICES_ARE_MESH_ELEMENTS
use mesh elements as vertices
@ BUILD_SUBSET_GRAPH
ignore invalid neighbors
@ GENERATE_CONSECUTIVE_IDS
algorithm requires consecutive ids
@ SYMMETRIZE_INPUT_TRANSPOSE
model must symmetrize input
@ SYMMETRIZE_INPUT_BIPARTITE
model must symmetrize input
@ REMOVE_SELF_EDGES
algorithm requires no self edges
@ VERTICES_ARE_MESH_NODES
use mesh nodes as vertices
@ VERTICES_ARE_MATRIX_COLUMNS
use columns as graph vertices
@ VERTICES_ARE_MATRIX_NONZEROS
use nonzeros as graph vertices
@ BUILD_LOCAL_GRAPH
model represents graph within only one rank
SparseMatrixAdapter_t::part_t part_t
static void DELETE_ARRAY(first_t **a)
static void ASSIGN_ARRAY(first_t **a, ArrayView< second_t > &b)