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>
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
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.
GraphModel defines the interface required for graph models.
An implementation of the Matcher interface that operates on Epetra matrices and Graphs.
const std::vector< LO > & getVertexVMatches()
const std::vector< LO > & getVertexUMatches()
void getVCfromMatching(const std::vector< LO > &bigraphCRSRowPtr, std::vector< LO > &bigraphCRSCols, const std::vector< LO > &vertUMatches, const std::vector< LO > &vertVMatches, const std::vector< LO > &bigraphVMapU, const std::vector< LO > &bigraphVMapV, std::vector< LO > &VC)
LO match()
Computes the maximum cardinality matching.
A PartitioningSolution is a solution to a partitioning problem.
The StridedData class manages lists of weights or coordinates.
map_t::local_ordinal_type lno_t
Definition: mapRemotes.cpp:17
Created by mbenlioglu on Aug 31, 2020.
std::bitset< NUM_MODEL_FLAGS > modelFlag_t
@ DETAILED_STATUS
sub-steps, each method's entry and exit
SparseMatrixAdapter_t::part_t part_t