48#ifndef _ZOLTAN2_ALGND_HPP_
49#define _ZOLTAN2_ALGND_HPP_
82 template <
typename Adapter>
87 typedef typename Adapter::part_t part_t;
89 typedef typename Adapter::lno_t lno_t;
90 typedef typename Adapter::gno_t gno_t;
92 const RCP<const Environment> mEnv;
93 const RCP<const Comm<int>> mProblemComm;
95 std::string mPartitionMethod;
97 const RCP<const typename Adapter::base_adapter_t> mBaseInputAdapter;
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,
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);
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);
124 part_t targetPart,
const std::set<lno_t> &idsToExcl, std::set<lno_t> &outIds);
128 AlgND(
const RCP<const Environment> &env_,
129 const RCP<
const Comm<int>> &problemComm_,
130 const RCP<const typename Adapter::base_adapter_t> &baseInputAdapter_,
132 : mEnv(env_), mProblemComm(problemComm_), mPartitionMethod(
"rcb"),
133 mBaseInputAdapter(baseInputAdapter_), graphFlags(graphFlags_)
135#ifndef INCLUDE_ZOLTAN2_EXPERIMENTAL
139 if (mProblemComm->getSize() != 1)
144 const Teuchos::ParameterList &pl = mEnv->getParameters();
145 const Teuchos::ParameterEntry *pe;
147 pe = pl.getEntryPtr(
"edge_separator_method");
151 mPartitionMethod = pe->getValue<std::string>(&mPartitionMethod);
164 RCP<Teuchos::StringValidator> es_method_Validator =
165 Teuchos::rcp(
new Teuchos::StringValidator(Teuchos::tuple<std::string>(
"rcb",
"phg")));
167 pl.set(
"edge_separator_method",
"rcb",
"ND ordering - Edge separator method", es_method_Validator);
174 template <
typename Adapter>
178 throw std::logic_error(
"AlgND does not support global ordering.");
185 template <
typename Adapter>
198 Teuchos::ParameterList partParams;
200 part_t numParts = mEnv->getParameters().template get<part_t>(
"num_global_parts");
202 partParams.set(
"num_global_parts", numParts);
205 partParams.set(
"keep_partition_tree",
true);
208 Teuchos::ParameterList &zparams = partParams.sublist(
"zoltan_parameters",
false);
209 zparams.set(
"LB_METHOD", mPartitionMethod);
215 const RCP<const Environment> partEnv = rcp(
new Zoltan2::Environment(partParams, this->mEnv->comm_));
220 RCP<AlgZoltan<Adapter>> algZoltan = rcp(
new AlgZoltan<Adapter>(partEnv, mProblemComm, this->mBaseInputAdapter));
222 RCP<PartitioningSolution<Adapter>> partSoln;
226 algZoltan->partition(partSoln);
228 size_t numGlobalParts = partSoln->getTargetGlobalNumberOfParts();
230 const part_t *parts = partSoln->getPartListView();
244 assert(partSoln->isPartitioningTreeBinary() ==
true);
249 part_t numTreeVerts = 0;
250 std::vector<part_t> permPartNums;
252 std::vector<part_t> splitRangeBeg;
253 std::vector<part_t> splitRangeEnd;
254 std::vector<part_t> treeVertParents;
256 partSoln->getPartitionTree(numTreeVerts, permPartNums, splitRangeBeg,
257 splitRangeEnd, treeVertParents);
271 std::vector<part_t> levInds;
273 std::vector<part_t> sepLevels;
274 std::vector<std::set<part_t>> sepParts1;
275 std::vector<std::set<part_t>> sepParts2;
277 std::vector<std::pair<part_t, part_t>> treeIndxToSepLev(treeVertParents.size());
282 part_t *sepTreeView = solution_->getSeparatorTreeView();
284 part_t sepTreeIndx = treeVertParents.size() - 1;
286 sepTreeView[sepTreeIndx] = -1;
288 buildPartTree(0, levInds, numTreeVerts, permPartNums, splitRangeBeg, splitRangeEnd, treeVertParents,
289 sepLevels, sepParts1, sepParts2, maxLevel, sepTreeIndx, sepTreeView, treeIndxToSepLev);
291 solution_->setHaveSeparatorTree(
true);
306 part_t numSeparators = sepLevels.size();
315 part_t numLevels = maxLevel + 1;
317 std::vector<std::vector<part_t>> partLevelMap(numLevels, std::vector<part_t>(numGlobalParts));
319 std::vector<part_t> sepsInLev(numLevels, 0);
321 const auto graphModel = rcp(
new GraphModel<Adapter>(mBaseInputAdapter, mEnv, mProblemComm, graphFlags));
323 for (part_t i = 0; i < numSeparators; i++)
325 part_t level = sepLevels[i];
327 for (
typename std::set<part_t>::const_iterator iter = sepParts1[i].begin();
328 iter != sepParts1[i].end(); ++iter)
330 partLevelMap[level][*iter] = 2 * sepsInLev[level];
333 for (
typename std::set<part_t>::const_iterator iter = sepParts2[i].begin();
334 iter != sepParts2[i].end(); ++iter)
336 partLevelMap[level][*iter] = 2 * sepsInLev[level] + 1;
346 std::set<lno_t> sepVerts;
347 std::vector<std::vector<std::set<lno_t>>> sepVertsByLevel(numLevels);
354 for (part_t level = 0; level < numLevels; level++)
356 sepVertsByLevel[level].resize(sepsInLev[level]);
358 for (part_t levIndx = 0; levIndx < sepsInLev[level]; levIndx++)
364 lno_t bigraphNumU = 0, bigraphNumV = 0;
365 lno_t bigraphNumE = 0;
366 std::vector<lno_t> bigraphVMapU;
367 std::vector<lno_t> bigraphVMapV;
369 std::vector<lno_t> bigraphCRSRowPtr;
370 std::vector<lno_t> bigraphCRSCols;
372 getBoundLayer(levIndx, partLevelMap[level], parts, sepVerts,
373 bigraphNumU, bigraphNumV, bigraphNumE,
374 bigraphCRSRowPtr, bigraphCRSCols,
375 bigraphVMapU, bigraphVMapV, graphModel);
407 assert(bigraphNumV > 0);
409 Matcher<lno_t> bpMatch(bigraphCRSRowPtr.data(), bigraphCRSCols.data(), bigraphNumU, bigraphNumV, bigraphNumE);
419 std::vector<lno_t> VC;
421 bpMatch.
getVCfromMatching(bigraphCRSRowPtr, bigraphCRSCols, vertUMatches, vertVMatches,
422 bigraphVMapU, bigraphVMapV, VC);
424 for (
size_t i = 0; i < VC.size(); i++)
426 sepVerts.insert(VC[i]);
428 sepVertsByLevel[level][levIndx].insert(VC[i]);
441 lno_t *ipermView = solution_->getPermutationView(inverse);
442 lno_t *sepRangeView = solution_->getSeparatorRangeView();
444 fillSolutionIperm(graphModel, parts, sepVerts, sepVertsByLevel, treeIndxToSepLev, ipermView, sepRangeView);
446 solution_->setHaveInverse(
true);
447 solution_->setHaveSeparatorRange(
true);
453 std::cout <<
"Separators: " << std::endl;
455 part_t nLevels = sepVertsByLevel.size();
456 for (part_t level = 0; level < nLevels; level++)
459 part_t nSepsOnLev = sepVertsByLevel[level].size();
461 for (part_t levIndx = 0; levIndx < nSepsOnLev; levIndx++)
463 std::cout <<
" Separator " << level <<
" " << levIndx <<
": ";
465 typename std::set<lno_t>::const_iterator iterS;
466 for (iterS = sepVertsByLevel[level][levIndx].begin(); iterS != sepVertsByLevel[level][levIndx].end(); ++iterS)
468 std::cout << *iterS <<
" ";
470 std::cout << std::endl;
504 template <
typename Adapter>
507 const std::set<lno_t> &excVerts,
509 std::vector<lno_t> &bigraphCRSRowPtr, std::vector<lno_t> &bigraphCRSCols,
510 std::vector<lno_t> &bigraphVMapS, std::vector<lno_t> &bigraphVMapT,
513 typedef typename Adapter::offset_t offset_t;
516 lno_t numVerts = graphModel->getLocalNumVertices();
520 ArrayView<const gno_t> eIDs;
521 ArrayView<const offset_t> vOffsets;
522 ArrayView<input_t> wgts;
533 graphModel->getEdgeList(eIDs, vOffsets, wgts);
538 std::map<lno_t, std::set<lno_t>> bigraphEs;
539 std::set<lno_t> vSetS;
540 std::set<lno_t> vSetT;
544 for (
lno_t v1 = 0; v1 < numVerts; v1++)
547 part_t vpart1 = partMap[parts[v1]];
549 bool correctBL = (vpart1 >= 2 * levelIndx && vpart1 < 2 * (levelIndx + 1));
559 if (excVerts.find(v1) != excVerts.end())
566 for (offset_t j = vOffsets[v1]; j < vOffsets[v1 + 1]; j++)
571 part_t vpart2 = partMap[parts[v2]];
573 correctBL = (vpart2 >= 2 * levelIndx && vpart2 < 2 * (levelIndx + 1));
583 if (excVerts.find(v2) != excVerts.end())
588 if (vpart1 != vpart2)
596 if (bigraphEs.find(v1) == bigraphEs.end())
598 bigraphEs[v1] = std::set<lno_t>();
600 bigraphEs[v1].insert(v2);
615 bigraphNumS = vSetS.size();
616 bigraphNumT = vSetT.size();
622 bigraphVMapS.resize(bigraphNumS);
624 std::map<lno_t, lno_t> glob2LocTMap;
627 for (
typename std::set<lno_t>::const_iterator iter = vSetS.begin(); iter != vSetS.end(); ++iter)
629 bigraphVMapS[indx] = *iter;
633 bigraphVMapT.resize(bigraphNumT);
635 for (
typename std::set<lno_t>::const_iterator iter = vSetT.begin(); iter != vSetT.end(); ++iter)
637 bigraphVMapT[indx] = *iter;
638 glob2LocTMap[*iter] = indx;
646 bigraphCRSRowPtr.resize(bigraphNumS + 1);
647 bigraphCRSCols.resize(bigraphNumE);
653 bigraphCRSRowPtr[0] = 0;
657 typename std::map<lno_t, std::set<lno_t>>::const_iterator iterM;
658 for (iterM = bigraphEs.begin(); iterM != bigraphEs.end(); ++iterM)
660 bigraphCRSRowPtr[rownum + 1] = bigraphCRSRowPtr[rownum] + (*iterM).second.size();
662 for (
typename std::set<lno_t>::const_iterator iter = (*iterM).second.begin(); iter != (*iterM).second.end(); ++iter)
664 bigraphCRSCols[nzIndx] = glob2LocTMap[(*iter)];
677 template <
typename Adapter>
678 void AlgND<Adapter>::
679 buildPartTree(
part_t level, std::vector<part_t> &levIndx,
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,
688 part_t *sepTreeView, std::vector<std::pair<part_t, part_t>> &treeIndxToSepLev)
692 part_t tmpMaxLev = maxLev;
697 typename std::vector<part_t>::const_iterator iter;
698 std::vector<part_t> inds;
700 for (iter = treeVertParents.begin(); iter != treeVertParents.end(); ++iter)
714 assert(inds.size() == 2 || inds.size() == 0);
717 if (inds.size() == 2)
720 if ((
part_t)levIndx.size() < level + 1)
722 levIndx.push_back(0);
731 treeIndxToSepLev[gIndx].first = level;
732 treeIndxToSepLev[gIndx].second = levIndx[level];
737 sepLevels.push_back(level);
739 sepParts1.push_back(std::set<part_t>());
740 typename std::vector<std::set<part_t>>::iterator setIter = sepParts1.end();
743 for (
part_t k = splitRangeBeg[v0]; k < splitRangeEnd[v0]; k++)
745 (*setIter).insert(permPartNums[k]);
748 sepParts2.push_back(std::set<part_t>());
749 setIter = sepParts2.end();
752 for (
part_t k = splitRangeBeg[v1]; k < splitRangeEnd[v1]; k++)
754 (*setIter).insert(permPartNums[k]);
757 part_t parentNode = gIndx;
759 sepTreeView[gIndx] = parentNode;
762 buildPartTree(level + 1, levIndx, v0,
763 permPartNums, splitRangeBeg, splitRangeEnd, treeVertParents,
764 sepLevels, sepParts1, sepParts2,
766 gIndx, sepTreeView, treeIndxToSepLev);
767 if (tmpMaxLev > maxLev)
773 sepTreeView[gIndx] = parentNode;
775 buildPartTree(level + 1, levIndx, v1,
776 permPartNums, splitRangeBeg, splitRangeEnd, treeVertParents,
777 sepLevels, sepParts1, sepParts2,
779 gIndx, sepTreeView, treeIndxToSepLev);
780 if (tmpMaxLev > maxLev)
788 treeIndxToSepLev[gIndx].first = -1;
789 treeIndxToSepLev[gIndx].second = permPartNums[splitRangeBeg[startV]];
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,
809 lno_t sepRangeIndx = 0;
810 sepRangeView[sepRangeIndx] = 0;
812 for (
size_t i = 0; i < treeIndxToSepLev.size(); i++)
814 part_t lev = treeIndxToSepLev[i].first;
820 std::set<lno_t> idSet;
821 getIdsOfPart(graphModel, parts, treeIndxToSepLev[i].second, sepVerts, idSet);
823 for (
typename std::set<lno_t>::const_iterator setIter = idSet.begin(); setIter != idSet.end();
826 ipermView[permIndx] = *setIter;
829 sepRangeView[sepRangeIndx + 1] = sepRangeView[sepRangeIndx] + idSet.size();
838 const std::set<lno_t> &idSet = sepVertsByLevel[lev][treeIndxToSepLev[i].second];
840 for (
typename std::set<lno_t>::const_iterator setIter = idSet.begin();
841 setIter != idSet.end(); ++setIter)
843 ipermView[permIndx] = *setIter;
846 sepRangeView[sepRangeIndx + 1] = sepRangeView[sepRangeIndx] + idSet.size();
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)
861 size_t numVerts = graphModel->getLocalNumVertices();
863 for (
size_t i = 0; i < numVerts; i++)
865 if (parts[i] == targetPart && idsToExcl.find(i) == idsToExcl.end())
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
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