RecBipartLB: ldb strategy using recursive bipartition
[charm.git] / src / ck-ldb / RecBipartLB.C
1 /** \file RecBipartLB.C
2  *  Author: Swapnil Ghike
3  *  Date Created: 
4  *  E-mail: ghike2@illinois.edu
5  *
6  *  This strategy does a recursive bipartition of the object graph and the
7  *  processor graph. The objects are divided based on the loads in case of odd
8  *  number of processors. Recursive bi-partitioning is done by a breadth-first
9  *  traversal until you have the required load in one group.
10  *
11  * 
12  *  At each recursive biparititioning, the boundaries are refined to minimize
13  *  the edge cut. Vertices are moved across the boundary to see if the edge cut
14  *  reduces while trying to maintain proportionate load in both partitions.
15  */
16
17 /**
18  *  \addtogroup CkLdb
19  */
20
21 /*@{*/
22 using namespace std;
23
24 #include <limits.h>
25 #include <math.h>
26 #include <queue>
27 #include <vector>
28 #include "ckgraph.h"
29 #include "RecBipartLB.h"
30
31 void RecursiveBiPart(ObjGraph *, vector<Vertex *> & ,int, int);
32 void adjustqueues(ObjGraph *, BQueue *, BQueue *, vector<Vertex *> &, vector<Vertex *> &,int *, int);
33 void adjustgain(ObjGraph *,vector<Vertex *> &,BQueue *);
34 void RefineBoundary(ObjGraph *, vector<Vertex *> &, vector<Vertex *> &,BQueue *, BQueue *, int, int, int, double, double, double);
35 int modifypartitions(ObjGraph *,vector<Vertex *> &, vector<Vertex *> &, BQueue *, BQueue *, int, int);
36 void swapQ1toQ2(ObjGraph *, BQueue *, BQueue *, int);
37 Vertex * removeinSwap(ObjGraph *,BQueue *, BQueue *, int);
38 Vertex * removePtr(vector<Vertex *> &,int);
39
40 int level;
41 double TOTALLOAD;
42 vector<Vertex_helper *> vhelpers;
43 int numparts, peno;
44 ProcArray *parray;
45
46 CreateLBFunc_Def(RecBipartLB, "Algorithm for load balacing based on recursive bipartitioning of object graph")
47
48 //removes from BQueue but not from boundaryline
49 void BQueue::removeToSwap(Vertex *vert)
50 {
51   int i;
52   int v=vert->getVertexId();
53   for(i=0;i<q.size();i++)
54   {
55     if(q[i]==v)
56     {
57       //boundaryline and edgestopart1, edgestopart2 are left as they were since this vertex only swaps boundarylines
58       q[i]=q.back();
59       q.pop_back();
60       return;
61     }
62   }
63 }
64
65 //completely removes from the BQueue as well as from both boundarylines
66 void BQueue::removeComplete(Vertex *vert)
67 {        
68   int i;
69   int v=vert->getVertexId();
70   for(i=0;i<q.size();i++)
71   {
72     if(q[i]==v)
73     {
74       vhelpers[v]->setBoundaryline(false);
75       vhelpers[v]->setEdgestopart1(0);
76       vhelpers[v]->setEdgestopart2(0);
77       q[i]=q.back();
78       q.pop_back();
79       return;
80     }
81   }
82 }
83
84 void BQueue::push(Vertex *vert)
85 {
86   int v=vert->getVertexId();
87   q.push_back(v);
88   vhelpers[v]->setBoundaryline(true);
89 }
90
91
92 RecBipartLB::RecBipartLB(const CkLBOptions &opt) : CentralLB(opt) {
93   lbname = "RecBipartLB";
94   if(CkMyPe() == 0)
95     CkPrintf("RecBipartLB created\n");
96 }
97
98 CmiBool RecBipartLB::QueryBalanceNow(int _step) {
99   return CmiTrue;
100 }
101
102 void RecBipartLB::work(LDStats *stats) {
103   vector<Vertex *> ptrvector;
104   /** ========================== INITIALIZATION ============================= */
105   ProcArray *parr = new ProcArray(stats);       // Processor Array
106   ObjGraph *ogr = new ObjGraph(stats);          // Object Graph
107
108
109   /** ============================= STRATEGY ================================ */
110   level=0;
111   peno=0;
112   TOTALLOAD=0;
113   numparts=CkNumPes();
114   parray=parr;
115
116   double avgLoad = parr->getAverageLoad();
117   int numPes = parr->procs.size();
118
119   parr->resetTotalLoad();
120   for(int i=0;i<ogr->vertices.size();i++)
121   {
122     Vertex_helper *helper = new Vertex_helper();
123     vhelpers.push_back(helper);
124     ptrvector.push_back((Vertex *)&(ogr->vertices[i]));
125
126   }
127
128   RecursiveBiPart(ogr,ptrvector,1,numparts);
129
130   /** ============================== CLEANUP ================================ */
131   ogr->convertDecisions(stats);         // Send decisions back to LDStats
132 }
133
134 /* Function that performs Recursive bipartitioning of the object graph.*/
135 void RecursiveBiPart(ObjGraph *ogr, vector<Vertex *> &pvertices, int parent, int nump)
136 {
137   //if the number of processors that this call has to deal with is 1, dont recurse any further
138   if(nump==1)
139   {
140     parray->procs[peno].setTotalLoad(0);
141     for(int i=0;i<pvertices.size();i++)
142     {
143       pvertices[i]->setNewPe(peno);
144       parray->procs[peno].setTotalLoad(parray->procs[peno].getTotalLoad() + pvertices[i]->getVertexLoad());
145     }
146     peno++;
147
148     return;
149   }
150
151   int numerator=nump/2;
152   double ratio = ((double)numerator/nump);//(ratio=floor of nump/2 divided by nump) This is equal to half if nump is even
153
154   //if you have only one vertex in the parent partition, just map it to the appropriate processor
155   if(pvertices.size()==1)
156   {
157     level++;    
158     RecursiveBiPart(ogr,pvertices,2*parent-1,numerator);//nump =6 =>numerator =3, nump =7=>numertaor =3
159     level--;
160     return;
161   }
162
163   //child partitions
164   vector<Vertex *> partition1;
165   vector<Vertex *> partition2;
166   bool *taken=(bool *)malloc(vhelpers.size()*sizeof(bool));
167
168   for(int i=0;i<vhelpers.size();i++)
169     taken[i]=false;
170   int start = pvertices[0]->getVertexId();
171   int nextPe = 0, count=0, n=0;
172   double loadseen=0;
173   double pload=0;
174   bool getout=false;
175   std::queue<int> que2;
176   std::queue<int> que1;
177   int KLFMruns=pvertices.size()/5;
178
179   //initialize from the parent partition
180   for(int i=0;i<pvertices.size();i++){
181     int id=pvertices[i]->getVertexId();
182     vhelpers[id]->setPartition(2*parent);
183     vhelpers[id]->setMarked(false);
184     vhelpers[id]->setBoundaryline(false);
185     vhelpers[id]->setEdgestopart2(0);
186     vhelpers[id]->setEdgestopart1(0);
187     vhelpers[id]->setLevel(level);
188     pload+=ogr->vertices[id].getVertexLoad();
189   }
190
191   // start at vertex with id 0
192   que2.push(start);
193   vhelpers[start]->setMarked(true);
194
195   int i, nbr, lastforced=0;
196   int visitcount=0;
197
198   bool swap=true;
199   int ei=-1;
200   // breadth first traversal
201   while(!que2.empty() && !getout) {
202     int n = que2.front();
203     que2.pop();
204     count++;
205
206     Vertex *v=(Vertex *)&(ogr->vertices[n]);
207     loadseen+=v->getVertexLoad();
208
209     vhelpers[v->getVertexId()]->setPartition(2*parent-1);//vertices in que2 are in the other partition
210
211     partition1.push_back(v);
212     taken[v->getVertexId()]=true;
213
214     //this case is useful if the last remaining vertex is way too large/heavy
215     if(count==pvertices.size()-1)
216       break;
217
218     //visit neighbors of a vertex
219     while(1) {
220       ei++;
221       if(swap==true && ei==v->sendToList.size())
222       { swap=false; ei=0;}
223
224       if(swap==false && ei==v->recvFromList.size())
225       {swap=true; ei=-1;  break;}
226
227       if(swap)
228         nbr = v->sendToList[ei].getNeighborId();
229       else
230         nbr=v->recvFromList[ei].getNeighborId();
231
232       Vertex_helper *u=(vhelpers[nbr]);
233       visitcount++;
234
235       //not all neighbos of v belong to the parent partition
236       if((u->getMarked()==false) && (u->getPartition()==2*parent) && (u->getLevel()==level)){
237         que2.push(nbr);
238         u->setMarked(true);
239
240       }//end of if
241     }//end of while(1)loop
242
243     //if you have visited enough vertices, stop Breadth First traversal
244     if(loadseen>=(ratio*pload))//if nump is even, ratio=1/2, if nump is odd say 7, ratio = 3/7. 1st rec call will have nump =3 and second nump = 4
245     {
246       getout=true;
247     }
248     else{
249       //if the parent partition is disconnected (likely to happen down the recursion tree), force a vertex in BFS
250       if(que2.empty())
251       {
252         for(int i=lastforced;i<pvertices.size();i++)
253         {
254           Vertex *w=pvertices[i];
255           if(taken[w->getVertexId()]==false)
256           {
257             que2.push(w->getVertexId());
258             vhelpers[w->getVertexId()]->setMarked(true);
259             lastforced=i+1;
260             break;
261           }             
262         }
263       }
264     }
265   } // end of while loop
266
267
268   for(int i=0;i<pvertices.size();i++){
269     Vertex *v=pvertices[i];
270     if(taken[v->getVertexId()]==false)
271       partition2.push_back(v);
272   }
273
274   delete[] taken;
275
276   int initialedgecut;
277
278   //Boundaries in respective child partitions, they are really vectors though the name says BQueue
279   BQueue *q1=new BQueue(1);
280   BQueue *q2=new BQueue(2);
281   int tempsize=que2.size();
282
283   for(i=0;i<tempsize;i++)
284   {
285     q2->push((Vertex *)&(ogr->vertices[que2.front()]));//also sets boundaryline=true for each vertex
286     que2.pop();
287   }
288   adjustqueues(ogr,q1,q2,partition1, partition2, &initialedgecut,parent);//adjusts initial queues and gains, edgecut
289
290   RefineBoundary(ogr,partition1,partition2,q1,q2,KLFMruns,initialedgecut,parent,loadseen,pload-loadseen,ratio);//iteratively modified queues and gains, edgecuts
291
292   //level must be incremented/decremented here
293   level++;
294   RecursiveBiPart(ogr,partition1,vhelpers[partition1[0]->getVertexId()]->getPartition(),numerator);//nump =6 =>numerator =3, nump =7=>numertaor =3
295   RecursiveBiPart(ogr,partition2,vhelpers[partition2[0]->getVertexId()]->getPartition(), nump-numerator);//nump=6=>nump-numerator=3, nump=7=>nump-numerator=4
296   level--;
297 }
298
299 //Fills in que1, que2 and adjusts their gains, calculates initial edgecut before KLFM
300 void adjustqueues(ObjGraph *ogr, BQueue *que1, BQueue *que2, vector <Vertex *> &partition1, vector<Vertex *> &partition2, int *initialedgecut, int parent)
301 {
302   int i,j,uid,wid;
303   bool swap=true;
304   int ei=-1;
305   Edge *edge;
306   int edgecut=0;
307   que2->setMingain(INT_MAX);
308   que2->setVertextoswap(-1);
309   que2->setSwapid(-1);
310
311   //This loop fills in que1 and adjusts gain of que2
312   for(i=0;i<que2->q.size();i++)//for each vertex v in que2
313   {
314     int vid=que2->q[i];
315     Vertex *v=((Vertex *)&(ogr->vertices[vid]));
316
317     while(1) {
318       ei++;
319       if(swap==true && ei==v->sendToList.size())
320       { swap=false; ei=0;}
321
322       if(swap==false && ei==v->recvFromList.size())
323       { swap=true; ei=-1; break;}
324
325       if(swap)
326       {
327         uid = v->sendToList[ei].getNeighborId();
328         edge=(Edge *)&(v->sendToList[ei]);
329       }
330       else
331       {
332         uid = v->recvFromList[ei].getNeighborId();
333         edge = (Edge *)&(v->recvFromList[ei]);
334       }
335
336       Vertex *u =(Vertex *)&(ogr->vertices[uid]);
337
338       if((vhelpers[uid]->getPartition())==(2*parent-1) && (vhelpers[uid]->getLevel())==level)//since v is on boundaryline2, its every neighbour in part1 is on boundaryline1
339       {
340         //if not already added to que1
341         if(vhelpers[uid]->getBoundaryline()==false)
342         {
343           que1->push(u);//also sets boundaryline=true
344         }
345
346         //calculate edgecut
347         edgecut+=edge->getNumBytes();
348         vhelpers[vid]->incEdgestopart1(edge->getNumBytes());//assuming it was initialized earlier to 0
349         vhelpers[uid]->incEdgestopart2(edge->getNumBytes());//assuming it was initialized earlier to 0
350       }
351       if(vhelpers[uid]->getPartition()==2*parent && vhelpers[uid]->getLevel()==level)
352       {
353         vhelpers[vid]->incEdgestopart2(edge->getNumBytes());
354       }
355     }//end of while(1) loop
356
357
358     //Edge counts are initialized while performing BFS
359     vhelpers[vid]->setGain(vhelpers[vid]->getEdgestopart2() - vhelpers[vid]->getEdgestopart1());
360     if(vhelpers[vid]->getGain() < que2->getMingain())//we want most negative gain
361     {
362       que2->setMingain(vhelpers[vid]->getGain());
363       que2->setVertextoswap(v->getVertexId());
364       que2->setSwapid(i);
365     }
366   }
367
368   for(i=0;i<que1->q.size();i++)
369   {
370     int uid=que1->q[i];
371     swap = true; ei=-1;
372     Vertex *u=(Vertex *)&(ogr->vertices[uid]);
373
374     while(1) {
375       ei++;
376       if(swap==true && ei==u->sendToList.size())
377       { swap=false; ei=0;}
378
379       if(swap==false && ei==u->recvFromList.size())
380       { swap=true; ei=-1; break;}
381
382       if(swap)
383       {
384         wid=u->sendToList[ei].getNeighborId();
385         edge = (Edge *)&(u->sendToList[ei]);
386       }
387       else
388       {
389         wid=u->recvFromList[ei].getNeighborId();
390         edge = (Edge *)&(u->recvFromList[ei]);
391       }
392
393       Vertex *w=(Vertex *)&(ogr->vertices[wid]);
394       if(vhelpers[wid]->getLevel()==level && vhelpers[wid]->getPartition()==(2*parent-1))
395         vhelpers[uid]->incEdgestopart1(edge->getNumBytes());
396     }
397
398   }     
399   *initialedgecut=edgecut;
400   //figure out which vertex to swap out of boundaryline1
401   //by this time we know edgestopart2 for every vertex in que1
402   adjustgain(ogr,partition1, que1);
403 }
404
405 //precondition - edgestopart1 and edgestopart2 must be known for every vertex in queue
406 void adjustgain(ObjGraph *ogr,vector<Vertex *> &partition, BQueue *que)
407 {
408   int i;
409   int bdry=que->getBoundary();
410   que->setMingain(INT_MAX);
411   que->setVertextoswap(-1);
412   que->setSwapid(-1);
413
414   for (i=0;i<que->q.size();i++)//for each vertex u in que
415   {
416     int uid=que->q[i];
417     Vertex *u =(Vertex *)&(ogr->vertices[uid]);
418
419     if(bdry==1)
420     {
421       vhelpers[uid]->setGain(vhelpers[uid]->getEdgestopart1() - vhelpers[uid]->getEdgestopart2());
422     }
423     else if(bdry==2)
424     {
425       vhelpers[uid]->setGain(vhelpers[uid]->getEdgestopart2() - vhelpers[uid]->getEdgestopart1());
426     }
427     if(vhelpers[uid]->getGain() < que->getMingain())//we want most negative gain
428     {   
429       que->setMingain(vhelpers[uid]->getGain());
430       que->setVertextoswap(u->getVertexId());
431       que->setSwapid(i);
432     }
433   }
434 }
435
436 // Fiduccia Mattheyses boundary refinement algorithm
437 void RefineBoundary(ObjGraph *ogr,vector<Vertex *> &partition1, vector<Vertex *> &partition2, BQueue *que1, BQueue *que2, int runs, int initialedgecut, int parent, double part1load, double part2load, double ratio)
438 {
439   int r=runs;
440   int t;
441   if(que1->q.size()<que2->q.size())
442     t=que1->q.size();
443   else t=que2->q.size();
444   if(t<r) r=t;
445   if(r==0) return;
446
447   int newedgecut=initialedgecut;
448
449   for(int i=0;i<r;i++)
450   {
451     if((part1load/(part1load+part2load))>ratio)
452     {
453       if(partition1.size()>1 && que1->q.size()>0)//because if part1 has only one vertex which is heavier than the whole part2, swapping it wouldnt make sense
454       {
455         double xfer=(ogr->vertices[que1->getVertextoswap()]).getVertexLoad();
456         part1load-=xfer;
457         part2load+=xfer;
458         newedgecut=modifypartitions(ogr, partition1, partition2, que1, que2, newedgecut, parent);//it also should adjust the new gains of both boundaries and the edgecut
459       }
460     }
461     else{
462       if(partition2.size()>1 && que2->q.size()>0)
463       {
464         double xfer=(ogr->vertices[que2->getVertextoswap()]).getVertexLoad();
465         part2load-=xfer;
466         part1load+=xfer;
467         newedgecut=modifypartitions(ogr, partition1, partition2, que2, que1, newedgecut, parent);//it also should adjust the new gains of both boundaries and the edgecut
468       }
469     }
470
471   }
472 }
473
474
475 int modifypartitions(ObjGraph *ogr,vector<Vertex *> &partition1, vector<Vertex *> &partition2, BQueue *q1, BQueue *q2,int ec, int parent)
476 {
477   int newedgecut;
478   if(q1->getBoundary()==1)//we are swapping vertex out of boundaryline1
479   {
480     int e2=vhelpers[q1->getVertextoswap()]->getEdgestopart2();
481     int e1=vhelpers[q1->getVertextoswap()]->getEdgestopart1();
482     newedgecut=ec-(e2)+(e1);
483     vhelpers[q1->getVertextoswap()]->setPartition(2*parent);
484     Vertex *ptr=removePtr(partition1,q1->getVertextoswap());
485     partition2.push_back(ptr);
486
487   }
488   else if(q1->getBoundary()==2)//we are swapping vertex out of boundaryline2
489   {
490     int e1=vhelpers[q1->getVertextoswap()]->getEdgestopart1();
491     int e2=vhelpers[q1->getVertextoswap()]->getEdgestopart2();
492     newedgecut=ec-(e1)+(e2);
493     vhelpers[q1->getVertextoswap()]->setPartition(2*parent-1);
494     Vertex *ptr=removePtr(partition2,q1->getVertextoswap());
495     partition1.push_back(ptr);
496
497   }
498
499   swapQ1toQ2(ogr,q1,q2,parent);//avoid thrashing, same vertex cannot be swapped more than once in same call
500   adjustgain(ogr,partition1,q1);//not required for last run of KLFM
501   adjustgain(ogr,partition2,q2);        //not required for last run of KLFM
502   return newedgecut;
503 }
504
505 void swapQ1toQ2(ObjGraph *ogr, BQueue *q1, BQueue *q2, int parent)
506 {
507   Vertex *vert=removeinSwap(ogr,q1,q2,parent);//remove vertex from q1
508   //removevert also removes or brings in new vertices in the queues, so the edgestopart1 and edgestopart2 are calculated for new vertices inside removevert
509   q2->push(vert);
510 }
511
512 Vertex * removeinSwap(ObjGraph *ogr,BQueue *q1, BQueue *q2, int parent)
513 {
514   int i,j,ei=-1, uid, wid, einested=-1;
515   Edge *edge, *edgenested;
516   bool swap=true, swapnested=true;
517   Vertex *v=(Vertex *)&(ogr->vertices[q1->getVertextoswap()]);
518   //edge counts of v do not change
519   //Adjust edgecounts of neighbours, verify whether any additions or deletions happen to the boundarylines
520
521   while(1) {
522     ei++;
523     if(swap==true && ei==v->sendToList.size())
524     { swap=false; ei=0;}
525     if(swap==false && ei==v->recvFromList.size())
526     { swap=true; ei=-1; break;}
527     if(swap)
528     {
529       uid=v->sendToList[ei].getNeighborId();
530       edge=(Edge *)&(v->sendToList[ei]);
531     }
532     else
533     {
534       uid=v->recvFromList[ei].getNeighborId();
535       edge=(Edge *)&(v->recvFromList[ei]);
536     }
537
538     Vertex *u=(Vertex *)&(ogr->vertices[uid]);
539
540     if(q1->getBoundary()==1)//vertex being removed out of boundaryline1
541     {
542       if((vhelpers[uid]->getBoundaryline()==true) && vhelpers[uid]->getLevel()==level)//do for both partitions
543       {
544         vhelpers[uid]->incEdgestopart2(edge->getNumBytes());
545         vhelpers[uid]->decEdgestopart1(edge->getNumBytes());
546       }
547       else if(vhelpers[uid]->getPartition()==(2*parent-1) && vhelpers[uid]->getLevel()==level && vhelpers[uid]->getBoundaryline()==false)
548         //nbr u of v which was in part1, but not in boundaryline1, is now introduced to boundaryline1
549       {
550         //new to boundaryline1, hence calculate edgestopart2
551         vhelpers[uid]->setEdgestopart2(edge->getNumBytes());
552         vhelpers[uid]->setEdgestopart1(0);
553
554         while(1) {
555           einested++;
556           if(swapnested==true && einested==u->sendToList.size())
557           { swapnested=false; einested=0;}
558           if(swapnested==false && einested==u->recvFromList.size())
559           { swapnested=true; einested=-1; break;}
560           if(swapnested)
561           {
562             wid=u->sendToList[einested].getNeighborId();
563             edgenested=(Edge *)&(u->sendToList[einested]);
564           }
565           else
566           {
567             wid=u->recvFromList[einested].getNeighborId();
568             edgenested = (Edge *)&(u->recvFromList[einested]);
569           }
570           Vertex *w=(Vertex *)&(ogr->vertices[wid]);
571           if(vhelpers[wid]->getLevel()==level && vhelpers[wid]->getPartition()==(2*parent-1))
572             vhelpers[uid]->incEdgestopart1(edgenested->getNumBytes());
573         }
574         q1->push(u);//also sets boundaryline=true
575       }
576       if(vhelpers[uid]->getPartition()==2*parent && vhelpers[uid]->getLevel()==level && vhelpers[uid]->getBoundaryline()==true && vhelpers[uid]->getEdgestopart1()==0)
577         //vertex in part2, on boundaryline2, now not a part of boundaryline2
578       {
579         q2->removeComplete(u);//q1 is queue1, q2 is queue2//sets boundaryline=false
580       }
581     }
582     else if(q1->getBoundary()==2)//vertex being removed out of boundaryline2
583     {
584       if(vhelpers[uid]->getBoundaryline()==true && vhelpers[uid]->getLevel()==level)//do for both partitions
585       {
586         vhelpers[uid]->incEdgestopart1(edge->getNumBytes());
587         vhelpers[uid]->decEdgestopart2(edge->getNumBytes());
588       }
589       else if(vhelpers[uid]->getPartition()==2*parent && vhelpers[uid]->getLevel()==level && vhelpers[uid]->getBoundaryline()==false)
590         //vertex which was in part2, but not in boundaryline2, is now introduced to boundaryline2
591       {
592         //new to boundaryline2
593         vhelpers[uid]->setEdgestopart1(edge->getNumBytes());
594         vhelpers[uid]->setEdgestopart2(0);
595
596         while(1) {
597           einested++;
598           if(swapnested==true && einested==u->sendToList.size())
599           { swapnested=false; einested=0;}
600           if(swapnested==false && einested==u->recvFromList.size())
601           { swapnested=true; einested=-1; break;}
602           if(swapnested)
603           {
604             wid=u->sendToList[einested].getNeighborId();
605             edgenested = (Edge *)&(u->sendToList[einested]);
606           }
607           else
608           {
609             wid=u->recvFromList[einested].getNeighborId();
610             edgenested= (Edge *)&(u->recvFromList[einested]);
611           }
612
613           Vertex *w=(Vertex *)&(ogr->vertices[wid]);
614           if(vhelpers[wid]->getLevel()==level && vhelpers[wid]->getPartition()==(2*parent))
615             vhelpers[uid]->incEdgestopart2(edgenested->getNumBytes());
616         }
617
618         q1->push(u);//q1 is boundaryline2
619       }
620       if(vhelpers[uid]->getPartition()==(2*parent-1) && vhelpers[uid]->getLevel()==level && vhelpers[uid]->getBoundaryline()==true && vhelpers[uid]->getEdgestopart2()==0)
621         //vertex in part1, on boundaryline1, now not a part of boundaryline1
622       {
623         q2->removeComplete(u);//q1 is queue1, q2 is queue2
624       }
625     }
626   }
627
628   //remove vertex v from q1 to swap into q2
629   /*q1->removeToSwap(v); */
630   q1->removeComplete(v);        
631   return v;
632 }
633
634 Vertex * removePtr(vector<Vertex *> &vec,int id)
635 {
636   int i;
637   for(i=0;i<vec.size();i++)
638   {
639     if(vec[i]->getVertexId()==id)
640     {
641       Vertex *ptr=vec[i];
642       vec[i]=vec.back();
643       vec.pop_back();
644       return ptr;
645     }
646   }
647   return NULL;
648 }
649
650 #include "RecBipartLB.def.h"
651 /*@}*/