Zoltan2
Loading...
Searching...
No Matches
Zoltan2_MatcherHelper.hpp
Go to the documentation of this file.
1#ifndef _ZOLTAN2_MatcherHelper_hpp_
2#define _ZOLTAN2_MatcherHelper_hpp_
3
4//#define _ZOLTAN2_MatcherHelper_hpp_
5
6
7#ifdef ZOLTAN2ND_HAVE_OMP
8#include <omp.h>
9#endif
10
11#include <iostream>
12#include <fstream>
13#include <string>
14#include <vector>
15#include <algorithm>
16#include <cstdlib>
17#include <set>
18#include <queue>
19#include <cassert>
20
21// PPF Matching code copied from Isorropia. Siva has reservations about algorithm
22// robustness. It uses recursion, which can cause problems on the stack.
23// Probably should rewrite at least some of these algorithms, eventually.
24
25
26namespace Zoltan2 {
27
37
38
39template <typename LO>
40class Matcher
41{
42private:
43
44 LO *mCRS_rowPtrs;
45 LO *mCRS_cols;
46
47 // Number of vertices in u set (num row vertices)
48 LO numU;
49
50 // Number of vertices in v set (num col vertices)
51 LO numV;
52
53 // For each u vertex, the matching v vertex
54 std::vector<LO> matchedVertexForU;
55
56 // For each v vertex, the matching u vertex
57 std::vector<LO> matchedVertexForV;
58
59 std::vector<LO> queue;
60 LO* LV_;
61 LO* LU_;
62 LO* unmatchedU_;
63 LO *parent_;
64 LO *lookahead_;
65 bool finish_;
66 LO numE,avgDegU_,k_star_,icm_,BFSInd_,numThread_,Qst_,Qend_,numMatched;
67
68 LO *visitedV_;
69
70 void delete_matched_v();
71 LO SGM();
72 LO match_dfs();
73 LO match_hk();
74 LO construct_layered_graph();
75 LO find_set_del_M();
76 LO recursive_path_finder(LO, LO);
77 LO dfs_path_finder(LO);
78 LO dfs_augment();
79 LO augment_matching(LO);
80 LO DW_phase();
81
82public:
90 Matcher(LO *_rowPtr, LO *_cols, LO _numU, LO _numV, LO _numE);
91
92
93
94
98 virtual ~Matcher();
99
100 /* @ingroup matching_grp
101 Returns the number of matched vertices from Maximum Cardinality
102 Matching set
103 */
105 {
106 LO count=0;
107 for(unsigned int i=0;i<matchedVertexForU.size(); i++)
108 {
109 if(matchedVertexForU[i]!=-1)
110 {
111 count++;
112 }
113 }
114 return count;
115 }
116
117
118
119 const std::vector<LO> &getVertexUMatches() {return matchedVertexForU;};
120 const std::vector<LO> &getVertexVMatches() {return matchedVertexForV;};
121
122
123 // Perhaps should be moved outside of class eventually or reworked to use internal variables
124 void getVCfromMatching(const std::vector<LO> &bigraphCRSRowPtr,
125 std::vector<LO> &bigraphCRSCols,
126 const std::vector<LO> &vertUMatches,
127 const std::vector<LO> &vertVMatches,
128 const std::vector<LO> &bigraphVMapU,
129 const std::vector<LO> &bigraphVMapV,
130 std::vector<LO> &VC);
131
132
136 LO match();
137};
139
142template <typename LO>
143Matcher<LO>::Matcher(LO *_rowPtr, LO *_cols, LO _numU, LO _numV, LO _numE)
144 :mCRS_rowPtrs(_rowPtr),mCRS_cols(_cols),numU(_numU),numV(_numV),numE(_numE)
145{
146 finish_=false;
147 avgDegU_=numE/numU+1;
148 matchedVertexForU.resize(numU);
149 matchedVertexForV.resize(numV);
150
151 lookahead_=new LO[numU];
152 unmatchedU_=new LO[numU];
153
154 for(LO i=0;i<numU;i++)
155 {
156 matchedVertexForU[i]=-1;
157
158 lookahead_[i]=mCRS_rowPtrs[i];
159 unmatchedU_[i]=i;
160 }
161
162 visitedV_=new LO[numV];
163
164 parent_=new LO[numV];
165
166 for(LO i=0;i<numV;i++)
167 {
168 visitedV_[i]=0;
169
170 matchedVertexForV[i]=-1;
171 parent_[i]=-1;
172 }
173
174 numThread_=1;
175}
177
178
181template <typename LO>
183{
184 delete [] lookahead_;
185 delete [] unmatchedU_;
186
187 if (parent_)
188 {
189 delete [] parent_; parent_ = NULL;
190 }
191
192 if(visitedV_)
193 {
194 delete [] visitedV_;
195 }
196
197}
199
201// This function increases the matching size by one with the help of a
202// augmenting path. The input is an integer which is the id of the last
203// columns vertex of the augmenting path. We trace the whole path by
204// backtraking using parent array. while tracing back we flip the unmatched
205// edges to matched edges.
207template <typename LO>
209{
210 LO u,v,t,lnt=1;
211 v=tv;
212 while(true)
213 {
214 u=parent_[v];
215 t=matchedVertexForU[u];
216 matchedVertexForV[v]=u;
217 matchedVertexForU[u]=v;
218 if(t==-1)
219 break;
220 lnt+=2;
221 v=t;
222 }
223
224 return lnt;
225}
227
229// This function is almost similar to the previous function which is to find
230// a vertex disjoint path. It is used for the algorithm DFS, PPF and in HKDW. The
231// difference is that this function operates on the original graph not on the
232// layerd subgraph. It also does the incorporates the lookahead mechanism and
233// scanning adjacency list alternately from backward and from forward in
234// alternate iterations for PPF and HKDW.
236template <typename LO>
237LO Matcher<LO>::dfs_path_finder(LO u)
238{
239 LO i,ind=-1,res=0;
240
241 for(i=lookahead_[u];i<mCRS_rowPtrs[u+1];i++) // the lookahead scheme
242 {
243 ind=mCRS_cols[i];
244 assert(ind>=0 && ind<numV);
245 if(matchedVertexForV[ind]==-1)
246 {
247 LO lock2=0;
248 if (visitedV_[ind]==0)
249 {
250 visitedV_[ind]=1;
251 lock2=1;
252 }
253
254 if(lock2>0)
255 {
256 parent_[ind]=u;
257 lookahead_[u]=i+1;
258 return ind;
259 }
260 }
261 }
262
263
264 if(icm_%2==1) // odd number iteration so scan the adj list forward dir
265 {
266 for(i=mCRS_rowPtrs[u];i<mCRS_rowPtrs[u+1];i++)
267 {
268 ind=mCRS_cols[i];
269 assert(ind>=0 && ind<numV);
270
271 LO lock2=0;
272 if (visitedV_[ind]==0)
273 {
274 visitedV_[ind]=1;
275 lock2=1;
276 }
277
278 if(lock2>0)
279 {
280 parent_[ind]=u;
281 res=dfs_path_finder(matchedVertexForV[ind]);
282 if(res!=-1)
283 return res;
284 }
285 }
286 }
287 else // even number iteration so scan from backward
288 {
289 for(i=mCRS_rowPtrs[u+1]-1;i>=mCRS_rowPtrs[u];i--)
290 {
291 ind=mCRS_cols[i];
292 assert(ind>=0 && ind<numV);
293
294
295 LO lock2=0;
296 if (visitedV_[ind]==0)
297 {
298 visitedV_[ind]=1;
299 lock2=1;
300 }
301
302 if(lock2>0)
303 {
304 parent_[ind]=u;
305 res=dfs_path_finder(matchedVertexForV[ind]);
306 if(res!=-1)
307 return res;
308 }
309 }
310 }
311
312
313 return -1;
314}
316
317// ////////////////////////////////////////////////////////////////////////////////
318// // This function starts the BFS phase for the HK and HKDW. It starts from the
319// // layer 0 vertices and tries to find a vertex disjoint path from each of
320// // these vertices.
321// ////////////////////////////////////////////////////////////////////////////////
322// int Matcher::find_set_del_M()
323// {
324
325// int i,j,count=0;
326// delete_matched_v();
327
328// #ifdef ZOLTAN2ND_HAVE_OMP
329// #pragma omp parallel for private(j)
330// #endif
331// for(i=0;i<BFSInd_;i++)
332// {
333
334// j=recursive_path_finder(0,queue[i]);
335// if(j!=-1)
336// {
337// augment_matching(j);
338
339// //MMW: Not 100% this is necessary, let this in just in case bug in original code
340// #ifdef ZOLTAN2ND_HAVE_OMP
341// #pragma omp atomic
342// #endif
343// count++;
344
345
346
347// }
348
349// }
350// return count;
351// }
352// ////////////////////////////////////////////////////////////////////////////////
353
354// ////////////////////////////////////////////////////////////////////////////////
355// // This is the additional Duff and Wiberg phase for the HKDW. This function
356// // does nothing but first unset the locks and then runs PPF from the
357// // remaining unmatched row vertices after the BFS phase of HK.
358// ////////////////////////////////////////////////////////////////////////////////
359// int Matcher::DW_phase()
360// {
361// int i,count=0;
362
363// #ifdef ZOLTAN2ND_HAVE_OMP
364// #pragma omp parallel for
365// #endif
366// for(i=0;i<numV;i++)
367// {
368// #ifdef ZOLTAN2ND_HAVE_OMP
369// omp_unset_lock(&scannedV_[i]); // unsetting the locks
370// #endif
371// }
372
373// #ifdef ZOLTAN2ND_HAVE_OMP
374// #pragma omp parallel for
375// #endif
376// for(i=0;i<BFSInd_;i++) // calling the PPF
377// {
378// int u=queue[i];
379// if(matchedVertexForU[u]==-1)
380// {
381// int ind=dfs_path_finder(u);
382// if(ind!=-1)
383// {
384// augment_matching(ind);
385
386// //MMW: Not 100% this is necessary, let this in just in case bug in original code
387// #ifdef ISORROPIA_HAVE_OMP
388// #pragma omp atomic
389// #endif
390// count++;
391
392// }
393// }
394// }
395// return count;
396// }
397// ////////////////////////////////////////////////////////////////////////////////
398
400 //This function is the starter function for PPF and DFS. It unsets the locks
401 //the call dfs_path_finder and then call the augment_matching.
403template <typename LO>
404LO Matcher<LO>::dfs_augment()
405{
406 LO i,flag=0,flag1=0,count=0,totc=0,index=numU,cur=0;
407 icm_=0;
408
409 while(true)
410 {
411 icm_++;
412
413 for(i=0;i<numV;i++)
414 {
415 visitedV_[i]=0;
416 }
417
418 cur=0;
419 for(i=0;i<numU;i++)
420 {
421 if(matchedVertexForU[i]==-1)
422 unmatchedU_[cur++]=i;
423 }
424 index=cur;
425 flag=flag1=count=0;
426
427 for(i=0;i<index;i++)
428 {
429 flag=1;
430 LO u=unmatchedU_[i];
431 LO ind=dfs_path_finder(u);
432 if(ind!=-1)
433 {
434 flag1=1;
435 augment_matching(ind);
436 }
437 }
438
439 if(flag==0 || flag1==0)
440 break;
441 else
442 {
443 cur=0;
444 for(i=0;i<index;i++)
445 {
446 if(matchedVertexForU[unmatchedU_[i]]==-1)
447 unmatchedU_[cur++]=unmatchedU_[i];
448 }
449 index=cur;
450
451 }
452 }
453
454 return totc;
455}
457
458// ////////////////////////////////////////////////////////////////////////////////
459// ////////////////////////////////////////////////////////////////////////////////
460// int Matcher::SGM()
461// {
462// int i,j,lock,ind,count=0;
463// #ifdef ZOLTAN2ND_HAVE_OMP
464// #pragma omp parallel for private(j,ind,lock)
465// #endif
466// for(i=0;i<numU;i++)
467// {
468// for(j=mCRS_rowPtrs[i];j<mCRS_rowPtrs[i+1];j++)
469// {
470// ind=mCRS_cols[j];
471// #ifdef ZOLTAN2ND_HAVE_OMP
472// lock=omp_test_lock(&scannedV_[ind]);
473// #else
474// // mfh 07 Feb 2013: lock wasn't getting initialized if
475// // ZOLTAN2ND_HAVE_OMP was not defined. omp_test_lock()
476// // returns nonzero if the thread successfully acquired the
477// // lock. If there's only one thread, that thread will
478// // always be successful, so the default value of lock
479// // should be nonzero.
480// lock = 1;
481// #endif
482// if(lock>0)
483// {
484// matchedVertexForU[i]=ind;
485// matchedVertexForV[ind]=i;
486// break;
487// }
488// }
489// }
490// return count;
491// }
492// ////////////////////////////////////////////////////////////////////////////////
493
494
497template <typename LO>
498LO Matcher<LO>::SGM()
499{
500 LO i,j,ind,count=0;
501
502 for(i=0;i<numU;i++)
503 {
504 for(j=mCRS_rowPtrs[i];j<mCRS_rowPtrs[i+1];j++)
505 {
506 ind=mCRS_cols[j];
507
508 LO lock2=0;
509 if (visitedV_[ind]==0)
510 {
511 visitedV_[ind]=1;
512 lock2=1;
513 }
514
515 if(lock2>0)
516 {
517 matchedVertexForU[i]=ind;
518 matchedVertexForV[ind]=i;
519 break;
520 }
521 }
522 }
523 return count;
524}
526
527
528
530// Forking function for DFS based algorithm
532template <typename LO>
533LO Matcher<LO>::match_dfs()
534{
535 LO totc=0;
536 icm_=0;
537
538 totc=dfs_augment();
539
540 return totc;
541}
543
546template <typename LO>
548{
549 // User interface function for the matching..
550
551 LO totc=0;
552 totc=SGM();
553 totc+=match_dfs();
554
555 numMatched = totc;
556
557 return 0;
558}
560
561
563// Calculate vertex cover (which is vertex separator) from matching
564// VC = (U-L) union (B intersection L)
565//
566// Let X be the exposed nodes in U (those without a match)
567//
568// E':
569// Matched edges should be directed VtoU -- just use vertVMatches array
570// All other edges should be directed UtoV -- use modified biGraphCRScols
571//
572// L is the set of vertices in (U union V, E') that can be reached from X
573//
574//
575// Perhaps I should use internal class members in this function
576// However, I decided not to do this for now since I'm changing some of these
577// member variables in this function
579template <typename LO>
580void Matcher<LO>::getVCfromMatching(const std::vector<LO> &bigraphCRSRowPtr,
581 std::vector<LO> &bigraphCRSCols,
582 const std::vector<LO> &vertSMatches,
583 const std::vector<LO> &vertTMatches,
584 const std::vector<LO> &bigraphVMapU,
585 const std::vector<LO> &bigraphVMapV,
586 std::vector<LO> &VC)
587{
588 LO numS = vertSMatches.size();
589 LO numT = vertTMatches.size();
590
592 // Build X
594 std::set<LO> X;
595 for(LO i=0;i<numS; i++)
596 {
597 if(vertSMatches[i]==-1)
598 {
599 X.insert(i);
600 }
601 }
603
605 // Non matched edges should be directed UtoV
606 // Removed matches edges from bipartite graph (set to -1)
607 // -- perhaps replace this with something more efficient/compact
609 for (LO uID=0;uID<numS;uID++)
610 {
611 for (LO eIdx=bigraphCRSRowPtr[uID];eIdx<bigraphCRSRowPtr[uID+1];eIdx++)
612 {
613 LO vID = bigraphCRSCols[eIdx];
614
615 if (vertSMatches[uID]==vID)
616 {
617 bigraphCRSCols[eIdx]=-1;
618 }
619 }
620
621 }
623
625 // Calculate L - set of vertices in (U union V, E') that can be reached from X
627 std::set<LO> L;
628
629 std::queue<LO> vqueue;
630
631 std::copy(X.begin(), X.end(), std::inserter( L, L.begin() ) );
632
633
634
635 typename std::set<LO>::const_iterator iter;
636 for(iter = X.begin(); iter != X.end(); ++iter)
637 {
638 L.insert(bigraphVMapU[*iter]); // L contains all vertices in X
639
640 vqueue.push(*iter); // copy on to vqueue
641 }
642
643 LO iteration=0;
644 while(vqueue.size()!=0)
645 {
646 //Number of active vertices on this side of bipartite graph
647 LO nstarts=vqueue.size();
648
649 for (LO i=0; i<nstarts; i++)
650 {
651 LO start = vqueue.front();
652 vqueue.pop();
653
654 //Traverse from U to V
655 if(iteration%2==0)
656 {
657 //Traverse edges starting from vertex "start"
658 for (LO eIdx=bigraphCRSRowPtr[start];eIdx<bigraphCRSRowPtr[start+1];eIdx++)
659 {
660 LO newV = bigraphCRSCols[eIdx];
661
662 //Edge is in correct direction (U to V) => newV is valid
663 if (newV!=-1)
664 {
665 // If this vertex has not been reached
666 if(L.find(bigraphVMapV[newV])==L.end())
667 {
668 L.insert(bigraphVMapV[newV]);
669 vqueue.push(newV);
670 }
671 }
672 }
673
674 }
675
676 //Traverse from V to U
677 else
678 {
679 LO newU = vertTMatches[start];
680
681 // If this vertex has not been reached
682 if(L.find(bigraphVMapU[newU])==L.end())
683 {
684 L.insert(bigraphVMapU[newU]);
685 vqueue.push(newU);
686 }
687 }
688 } // for
689
690 iteration++;
691 } //while
693
695 // Calc VC = (U-L) union (B intersection L)
697 for(LO uID=0;uID<numS;uID++)
698 {
699 // if vertex not in L, it is in VC
700 if(L.find(bigraphVMapU[uID])==L.end())
701 {
702 VC.push_back(bigraphVMapU[uID]);
703 }
704 }
705
706 for(LO vID=0;vID<numT;vID++)
707 {
708 // if vertex is in L, it is in VC
709 if(L.find(bigraphVMapV[vID])!=L.end())
710 {
711 VC.push_back(bigraphVMapV[vID]);
712 }
713 }
715
716
717
718}
720
721
722
723
724
725
726
727
728
729
730
731
732
733} //Zoltan2 namespace
734#endif //ifdef
An implementation of the Matcher interface that operates on Epetra matrices and Graphs.
const std::vector< LO > & getVertexVMatches()
virtual ~Matcher()
Destructor.
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.
Matcher(LO *_rowPtr, LO *_cols, LO _numU, LO _numV, LO _numE)
Constructor.
Created by mbenlioglu on Aug 31, 2020.