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