1 #ifndef _ZOLTAN2_MatcherHelper_hpp_ 2 #define _ZOLTAN2_MatcherHelper_hpp_ 5 #ifdef ZOLTAN2ND_HAVE_OMP 49 std::vector<int> matchedVertexForU;
52 std::vector<int> matchedVertexForV;
54 std::vector<int> queue;
61 int numE,avgDegU_,k_star_,icm_,BFSInd_,numThread_,Qst_,Qend_,numMatched;
65 void delete_matched_v();
69 int construct_layered_graph();
71 int recursive_path_finder(
int,
int);
72 int dfs_path_finder(
int);
74 int augment_matching(
int);
85 Matcher(
int *_rowPtr,
int *_cols,
int _numU,
int _numV,
int _numE);
102 for(
unsigned int i=0;i<matchedVertexForU.size(); i++)
104 if(matchedVertexForU[i]!=-1)
127 :mCRS_rowPtrs(_rowPtr),mCRS_cols(_cols),numU(_numU),numV(_numV),numE(_numE)
130 avgDegU_=numE/numU+1;
131 matchedVertexForU.resize(numU);
132 matchedVertexForV.resize(numV);
134 lookahead_=
new int[numU];
135 unmatchedU_=
new int[numU];
137 for(
int i=0;i<numU;i++)
139 matchedVertexForU[i]=-1;
141 lookahead_[i]=mCRS_rowPtrs[i];
145 visitedV_=
new int[numV];
147 parent_=
new int[numV];
149 for(
int i=0;i<numV;i++)
153 matchedVertexForV[i]=-1;
166 delete [] lookahead_;
167 delete [] unmatchedU_;
169 if (parent_)
delete [] parent_; parent_ = NULL;
186 int Matcher::augment_matching(
int tv)
193 t=matchedVertexForU[u];
194 matchedVertexForV[v]=u;
195 matchedVertexForU[u]=v;
214 int Matcher::dfs_path_finder(
int u)
218 for(i=lookahead_[u];i<mCRS_rowPtrs[u+1];i++)
221 assert(ind>=0 && ind<numV);
222 if(matchedVertexForV[ind]==-1)
225 if (visitedV_[ind]==0)
243 for(i=mCRS_rowPtrs[u];i<mCRS_rowPtrs[u+1];i++)
246 assert(ind>=0 && ind<numV);
249 if (visitedV_[ind]==0)
258 res=dfs_path_finder(matchedVertexForV[ind]);
266 for(i=mCRS_rowPtrs[u+1]-1;i>=mCRS_rowPtrs[u];i--)
269 assert(ind>=0 && ind<numV);
273 if (visitedV_[ind]==0)
282 res=dfs_path_finder(matchedVertexForV[ind]);
380 int Matcher::dfs_augment()
382 int i,flag=0,flag1=0,count=0,totc=0,index=numU,cur=0;
397 if(matchedVertexForU[i]==-1)
398 unmatchedU_[cur++]=i;
406 int u=unmatchedU_[i];
407 int ind=dfs_path_finder(u);
411 augment_matching(ind);
415 if(flag==0 || flag1==0)
422 if(matchedVertexForU[unmatchedU_[i]]==-1)
423 unmatchedU_[cur++]=unmatchedU_[i];
479 for(j=mCRS_rowPtrs[i];j<mCRS_rowPtrs[i+1];j++)
484 if (visitedV_[ind]==0)
492 matchedVertexForU[i]=ind;
493 matchedVertexForV[ind]=i;
507 int Matcher::match_dfs()
553 std::vector<int> &bigraphCRSCols,
554 const std::vector<int> &vertUMatches,
555 const std::vector<int> &vertVMatches,
556 const std::vector<int> &bigraphVMapU,
557 const std::vector<int> &bigraphVMapV,
558 std::vector<int> &VC)
560 int numU = vertUMatches.size();
561 int numV = vertVMatches.size();
567 for(
int i=0;i<numU; i++)
569 if(vertUMatches[i]==-1)
581 for (
int uID=0;uID<numU;uID++)
583 for (
int eIdx=bigraphCRSRowPtr[uID];eIdx<bigraphCRSRowPtr[uID+1];eIdx++)
585 int vID = bigraphCRSCols[eIdx];
587 if (vertUMatches[uID]==vID)
589 bigraphCRSCols[eIdx]=-1;
601 std::queue<int> queue;
603 std::copy(X.begin(), X.end(), std::inserter( L, L.begin() ) );
605 for(std::set<int>::const_iterator iter = X.begin(); iter != X.end(); ++iter)
607 L.insert(bigraphVMapU[*iter]);
613 while(queue.size()!=0)
616 int nstarts=queue.size();
618 for (
int i=0; i<nstarts; i++)
620 int start = queue.front();
627 for (
int eIdx=bigraphCRSRowPtr[start];eIdx<bigraphCRSRowPtr[start+1];eIdx++)
629 int newV = bigraphCRSCols[eIdx];
635 if(L.find(bigraphVMapV[newV])==L.end())
637 L.insert(bigraphVMapV[newV]);
648 int newU = vertVMatches[start];
651 if(L.find(bigraphVMapU[newU])==L.end())
653 L.insert(bigraphVMapU[newU]);
666 for(
int uID=0;uID<numU;uID++)
669 if(L.find(bigraphVMapU[uID])==L.end())
671 VC.push_back(bigraphVMapU[uID]);
675 for(
int vID=0;vID<numV;vID++)
678 if(L.find(bigraphVMapV[vID])!=L.end())
680 VC.push_back(bigraphVMapV[vID]);
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.
const std::vector< int > & getVertexVMatches()
virtual ~Matcher()
Destructor.
Matcher(int *_rowPtr, int *_cols, int _numU, int _numV, int _numE)
Constructor.
const std::vector< int > & getVertexUMatches()
int getNumberOfMatchedVertices()