49 #ifndef _ZOLTAN2_ALGND_HPP_ 50 #define _ZOLTAN2_ALGND_HPP_ 69 void buildPartTree(
int level,
int leftPart,
int splitPart,
int rightPart, std::vector<int> &partTree);
87 template <
typename Adapter>
95 typedef typename Adapter::part_t part_t;
97 typedef typename Adapter::lno_t lno_t;
98 typedef typename Adapter::gno_t gno_t;
101 const RCP<const Environment> mEnv;
102 const RCP<const Comm<int> > mProblemComm;
105 const RCP<GraphModel<typename Adapter::base_adapter_t> > mGraphModel;
107 const RCP<CoordinateModel<typename Adapter::base_adapter_t> > mIds;
111 const RCP<const typename Adapter::base_adapter_t> mBaseInputAdapter;
113 void getBoundLayer(
int levelIndx,
const std::vector<part_t> &partMap,
114 const part_t * parts,
115 const std::set<int> &excVerts,
116 int &bigraphNumS,
int &bigraphNumT,
int &bigraphNumE,
117 std::vector<int> &bigraphCRSRowPtr, std::vector<int> &bigraphCRSCols,
118 std::vector<int> &bigraphVMapU, std::vector<int> &bigraphVMapV);
123 AlgND(
const RCP<const Environment> &env_,
124 const RCP<
const Comm<int> > &problemComm_,
127 const RCP<const typename Adapter::base_adapter_t> baseInputAdapter_
129 :mEnv(env_), mProblemComm(problemComm_), mGraphModel(gModel_),
130 mIds(cModel_), mBaseInputAdapter(baseInputAdapter_)
132 #ifndef INCLUDE_ZOLTAN2_EXPERIMENTAL 136 #ifndef INCLUDE_ZOLTAN2_EXPERIMENTAL_WOLF 140 if(mProblemComm->getSize()!=1)
155 template <
typename Adapter>
169 RCP<PartitioningSolution<Adapter> > partSoln;
172 std::cout <<
"HERE1" << std::endl;
179 std::cout <<
"HERE2" << std::endl;
183 std::cout <<
"HERE3" << std::endl;
186 size_t numGlobalParts = partSoln->getTargetGlobalNumberOfParts();
188 const part_t *parts = partSoln->getPartListView();
204 std::cout <<
"HERE4" << std::endl;
207 std::vector<int> partTree;
209 buildPartTree( 0, 0, (numGlobalParts-1)/2 + 1, numGlobalParts, partTree);
210 unsigned int numSeparators = partTree.size() / 4;
212 for(
unsigned int i=0;i<partTree.size(); i++)
214 std::cout <<
"partTree: " << partTree[i] << std::endl;
216 std::cout <<
"NumSeparators: " << numSeparators << std::endl;
218 std::cout <<
"HERE5" << std::endl;
228 std::cout <<
"HERE6" << std::endl;
231 int numLevels = partTree[4*(numSeparators-1)]+1;
233 std::vector<std::vector<int> > partLevelMap(numLevels,std::vector<int>(numGlobalParts));
235 std::vector<int> sepsInLev(numLevels,0);
237 for(
unsigned int i=0;i<numSeparators;i++)
239 int level = partTree[4*i];
240 int leftPart = partTree[4*i+1];
241 int splitPart = partTree[4*i+2];
242 int rightPart = partTree[4*i+3];
244 for(
int part=leftPart; part<splitPart; part++)
246 partLevelMap[level][part] = 2*sepsInLev[level];
249 for(
int part=splitPart; part<rightPart; part++)
251 partLevelMap[level][part] = 2*sepsInLev[level]+1;
257 std::cout <<
"partLevelMap[0][0] = " << partLevelMap[0][0] << std::endl;
258 std::cout <<
"partLevelMap[0][1] = " << partLevelMap[0][1] << std::endl;
260 std::cout <<
"HERE7" << std::endl;
267 const std::set<int> sepVerts;
274 std::cout <<
"HERE8" << std::endl;
276 for(
unsigned int level=0;level<numLevels;level++)
278 for(
unsigned int levIndx=0;levIndx<sepsInLev[level];levIndx++)
283 std::cout <<
"HERE9" << std::endl;
285 int bigraphNumU=0, bigraphNumV=0, bigraphNumE=0;
286 std::vector<int> bigraphVMapU;
287 std::vector<int> bigraphVMapV;
289 std::vector<int> bigraphCRSRowPtr;
290 std::vector<int> bigraphCRSCols;
293 getBoundLayer(levIndx, partLevelMap[level], parts, sepVerts,
294 bigraphNumU,bigraphNumV,bigraphNumE,
295 bigraphCRSRowPtr, bigraphCRSCols,
296 bigraphVMapU,bigraphVMapV);
298 std::cout <<
"Bipartite graph: " << bigraphNumU <<
" " << bigraphNumV <<
" " 299 << bigraphNumE << std::endl;
301 for (
unsigned int i=0;i<bigraphVMapU.size();i++)
303 std::cout <<
"boundVertU: " << bigraphVMapU[i] << std::endl;
306 for (
unsigned int i=0;i<bigraphVMapV.size();i++)
308 std::cout <<
"boundVertV: " << bigraphVMapV[i] << std::endl;
313 for (
int rownum=0;rownum<bigraphNumU;rownum++)
316 for (
int eIdx=bigraphCRSRowPtr[rownum];eIdx<bigraphCRSRowPtr[rownum+1];eIdx++)
318 std::cout <<
"bipartite E: " << bigraphVMapU[rownum] <<
", " << bigraphVMapV[ bigraphCRSCols[eIdx]]
319 <<
" ( " << rownum <<
"," << bigraphCRSCols[eIdx] <<
" )" << std::endl;
323 std::cout <<
"HERE10" << std::endl;
329 Matcher bpMatch(bigraphCRSRowPtr.data(), bigraphCRSCols.data(), bigraphNumU, bigraphNumV, bigraphNumE);
332 const std::vector<int> &vertUMatches = bpMatch.getVertexUMatches();
333 const std::vector<int> &vertVMatches = bpMatch.getVertexVMatches();
342 bigraphVMapU,bigraphVMapV,VC);
344 for(
unsigned int i=0;i<VC.size();i++)
346 std::cout <<
"VC: " << VC[i] << std::endl;
355 std::cout <<
"HERE20" << std::endl;
374 template <
typename Adapter>
376 const part_t * parts,
377 const std::set<int> &excVerts,
378 int &bigraphNumS,
int &bigraphNumT,
int &bigraphNumE,
379 std::vector<int> &bigraphCRSRowPtr, std::vector<int> &bigraphCRSCols,
380 std::vector<int> &bigraphVMapS, std::vector<int> &bigraphVMapT)
382 std::cout <<
"HI1" << std::endl;
384 typedef typename Adapter::lno_t lno_t;
385 typedef typename Adapter::scalar_t scalar_t;
388 int numVerts = mGraphModel->getLocalNumVertices();
391 ArrayView< const lno_t > eIDs;
392 ArrayView< const lno_t > vOffsets;
393 ArrayView< input_t > wgts;
402 std::map<int,std::set<int> > bigraphEs;
408 for(
int v1=0;v1<numVerts;v1++)
411 part_t vpart1 = partMap[parts[v1]];
413 bool correctBL = (vpart1 >= 2*levelIndx && vpart1 < 2*(levelIndx+1) );
423 if(excVerts.find(v1)!=excVerts.end())
430 for(
int j=vOffsets[v1];j<vOffsets[v1+1];j++)
435 part_t vpart2 = partMap[parts[v2]];
437 correctBL = (vpart2 >= 2*levelIndx && vpart2 < 2*(levelIndx+1) );
447 if(excVerts.find(v2)!=excVerts.end())
452 if ( vpart1 != vpart2 )
460 if(bigraphEs.find(v1)==bigraphEs.end())
462 bigraphEs[v1] = std::set<int>();
464 bigraphEs[v1].insert(v2);
481 bigraphNumS = vSetS.
size();
482 bigraphNumT = vSetT.size();
488 bigraphVMapS.resize(bigraphNumS);
490 std::map<int,int> glob2LocTMap;
493 for(std::set<int>::const_iterator iter=vSetS.begin(); iter!=vSetS.end(); ++iter)
495 bigraphVMapS[indx] = *iter;
500 bigraphVMapT.resize(bigraphNumT);
502 for(std::set<int>::const_iterator iter=vSetT.begin();iter!=vSetT.end();++iter)
504 bigraphVMapT[indx] = *iter;
505 glob2LocTMap[*iter]=indx;
514 bigraphCRSRowPtr.resize(bigraphNumS+1);
515 bigraphCRSCols.resize(bigraphNumE);
521 bigraphCRSRowPtr[0]=0;
523 unsigned int rownum=0;
524 unsigned int nzIndx=0;
525 std::map<int,std::set<int> >::const_iterator iterM;
526 for (iterM=bigraphEs.begin();iterM!=bigraphEs.end();++iterM)
528 bigraphCRSRowPtr[rownum+1] = bigraphCRSRowPtr[rownum] + (*iterM).second.size();
530 for(std::set<int>::const_iterator iter=(*iterM).second.begin(); iter!=(*iterM).second.end(); ++iter)
532 bigraphCRSCols[nzIndx] = glob2LocTMap[(*iter)];
649 void buildPartTree(
int level,
int leftPart,
int splitPart,
int rightPart, std::vector<int> &partTree)
652 partTree.push_back(level);
653 partTree.push_back(leftPart);
654 partTree.push_back(splitPart);
655 partTree.push_back(rightPart);
658 if(splitPart-leftPart > 1)
660 int newSplit = leftPart+(splitPart-leftPart-1)/2 + 1;
665 if(rightPart-splitPart>1)
667 int newSplit = splitPart+(rightPart-splitPart-1)/2 + 1;
668 buildPartTree(level+1,splitPart,newSplit,rightPart,partTree);
void getVCfromMatching(const std::vector< int > &bigraphCRSRowPtr, std::vector< int > &bigraphCRSCols, const std::vector< int > &vertUMatches, const std::vector< int > &vertVMatches, const std::vector< int > &bigraphVMapU, const std::vector< int > &bigraphVMapV, std::vector< int > &VC)
int match()
Computes the maximum cardinality matching.
#define Z2_THROW_SERIAL(mystr)
Throw an error when code is run on more than one processor.
#define Z2_THROW_EXPERIMENTAL_WOLF(mystr)
Throw an error when wolf experimental code is requested but not compiled.
interface to the Zoltan package
Defines the PartitioningSolution class.
An implementation of the Matcher interface that operates on Epetra matrices and Graphs.
sub-steps, each method's entry and exit
This class provides geometric coordinates with optional weights to the Zoltan2 algorithm.
void partition(const RCP< PartitioningSolution< Adapter > > &solution)
Partitioning method.
Defines the IdentifierModel interface.
void buildPartTree(int level, int leftPart, int splitPart, int rightPart, std::vector< int > &partTree)
A PartitioningSolution is a solution to a partitioning problem.
The StridedData class manages lists of weights or coordinates.
lno_t size() const
Return the length of the strided array.
Algorithm defines the base class for all algorithms.
#define Z2_THROW_EXPERIMENTAL(mystr)
Throw an error when experimental code is requested but not compiled.
GraphModel defines the interface required for graph models.
AlgND(const RCP< const Environment > &env_, const RCP< const Comm< int > > &problemComm_, const RCP< GraphModel< typename Adapter::base_adapter_t > > &gModel_, const RCP< CoordinateModel< typename Adapter::base_adapter_t > > &cModel_, const RCP< const typename Adapter::base_adapter_t > baseInputAdapter_)
The class containing ordering solutions.
int order(const RCP< OrderingSolution< lno_t, gno_t > > &solution_)
Ordering method.