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