Zoltan2
Loading...
Searching...
No Matches
Zoltan2_AlgND.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
46//MMW need to specify that this requires Zoltan
47
48#ifndef _ZOLTAN2_ALGND_HPP_
49#define _ZOLTAN2_ALGND_HPP_
50
53#include <Zoltan2_Algorithm.hpp>
54#include <Zoltan2_AlgZoltan.hpp>
55
57
58#include <sstream>
59#include <string>
60#include <bitset>
61
66namespace Zoltan2
67{
68
70
82 template <typename Adapter>
83 class AlgND : public Algorithm<Adapter>
84 {
85
86 private:
87 typedef typename Adapter::part_t part_t;
88
89 typedef typename Adapter::lno_t lno_t;
90 typedef typename Adapter::gno_t gno_t;
91
92 const RCP<const Environment> mEnv;
93 const RCP<const Comm<int>> mProblemComm;
94
95 std::string mPartitionMethod;
96
97 const RCP<const typename Adapter::base_adapter_t> mBaseInputAdapter;
98 modelFlag_t graphFlags;
99
100 void getBoundLayer(part_t levelIndx, const std::vector<part_t> &partMap,
101 const part_t *parts, const std::set<lno_t> &excVerts,
102 lno_t &bigraphNumS, lno_t &bigraphNumT, lno_t &bigraphNumE,
103 std::vector<lno_t> &bigraphCRSRowPtr, std::vector<lno_t> &bigraphCRSCols,
104 std::vector<lno_t> &bigraphVMapU, std::vector<lno_t> &bigraphVMapV,
105 const RCP<const GraphModel<Adapter>> &graphModel);
106
107 void buildPartTree(part_t level, std::vector<part_t> &levIndx,
108 part_t startV, const std::vector<part_t> &permPartNums,
109 const std::vector<part_t> &splitRangeBeg,
110 const std::vector<part_t> &splitRangeEnd,
111 const std::vector<part_t> &treeVertParents,
112 std::vector<part_t> &sepLevels, std::vector<std::set<part_t>> &sepParts1,
113 std::vector<std::set<part_t>> &sepParts2, part_t &maxLev,
114 part_t &sepTreeIndx, part_t *sepTreeView,
115 std::vector<std::pair<part_t, part_t>> &treeIndxToSepLev);
116
117 void fillSolutionIperm(const RCP<const GraphModel<Adapter>> &graphModel,
118 const part_t *parts, const std::set<lno_t> &sepVerts,
119 const std::vector<std::vector<std::set<lno_t>>> &sepVertsByLevel,
120 const std::vector<std::pair<part_t, part_t>> &treeIndxToSepLev,
121 lno_t *ipermView, lno_t *sepRangeView);
122
123 void getIdsOfPart(const RCP<const GraphModel<Adapter>> &graphModel, const part_t *parts,
124 part_t targetPart, const std::set<lno_t> &idsToExcl, std::set<lno_t> &outIds);
125
126 public:
127 // Constructor
128 AlgND(const RCP<const Environment> &env_,
129 const RCP<const Comm<int>> &problemComm_,
130 const RCP<const typename Adapter::base_adapter_t> &baseInputAdapter_,
131 const modelFlag_t &graphFlags_)
132 : mEnv(env_), mProblemComm(problemComm_), mPartitionMethod("rcb"),
133 mBaseInputAdapter(baseInputAdapter_), graphFlags(graphFlags_)
134 {
135#ifndef INCLUDE_ZOLTAN2_EXPERIMENTAL
136 Z2_THROW_EXPERIMENTAL("Zoltan2 AlgND is strictly experimental software ")
137#endif
138
139 if (mProblemComm->getSize() != 1)
140 {
141 Z2_THROW_SERIAL("Zoltan2 AlgND is strictly serial!");
142 }
143
144 const Teuchos::ParameterList &pl = mEnv->getParameters();
145 const Teuchos::ParameterEntry *pe;
146
147 pe = pl.getEntryPtr("edge_separator_method");
148
149 if (pe)
150 {
151 mPartitionMethod = pe->getValue<std::string>(&mPartitionMethod);
152 }
153 }
154
155 // Ordering method
156 int localOrder(const RCP<LocalOrderingSolution<lno_t>> &solution_);
157 int globalOrder(const RCP<GlobalOrderingSolution<gno_t>> &solution_);
158
161 static void getValidParameters(ParameterList &pl)
162 {
163
164 RCP<Teuchos::StringValidator> es_method_Validator =
165 Teuchos::rcp(new Teuchos::StringValidator(Teuchos::tuple<std::string>("rcb", "phg")));
166
167 pl.set("edge_separator_method", "rcb", "ND ordering - Edge separator method", es_method_Validator);
168 }
169 };
171
174 template <typename Adapter>
176 const RCP<GlobalOrderingSolution<gno_t>> &solution_)
177 {
178 throw std::logic_error("AlgND does not support global ordering.");
179 }
180
182
185 template <typename Adapter>
186 int AlgND<Adapter>::localOrder(const RCP<LocalOrderingSolution<lno_t>> &solution_)
187 {
188 mEnv->debug(DETAILED_STATUS, std::string("Entering AlgND"));
189
191 // First, let's partition with RCB using Zoltan. Eventually, we will change
192 // to give an option to use PHG
194
196 // Create parameter list for partitioning environment
198 Teuchos::ParameterList partParams;
199
200 part_t numParts = mEnv->getParameters().template get<part_t>("num_global_parts");
201
202 partParams.set("num_global_parts", numParts);
203
204 // Keeping partitioning tree
205 partParams.set("keep_partition_tree", true);
206
207 // Set Zoltan parameter lists
208 Teuchos::ParameterList &zparams = partParams.sublist("zoltan_parameters", false);
209 zparams.set("LB_METHOD", mPartitionMethod);
211
213 //Create new environment with parameters for partitioning
215 const RCP<const Environment> partEnv = rcp(new Zoltan2::Environment(partParams, this->mEnv->comm_));
217
218 int nUserWts = 0;
219
220 RCP<AlgZoltan<Adapter>> algZoltan = rcp(new AlgZoltan<Adapter>(partEnv, mProblemComm, this->mBaseInputAdapter));
221
222 RCP<PartitioningSolution<Adapter>> partSoln;
223 partSoln =
224 RCP<PartitioningSolution<Adapter>>(new PartitioningSolution<Adapter>(partEnv, mProblemComm, nUserWts, algZoltan));
225
226 algZoltan->partition(partSoln);
227
228 size_t numGlobalParts = partSoln->getTargetGlobalNumberOfParts();
229
230 const part_t *parts = partSoln->getPartListView();
231
232 // size_t numVerts = mGraphModel->getLocalNumVertices();
233 // for(size_t i=0; i< numVerts; i++)
234 // {
235 // std::cout << "part[" << i << "] = " << parts[i] <<std::endl;
236 // }
238
240 // Obtain partitioning tree info from solution
242
243 // Need to guarantee partitioning tree is binary
244 assert(partSoln->isPartitioningTreeBinary() == true);
245
247 // Get partitioning tree from solution
249 part_t numTreeVerts = 0;
250 std::vector<part_t> permPartNums; // peritab in Scotch
251
252 std::vector<part_t> splitRangeBeg;
253 std::vector<part_t> splitRangeEnd;
254 std::vector<part_t> treeVertParents;
255
256 partSoln->getPartitionTree(numTreeVerts, permPartNums, splitRangeBeg,
257 splitRangeEnd, treeVertParents);
259
261 // Grab part numbers that are to be split by the separators
262 //
263 // Each separator i is represented by 1 integer and two sets of part_t's in the
264 // the following 3 structure:
265 //
266 // sepLevels[i] - level of separator
267 // sepParts1[i] - 1st set of parts on one side of separator
268 // sepParts2[i] - 2nd set of parts on other side of separator
269 //
271 std::vector<part_t> levInds;
272
273 std::vector<part_t> sepLevels;
274 std::vector<std::set<part_t>> sepParts1;
275 std::vector<std::set<part_t>> sepParts2;
276
277 std::vector<std::pair<part_t, part_t>> treeIndxToSepLev(treeVertParents.size());
278
279 part_t maxLevel = 0;
280
281 //View of separator tree structure of solution
282 part_t *sepTreeView = solution_->getSeparatorTreeView();
283
284 part_t sepTreeIndx = treeVertParents.size() - 1;
285
286 sepTreeView[sepTreeIndx] = -1;
287
288 buildPartTree(0, levInds, numTreeVerts, permPartNums, splitRangeBeg, splitRangeEnd, treeVertParents,
289 sepLevels, sepParts1, sepParts2, maxLevel, sepTreeIndx, sepTreeView, treeIndxToSepLev);
290
291 solution_->setHaveSeparatorTree(true);
292
293 // std::cout << "sepTreeView: ";
294 // for(part_t i=0; i<treeVertParents.size(); i++)
295 // {
296 // std::cout << sepTreeView[i] << " ";
297 // }
298 // std::cout << std::endl;
299
300 // std::cout << "treeIndxToSepLev:" << std::endl;
301 // for(part_t i=0; i<treeVertParents.size(); i++)
302 // {
303 // std::cout << treeIndxToSepLev[i].first << " " << treeIndxToSepLev[i].second <<std::endl;
304 // }
305
306 part_t numSeparators = sepLevels.size();
309
311 // Create a map that maps each part number to a new number based on
312 // the level of the hiearchy of the separator tree. This allows us
313 // to easily identify the boundary value vertices
315 part_t numLevels = maxLevel + 1;
316
317 std::vector<std::vector<part_t>> partLevelMap(numLevels, std::vector<part_t>(numGlobalParts));
318
319 std::vector<part_t> sepsInLev(numLevels, 0);
320
321 const auto graphModel = rcp(new GraphModel<Adapter>(mBaseInputAdapter, mEnv, mProblemComm, graphFlags));
322
323 for (part_t i = 0; i < numSeparators; i++)
324 {
325 part_t level = sepLevels[i];
326
327 for (typename std::set<part_t>::const_iterator iter = sepParts1[i].begin();
328 iter != sepParts1[i].end(); ++iter)
329 {
330 partLevelMap[level][*iter] = 2 * sepsInLev[level];
331 }
332
333 for (typename std::set<part_t>::const_iterator iter = sepParts2[i].begin();
334 iter != sepParts2[i].end(); ++iter)
335 {
336 partLevelMap[level][*iter] = 2 * sepsInLev[level] + 1;
337 }
338
339 sepsInLev[level]++;
340 }
342
343 // Set of separator vertices. Used to keep track of what vertices are
344 // already in previous calculated separators. These vertices should be
345 // excluded from future separator calculations
346 std::set<lno_t> sepVerts;
347 std::vector<std::vector<std::set<lno_t>>> sepVertsByLevel(numLevels);
348
350 // Loop over each cut
351 // 1. Build boundary layer between parts
352 // 2. Build vertex separator from boundary layer
354 for (part_t level = 0; level < numLevels; level++)
355 {
356 sepVertsByLevel[level].resize(sepsInLev[level]);
357
358 for (part_t levIndx = 0; levIndx < sepsInLev[level]; levIndx++)
359 {
360
362 // Build boundary layer between parts (edge separator)
364 lno_t bigraphNumU = 0, bigraphNumV = 0;
365 lno_t bigraphNumE = 0; // Should probably be size_t, but making lno_t for Matcher
366 std::vector<lno_t> bigraphVMapU;
367 std::vector<lno_t> bigraphVMapV;
368
369 std::vector<lno_t> bigraphCRSRowPtr;
370 std::vector<lno_t> bigraphCRSCols;
371
372 getBoundLayer(levIndx, partLevelMap[level], parts, sepVerts,
373 bigraphNumU, bigraphNumV, bigraphNumE,
374 bigraphCRSRowPtr, bigraphCRSCols,
375 bigraphVMapU, bigraphVMapV, graphModel);
376
377 // std::cout << "Bipartite graph: " << bigraphNumU << " " << bigraphNumV << " "
378 // << bigraphNumE << std::endl;
379
380 // for (size_t i=0;i<bigraphVMapU.size();i++)
381 // {
382 // std::cout << "boundVertU: " << bigraphVMapU[i] << std::endl;
383 // }
384
385 // for (size_t i=0;i<bigraphVMapV.size();i++)
386 // {
387 // std::cout << "boundVertV: " << bigraphVMapV[i] << std::endl;
388 // }
389
390 // for (lno_t rownum=0;rownum<bigraphNumU;rownum++)
391 // {
392
393 // for (lno_t eIdx=bigraphCRSRowPtr[rownum];eIdx<bigraphCRSRowPtr[rownum+1];eIdx++)
394 // {
395 // std::cout << "bipartite E: " << bigraphVMapU[rownum] << ", " << bigraphVMapV[ bigraphCRSCols[eIdx]]
396 // << " ( " << rownum << "," << bigraphCRSCols[eIdx] << " )" << std::endl;
397 // }
398
399 // }
401
403 // Calculate bipartite matching from boundary layer
405 if (bigraphNumU > 0)
406 {
407 assert(bigraphNumV > 0);
408
409 Matcher<lno_t> bpMatch(bigraphCRSRowPtr.data(), bigraphCRSCols.data(), bigraphNumU, bigraphNumV, bigraphNumE);
410 bpMatch.match();
411
412 const std::vector<lno_t> &vertUMatches = bpMatch.getVertexUMatches();
413 const std::vector<lno_t> &vertVMatches = bpMatch.getVertexVMatches();
415
417 // Calculate vertex cover (which is vertex separator) from matching
419 std::vector<lno_t> VC;
420
421 bpMatch.getVCfromMatching(bigraphCRSRowPtr, bigraphCRSCols, vertUMatches, vertVMatches,
422 bigraphVMapU, bigraphVMapV, VC);
423
424 for (size_t i = 0; i < VC.size(); i++)
425 {
426 sepVerts.insert(VC[i]);
427
428 sepVertsByLevel[level][levIndx].insert(VC[i]);
429 // std::cout << "VC: " << VC[i] << std::endl;
430 }
432 }
433 }
434 }
436
438 // Fill solution structures: invperm and separatorRange
440 bool inverse = true;
441 lno_t *ipermView = solution_->getPermutationView(inverse);
442 lno_t *sepRangeView = solution_->getSeparatorRangeView();
443
444 fillSolutionIperm(graphModel, parts, sepVerts, sepVertsByLevel, treeIndxToSepLev, ipermView, sepRangeView);
445
446 solution_->setHaveInverse(true);
447 solution_->setHaveSeparatorRange(true);
449
451 // Output separators
453 std::cout << "Separators: " << std::endl;
454
455 part_t nLevels = sepVertsByLevel.size();
456 for (part_t level = 0; level < nLevels; level++)
457 {
458 //sepVertsByLevel[level].resize(sepsInLev[level]);
459 part_t nSepsOnLev = sepVertsByLevel[level].size();
460
461 for (part_t levIndx = 0; levIndx < nSepsOnLev; levIndx++)
462 {
463 std::cout << " Separator " << level << " " << levIndx << ": ";
464
465 typename std::set<lno_t>::const_iterator iterS;
466 for (iterS = sepVertsByLevel[level][levIndx].begin(); iterS != sepVertsByLevel[level][levIndx].end(); ++iterS)
467 {
468 std::cout << *iterS << " ";
469 }
470 std::cout << std::endl;
471 }
472 }
474
475 // std::cout << "iPerm: ";
476 // for(part_t i=0; i<numVerts; i++)
477 // {
478 // std::cout << ipermView[i] << " ";
479 // }
480 // std::cout << std::endl;
481
482 // std::cout << "sepRange: ";
483 // for(part_t i=0; i<treeVertParents.size()+1; i++)
484 // {
485 // std::cout << sepRangeView[i] << " ";
486 // }
487 // std::cout << std::endl;
488
490
492
493 mEnv->debug(DETAILED_STATUS, std::string("Exiting AlgND"));
494 return 0;
495 }
497
499 // Create boundary layer of vertices between 2 partitions
500 //
501 // Could improve the efficiency here by first creating a boundary layer graph
502 // between all parts
504 template <typename Adapter>
505 void AlgND<Adapter>::getBoundLayer(part_t levelIndx, const std::vector<part_t> &partMap,
506 const part_t *parts,
507 const std::set<lno_t> &excVerts,
508 lno_t &bigraphNumS, lno_t &bigraphNumT, lno_t &bigraphNumE,
509 std::vector<lno_t> &bigraphCRSRowPtr, std::vector<lno_t> &bigraphCRSCols,
510 std::vector<lno_t> &bigraphVMapS, std::vector<lno_t> &bigraphVMapT,
511 const RCP<const GraphModel<Adapter>> &graphModel)
512 {
513 typedef typename Adapter::offset_t offset_t; // offset_t
514 typedef StridedData<lno_t, typename Adapter::scalar_t> input_t;
515
516 lno_t numVerts = graphModel->getLocalNumVertices();
517
518 //Teuchos ArrayView
519 // Original -- ArrayView< const lno_t > eIDs;
520 ArrayView<const gno_t> eIDs;
521 ArrayView<const offset_t> vOffsets;
522 ArrayView<input_t> wgts;
523
524 // MMW:
525 // For some reason getLocalEdgeList seems to be returning empty eIDs
526 // getEdgeList expects eIDs to be an array of gno_t
527 // I wanted eIDs to be lno_t since this ordering is computed on a single node and
528 // it seems unnecessary to use the potentially larger gno_t.
529 // The problem might be that the partitioning is being calculated on the gno_t.
530 // Perhaps a solution would be set gno_t = lno_t in the partitioning.
531 // For now, I'll leave this since the edgelist is unlikely to be prohibitively big
532
533 graphModel->getEdgeList(eIDs, vOffsets, wgts);
534
535 // original
536 // ( (GraphModel<typename Adapter::base_adapter_t>) *mGraphModel).getEdgeList(eIDs, vOffsets, wgts);
537
538 std::map<lno_t, std::set<lno_t>> bigraphEs;
539 std::set<lno_t> vSetS;
540 std::set<lno_t> vSetT;
541
542 bigraphNumE = 0;
543
544 for (lno_t v1 = 0; v1 < numVerts; v1++)
545 {
546
547 part_t vpart1 = partMap[parts[v1]];
548
549 bool correctBL = (vpart1 >= 2 * levelIndx && vpart1 < 2 * (levelIndx + 1));
550
551 // if vertex is not in the correct range of parts, it cannot be a member of
552 // this boundary layer
553 if (!correctBL)
554 {
555 continue;
556 }
557
558 // Ignore vertices that belong to set of vertices to exclude
559 if (excVerts.find(v1) != excVerts.end())
560 {
561 continue;
562 }
563
564 //Loop over edges connected to v1
565 //MMW figure out how to get this from Zoltan2
566 for (offset_t j = vOffsets[v1]; j < vOffsets[v1 + 1]; j++)
567 {
568
569 lno_t v2 = eIDs[j];
570
571 part_t vpart2 = partMap[parts[v2]];
572
573 correctBL = (vpart2 >= 2 * levelIndx && vpart2 < 2 * (levelIndx + 1));
574
575 // if vertex is not in the correct range of parts, it cannot be a member of
576 // this boundary layer
577 if (!correctBL)
578 {
579 continue;
580 }
581
582 // Ignore vertices that belong to set of vertices to exclude
583 if (excVerts.find(v2) != excVerts.end())
584 {
585 continue;
586 }
587
588 if (vpart1 != vpart2)
589 {
590 // Vertex added to 1st set of boundary vertices
591 if (vpart1 < vpart2)
592 {
593 vSetS.insert(v1);
594
595 // v1, v2
596 if (bigraphEs.find(v1) == bigraphEs.end())
597 {
598 bigraphEs[v1] = std::set<lno_t>();
599 }
600 bigraphEs[v1].insert(v2);
601 bigraphNumE++;
602 }
603 // Vertex added to 2nd set of boundary vertices
604 else
605 {
606 vSetT.insert(v1);
607 }
608 }
609 }
610 }
611
613 // Set size of two vertex sets for bipartite graph
615 bigraphNumS = vSetS.size();
616 bigraphNumT = vSetT.size();
618
621
622 bigraphVMapS.resize(bigraphNumS);
623
624 std::map<lno_t, lno_t> glob2LocTMap;
625
626 lno_t indx = 0;
627 for (typename std::set<lno_t>::const_iterator iter = vSetS.begin(); iter != vSetS.end(); ++iter)
628 {
629 bigraphVMapS[indx] = *iter;
630 indx++;
631 }
632
633 bigraphVMapT.resize(bigraphNumT);
634 indx = 0;
635 for (typename std::set<lno_t>::const_iterator iter = vSetT.begin(); iter != vSetT.end(); ++iter)
636 {
637 bigraphVMapT[indx] = *iter;
638 glob2LocTMap[*iter] = indx;
639 indx++;
640 }
642
644 // Set sizes for bipartite graph data structures
646 bigraphCRSRowPtr.resize(bigraphNumS + 1);
647 bigraphCRSCols.resize(bigraphNumE);
649
651 // Copy bipartite graph edges into CRS format
653 bigraphCRSRowPtr[0] = 0;
654
655 lno_t rownum = 0;
656 size_t nzIndx = 0;
657 typename std::map<lno_t, std::set<lno_t>>::const_iterator iterM;
658 for (iterM = bigraphEs.begin(); iterM != bigraphEs.end(); ++iterM)
659 {
660 bigraphCRSRowPtr[rownum + 1] = bigraphCRSRowPtr[rownum] + (*iterM).second.size();
661
662 for (typename std::set<lno_t>::const_iterator iter = (*iterM).second.begin(); iter != (*iterM).second.end(); ++iter)
663 {
664 bigraphCRSCols[nzIndx] = glob2LocTMap[(*iter)];
665
666 nzIndx++;
667 }
668
669 rownum++;
670 }
672 }
674
677 template <typename Adapter>
678 void AlgND<Adapter>::
679 buildPartTree(part_t level, std::vector<part_t> &levIndx,
680 part_t startV,
681 const std::vector<part_t> &permPartNums,
682 const std::vector<part_t> &splitRangeBeg,
683 const std::vector<part_t> &splitRangeEnd,
684 const std::vector<part_t> &treeVertParents,
685 std::vector<part_t> &sepLevels,
686 std::vector<std::set<part_t>> &sepParts1, std::vector<std::set<part_t>> &sepParts2,
687 part_t &maxLev, part_t &gIndx,
688 part_t *sepTreeView, std::vector<std::pair<part_t, part_t>> &treeIndxToSepLev)
689 {
690 // Insert information for this separator
691 maxLev = level;
692 part_t tmpMaxLev = maxLev;
693
695 // Search for indices that have parent startV
697 typename std::vector<part_t>::const_iterator iter;
698 std::vector<part_t> inds;
699 part_t ind = 0;
700 for (iter = treeVertParents.begin(); iter != treeVertParents.end(); ++iter)
701 {
702 if (*iter == startV)
703 {
704 inds.push_back(ind);
705 }
706 ind++;
707 }
709
711 // If startV has children, this will correspond to a separator. Construct
712 // appropriate data structure and then recurse
714 assert(inds.size() == 2 || inds.size() == 0);
715
716 // If startV has children
717 if (inds.size() == 2)
718 {
719
720 if ((part_t)levIndx.size() < level + 1)
721 {
722 levIndx.push_back(0);
723 }
724 else
725 {
726 levIndx[level]++;
727 }
728
729 // std::cout << "gIndx " << gIndx << ": separator " << level << " " << levIndx[level] << std::endl;
730
731 treeIndxToSepLev[gIndx].first = level;
732 treeIndxToSepLev[gIndx].second = levIndx[level];
733
734 part_t v0 = inds[0];
735 part_t v1 = inds[1];
736
737 sepLevels.push_back(level);
738
739 sepParts1.push_back(std::set<part_t>());
740 typename std::vector<std::set<part_t>>::iterator setIter = sepParts1.end();
741 setIter--; // set iterator to point to new set
742
743 for (part_t k = splitRangeBeg[v0]; k < splitRangeEnd[v0]; k++)
744 {
745 (*setIter).insert(permPartNums[k]);
746 }
747
748 sepParts2.push_back(std::set<part_t>());
749 setIter = sepParts2.end();
750 setIter--; // set iterator to point to new set
751
752 for (part_t k = splitRangeBeg[v1]; k < splitRangeEnd[v1]; k++)
753 {
754 (*setIter).insert(permPartNums[k]);
755 }
756
757 part_t parentNode = gIndx;
758 gIndx--;
759 sepTreeView[gIndx] = parentNode;
760
761 // Recursively call function on children
762 buildPartTree(level + 1, levIndx, v0,
763 permPartNums, splitRangeBeg, splitRangeEnd, treeVertParents,
764 sepLevels, sepParts1, sepParts2,
765 tmpMaxLev,
766 gIndx, sepTreeView, treeIndxToSepLev);
767 if (tmpMaxLev > maxLev)
768 {
769 maxLev = tmpMaxLev;
770 }
771
772 gIndx--;
773 sepTreeView[gIndx] = parentNode;
774
775 buildPartTree(level + 1, levIndx, v1,
776 permPartNums, splitRangeBeg, splitRangeEnd, treeVertParents,
777 sepLevels, sepParts1, sepParts2,
778 tmpMaxLev,
779 gIndx, sepTreeView, treeIndxToSepLev);
780 if (tmpMaxLev > maxLev)
781 {
782 maxLev = tmpMaxLev;
783 }
784 }
785 else // no children, so this is not a separator
786 {
787 // std::cout << "gIndx " << gIndx << " leaf: " << permPartNums[splitRangeBeg[startV]] << std::endl;
788 treeIndxToSepLev[gIndx].first = -1;
789 treeIndxToSepLev[gIndx].second = permPartNums[splitRangeBeg[startV]];
790
791 maxLev--;
792 }
794 }
795
797
800 template <typename Adapter>
801 void AlgND<Adapter>::
802 fillSolutionIperm(const RCP<const GraphModel<Adapter>> &graphModel,
803 const part_t *parts, const std::set<lno_t> &sepVerts,
804 const std::vector<std::vector<std::set<lno_t>>> &sepVertsByLevel,
805 const std::vector<std::pair<part_t, part_t>> &treeIndxToSepLev,
806 lno_t *ipermView, lno_t *sepRangeView)
807 {
808 lno_t permIndx = 0;
809 lno_t sepRangeIndx = 0;
810 sepRangeView[sepRangeIndx] = 0;
811
812 for (size_t i = 0; i < treeIndxToSepLev.size(); i++)
813 {
814 part_t lev = treeIndxToSepLev[i].first;
816 // Leaf node of separator tree
818 if (lev == -1)
819 {
820 std::set<lno_t> idSet;
821 getIdsOfPart(graphModel, parts, treeIndxToSepLev[i].second, sepVerts, idSet);
822
823 for (typename std::set<lno_t>::const_iterator setIter = idSet.begin(); setIter != idSet.end();
824 ++setIter)
825 {
826 ipermView[permIndx] = *setIter;
827 permIndx++;
828 }
829 sepRangeView[sepRangeIndx + 1] = sepRangeView[sepRangeIndx] + idSet.size();
830 sepRangeIndx++;
831 }
834 // Internal "separator node" of separator tree
836 else
837 {
838 const std::set<lno_t> &idSet = sepVertsByLevel[lev][treeIndxToSepLev[i].second];
839
840 for (typename std::set<lno_t>::const_iterator setIter = idSet.begin();
841 setIter != idSet.end(); ++setIter)
842 {
843 ipermView[permIndx] = *setIter;
844 permIndx++;
845 }
846 sepRangeView[sepRangeIndx + 1] = sepRangeView[sepRangeIndx] + idSet.size();
847 sepRangeIndx++;
848 }
850 }
851 }
853
856 template <typename Adapter>
857 void AlgND<Adapter>::
858 getIdsOfPart(const RCP<const GraphModel<Adapter>> &graphModel, const part_t *parts,
859 part_t targetPart, const std::set<lno_t> &idsToExcl, std::set<lno_t> &outIds)
860 {
861 size_t numVerts = graphModel->getLocalNumVertices();
862
863 for (size_t i = 0; i < numVerts; i++)
864 {
865 if (parts[i] == targetPart && idsToExcl.find(i) == idsToExcl.end())
866 {
867 outIds.insert(i);
868 }
869 }
870 }
872
873} // namespace Zoltan2
874
875#endif
interface to the Zoltan package
#define Z2_THROW_SERIAL(mystr)
Throw an error when code is run on more than one processor.
#define Z2_THROW_EXPERIMENTAL(mystr)
Throw an error when experimental code is requested but not compiled.
Defines the IdentifierModel interface.
Defines the PartitioningSolution class.
int localOrder(const RCP< LocalOrderingSolution< lno_t > > &solution_)
Ordering method.
static void getValidParameters(ParameterList &pl)
Set up validators specific to this algorithm.
int globalOrder(const RCP< GlobalOrderingSolution< gno_t > > &solution_)
Ordering method.
AlgND(const RCP< const Environment > &env_, const RCP< const Comm< int > > &problemComm_, const RCP< const typename Adapter::base_adapter_t > &baseInputAdapter_, const modelFlag_t &graphFlags_)
Algorithm defines the base class for all algorithms.
The user parameters, debug, timing and memory profiling output objects, and error checking methods.
map_t::local_ordinal_type lno_t
Created by mbenlioglu on Aug 31, 2020.
std::bitset< NUM_MODEL_FLAGS > modelFlag_t
SparseMatrixAdapter_t::part_t part_t