lib/Transforms/Instrumentation/ProfilePaths/GraphAuxiliary.cpp

   1 //===-- GrapAuxillary.cpp- Auxillary functions on graph ----------*- C++ -*--=//
   2 //
   3 //auxillary function associated with graph: they
   4 //all operate on graph, and help in inserting
   5 //instrumentation for trace generation
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "Graph.h"
  10 #include "llvm/BasicBlock.h"
  11 #include <algorithm>
  12
  13 //check if 2 edges are equal (same endpoints and same weight)
  14 static bool edgesEqual(Edge  ed1, Edge ed2);
  15
  16 //Get the vector of edges that are to be instrumented in the graph
  17 static void getChords(vector<Edge > &chords, Graph g, Graph st);
  18
  19 //Given a tree t, and a "directed graph" g
  20 //replace the edges in the tree t with edges that exist in graph
  21 //The tree is formed from "undirectional" copy of graph
  22 //So whatever edges the tree has, the undirectional graph
  23 //would have too. This function corrects some of the directions in
  24 //the tree so that now, all edge directions in the tree match
  25 //the edge directions of corresponding edges in the directed graph
  26 static void removeTreeEdges(Graph g, Graph& t);
  27
  28 //Now we select a subset of all edges
  29 //and assign them some values such that
  30 //if we consider just this subset, it still represents
  31 //the path sum along any path in the graph
  32 static map<Edge, int> getEdgeIncrements(Graph& g, Graph& t);
  33
  34 //Based on edgeIncrements (above), now obtain
  35 //the kind of code to be inserted along an edge
  36 //The idea here is to minimize the computation
  37 //by inserting only the needed code
  38 static map<Edge, getEdgeCode *>*
  39 getCodeInsertions(Graph &g,
  40                   vector<Edge > &chords,
  41                   map<Edge,int> &edIncrements);
  42
  43 //Move the incoming dummy edge code and outgoing dummy
  44 //edge code over to the corresponding back edge
  45 static void moveDummyCode(vector<Edge > stDummy,
  46                    vector<Edge > exDummy,
  47                    vector<Edge > be,
  48                    map<Edge, getEdgeCode *> &insertions);
  49
  50
  51
  52 //Do graph processing: to determine minimal edge increments,
  53 //appropriate code insertions etc and insert the code at
  54 //appropriate locations
  55 void processGraph(Graph &g,
  56                   Instruction *rInst,
  57                   Instruction *countInst,
  58                   vector<Edge >& be,
  59                   vector<Edge >& stDummy,
  60                   vector<Edge >& exDummy){
  61   //Given a graph: with exit->root edge, do the following in seq:
  62   //1. get back edges
  63   //2. insert dummy edges and remove back edges
  64   //3. get edge assignments
  65   //4. Get Max spanning tree of graph:
  66   //   -Make graph g2=g undirectional
  67   //   -Get Max spanning tree t
  68   //   -Make t undirectional
  69   //   -remove edges from t not in graph g
  70   //5. Get edge increments
  71   //6. Get code insertions
  72   //7. move code on dummy edges over to the back edges
  73
  74
  75   //This is used as maximum "weight" for
  76   //priority queue
  77   //This would hold all
  78   //right as long as number of paths in the graph
  79   //is less than this
  80   const int INFINITY=99999999;
  81
  82
  83   //step 1-3 are already done on the graph when this function is called
  84 #ifdef DEBUG_PATH_PROFILES
  85   printGraph(g);
  86 #endif
  87   //step 4: Get Max spanning tree of graph
  88
  89   //now insert exit to root edge
  90   //if its there earlier, remove it!
  91   //assign it weight INFINITY
  92   //so that this edge IS ALWAYS IN spanning tree
  93   //Note than edges in spanning tree do not get
  94   //instrumented: and we do not want the
  95   //edge exit->root to get instrumented
  96   //as it MAY BE a dummy edge
  97   Edge ed(g.getExit(),g.getRoot(),INFINITY);
  98   g.addEdge(ed,INFINITY);
  99   Graph g2=g;
 100
 101   //make g2 undirectional: this gives a better
 102   //maximal spanning tree
 103   g2.makeUnDirectional();
 104 #ifdef DEBUG_PATH_PROFILES
 105   printGraph(g2);
 106 #endif
 107   Graph *t=g2.getMaxSpanningTree();
 108 #ifdef DEBUG_PATH_PROFILES
 109   printGraph(*t);
 110 #endif
 111   //now edges of tree t have weights reversed
 112   //(negative) because the algorithm used
 113   //to find max spanning tree is
 114   //actually for finding min spanning tree
 115   //so get back the original weights
 116   t->reverseWts();
 117
 118   //Ordinarily, the graph is directional
 119   //lets converts the graph into an
 120   //undirectional graph
 121   //This is done by adding an edge
 122   //v->u for all existing edges u->v
 123   t->makeUnDirectional();
 124
 125   //Given a tree t, and a "directed graph" g
 126   //replace the edges in the tree t with edges that exist in graph
 127   //The tree is formed from "undirectional" copy of graph
 128   //So whatever edges the tree has, the undirectional graph
 129   //would have too. This function corrects some of the directions in
 130   //the tree so that now, all edge directions in the tree match
 131   //the edge directions of corresponding edges in the directed graph
 132   removeTreeEdges(g, *t);
 133 #ifdef DEBUG_PATH_PROFILES
 134   cerr<<"Spanning tree---------\n";
 135   printGraph(*t);
 136   cerr<<"-------end spanning tree\n";
 137 #endif
 138   //now remove the exit->root node
 139   //and re-add it with weight 0
 140   //since infinite weight is kinda confusing
 141   g.removeEdge(ed);
 142   Edge edNew(g.getExit(), g.getRoot(),0);
 143   g.addEdge(edNew,0);
 144   if(t->hasEdge(ed)){
 145     t->removeEdge(ed);
 146     t->addEdge(edNew,0);
 147   }
 148
 149 #ifdef DEBUG_PATH_PROFILES
 150   printGraph(g);
 151   printGraph(*t);
 152 #endif
 153   //step 5: Get edge increments
 154
 155   //Now we select a subset of all edges
 156   //and assign them some values such that
 157   //if we consider just this subset, it still represents
 158   //the path sum along any path in the graph
 159   map<Edge, int> increment=getEdgeIncrements(g,*t);
 160 #ifdef DEBUG_PATH_PROFILES
 161   //print edge increments for debugging
 162   for(map<Edge, int>::iterator M_I=increment.begin(), M_E=increment.end();
 163       M_I!=M_E; ++M_I){
 164     printEdge(M_I->first);
 165     cerr<<"Increment for above:"<<M_I->second<<endl;
 166   }
 167 #endif
 168
 169   //step 6: Get code insertions
 170
 171   //Based on edgeIncrements (above), now obtain
 172   //the kind of code to be inserted along an edge
 173   //The idea here is to minimize the computation
 174   //by inserting only the needed code
 175   map<Edge, getEdgeCode *>* codeInsertions;
 176   vector<Edge > chords;
 177   getChords(chords, g, *t);
 178   codeInsertions=getCodeInsertions(g,chords,increment);
 179
 180 #ifdef DEBUG_PATH_PROFILES
 181   //print edges with code for debugging
 182   cerr<<"Code inserted in following---------------\n";
 183   for(map<Edge, getEdgeCode *>::iterator cd_i=codeInsertions->begin(),
 184         cd_e=codeInsertions->end(); cd_i!=cd_e; ++cd_i){
 185     printEdge(cd_i->first);
 186     cerr<<cd_i->second->getCond()<<":"<<cd_i->second->getInc()<<endl;
 187   }
 188   cerr<<"-----end insertions\n";
 189 #endif
 190   //step 7: move code on dummy edges over to the back edges
 191
 192   //Move the incoming dummy edge code and outgoing dummy
 193   //edge code over to the corresponding back edge
 194   moveDummyCode(stDummy, exDummy, be,  *codeInsertions);
 195
 196 #ifdef DEBUG_PATH_PROFILES
 197   //debugging info
 198   cerr<<"After moving dummy code\n";
 199   for(map<Edge, getEdgeCode *>::iterator cd_i=codeInsertions->begin(),
 200         cd_e=codeInsertions->end(); cd_i!=cd_e; ++cd_i){
 201     printEdge(cd_i->first);
 202     cerr<<cd_i->second->getCond()<<":"
 203         <<cd_i->second->getInc()<<endl;
 204   }
 205   cerr<<"Dummy end------------\n";
 206 #endif
 207
 208   //see what it looks like...
 209   //now insert code along edges which have codes on them
 210   for(map<Edge, getEdgeCode *>::iterator MI=codeInsertions->begin(),
 211         ME=codeInsertions->end(); MI!=ME; ++MI){
 212     Edge ed=MI->first;
 213     insertBB(ed, MI->second, rInst, countInst);
 214   }
 215 }
 216
 217
 218
 219 //check if 2 edges are equal (same endpoints and same weight)
 220 static bool edgesEqual(Edge  ed1, Edge ed2){
 221   return ((ed1==ed2) && ed1.getWeight()==ed2.getWeight());
 222 }
 223
 224 //Get the vector of edges that are to be instrumented in the graph
 225 static void getChords(vector<Edge > &chords, Graph g, Graph st){
 226   //make sure the spanning tree is directional
 227   //iterate over ALL the edges of the graph
 228   list<Node *> allNodes=g.getAllNodes();
 229   for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
 230       ++NI){
 231     Graph::nodeList node_list=g.getNodeList(*NI);
 232     for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
 233         NLI!=NLE; ++NLI){
 234       Edge f(*NI, NLI->element,NLI->weight);
 235       if(!(st.hasEdgeAndWt(f)))//addnl
 236         chords.push_back(f);
 237     }
 238   }
 239 }
 240
 241 //Given a tree t, and a "directed graph" g
 242 //replace the edges in the tree t with edges that exist in graph
 243 //The tree is formed from "undirectional" copy of graph
 244 //So whatever edges the tree has, the undirectional graph
 245 //would have too. This function corrects some of the directions in
 246 //the tree so that now, all edge directions in the tree match
 247 //the edge directions of corresponding edges in the directed graph
 248 static void removeTreeEdges(Graph g, Graph& t){
 249   list<Node* > allNodes=t.getAllNodes();
 250   for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
 251       ++NI){
 252     Graph::nodeList nl=t.getNodeList(*NI);
 253     for(Graph::nodeList::iterator NLI=nl.begin(), NLE=nl.end(); NLI!=NLE;++NLI){
 254       Edge ed(NLI->element, *NI, NLI->weight);
 255       //if(!g.hasEdge(ed)) t.removeEdge(ed);
 256       if(!g.hasEdgeAndWt(ed)) t.removeEdge(ed);//tree has only one edge
 257       //between any pair of vertices, so no need to delete by edge wt
 258     }
 259   }
 260 }
 261
 262 //Assign a value to all the edges in the graph
 263 //such that if we traverse along any path from root to exit, and
 264 //add up the edge values, we get a path number that uniquely
 265 //refers to the path we travelled
 266 int valueAssignmentToEdges(Graph& g){
 267   list<Node *> revtop=g.reverseTopologicalSort();
 268   map<Node *,int > NumPaths;
 269   for(list<Node *>::iterator RI=revtop.begin(), RE=revtop.end(); RI!=RE; ++RI){
 270     if(g.isLeaf(*RI))
 271       NumPaths[*RI]=1;
 272     else{
 273       NumPaths[*RI]=0;
 274       list<Node *> succ=g.getSuccNodes(*RI);
 275       for(list<Node *>::iterator SI=succ.begin(), SE=succ.end(); SI!=SE; ++SI){
 276         Edge ed(*RI,*SI,NumPaths[*RI]);
 277         g.setWeight(ed);
 278         NumPaths[*RI]+=NumPaths[*SI];
 279       }
 280     }
 281   }
 282   return NumPaths[g.getRoot()];
 283 }
 284
 285 //This is a helper function to get the edge increments
 286 //This is used in conjuntion with inc_DFS
 287 //to get the edge increments
 288 //Edge increment implies assigning a value to all the edges in the graph
 289 //such that if we traverse along any path from root to exit, and
 290 //add up the edge values, we get a path number that uniquely
 291 //refers to the path we travelled
 292 //inc_Dir tells whether 2 edges are in same, or in different directions
 293 //if same direction, return 1, else -1
 294 static int inc_Dir(Edge e,Edge f){
 295  if(e.isNull())
 296     return 1;
 297
 298  //check that the edges must have atleast one common endpoint
 299   assert(*(e.getFirst())==*(f.getFirst()) ||
 300          *(e.getFirst())==*(f.getSecond()) ||
 301          *(e.getSecond())==*(f.getFirst()) ||
 302          *(e.getSecond())==*(f.getSecond()));
 303
 304   if(*(e.getFirst())==*(f.getSecond()) ||
 305      *(e.getSecond())==*(f.getFirst()))
 306     return 1;
 307
 308   return -1;
 309 }
 310
 311 //used for getting edge increments (read comments above in inc_Dir)
 312 //inc_DFS is a modification of DFS
 313 static void inc_DFS(Graph& g,Graph& t,map<Edge, int>& Increment,
 314              int events, Node *v, Edge e){
 315
 316   list<Node *> allNodes=t.getAllNodes();
 317
 318   for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
 319       ++NI){
 320     Graph::nodeList node_list=t.getNodeList(*NI);
 321     for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
 322         NLI!= NLE; ++NLI){
 323       Edge f(*NI, NLI->element,NLI->weight);
 324       if(!edgesEqual(f,e) && *v==*(f.getSecond())){
 325         int dir_count=inc_Dir(e,f);
 326         int wt=1*f.getWeight();
 327         inc_DFS(g,t, Increment, dir_count*events+wt, f.getFirst(), f);
 328       }
 329     }
 330   }
 331
 332   for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
 333       ++NI){
 334     Graph::nodeList node_list=t.getNodeList(*NI);
 335     for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
 336         NLI!=NLE; ++NLI){
 337       Edge f(*NI, NLI->element,NLI->weight);
 338       if(!edgesEqual(f,e) && *v==*(f.getFirst())){
 339         int dir_count=inc_Dir(e,f);
 340         int wt=1*f.getWeight();
 341         inc_DFS(g,t, Increment, dir_count*events+wt,
 342                 f.getSecond(), f);
 343       }
 344     }
 345   }
 346
 347   allNodes=g.getAllNodes();
 348   for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
 349       ++NI){
 350     Graph::nodeList node_list=g.getNodeList(*NI);
 351     for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
 352         NLI!=NLE; ++NLI){
 353       Edge f(*NI, NLI->element,NLI->weight);
 354       if(!(t.hasEdgeAndWt(f)) && (*v==*(f.getSecond()) ||
 355                                   *v==*(f.getFirst()))){
 356         int dir_count=inc_Dir(e,f);
 357         Increment[f]+=dir_count*events;
 358       }
 359     }
 360   }
 361 }
 362
 363 //Now we select a subset of all edges
 364 //and assign them some values such that
 365 //if we consider just this subset, it still represents
 366 //the path sum along any path in the graph
 367 static map<Edge, int> getEdgeIncrements(Graph& g, Graph& t){
 368   //get all edges in g-t
 369   map<Edge, int> Increment;
 370
 371   list<Node *> allNodes=g.getAllNodes();
 372
 373   for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
 374       ++NI){
 375     Graph::nodeList node_list=g.getNodeList(*NI);
 376     for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
 377         NLI!=NLE; ++NLI){
 378       Edge ed(*NI, NLI->element,NLI->weight);
 379       if(!(t.hasEdge(ed))){
 380         Increment[ed]=0;;
 381       }
 382     }
 383   }
 384
 385   Edge *ed=new Edge();
 386   inc_DFS(g,t,Increment, 0, g.getRoot(), *ed);
 387
 388
 389   for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
 390       ++NI){
 391     Graph::nodeList node_list=g.getNodeList(*NI);
 392     for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
 393         NLI!=NLE; ++NLI){
 394       Edge ed(*NI, NLI->element,NLI->weight);
 395       if(!(t.hasEdge(ed))){
 396         int wt=ed.getWeight();
 397         Increment[ed]+=wt;
 398       }
 399     }
 400   }
 401
 402   return Increment;
 403 }
 404
 405 //Based on edgeIncrements (above), now obtain
 406 //the kind of code to be inserted along an edge
 407 //The idea here is to minimize the computation
 408 //by inserting only the needed code
 409 static map<Edge, getEdgeCode *>*
 410 getCodeInsertions(Graph &g,
 411                   vector<Edge > &chords,
 412                   map<Edge,int> &edIncrements){
 413   //map of instrumented edges that's returned in the end
 414   map<Edge, getEdgeCode *> *instr=
 415     new map<Edge, getEdgeCode *>;
 416
 417   //Register initialization code
 418   vector<Node *> ws;
 419   ws.push_back(g.getRoot());
 420   while(ws.size()>0){
 421     Node *v=ws[0];
 422     ws.erase(ws.begin());
 423     //for each edge v->w
 424     Graph::nodeList succs=g.getNodeList(v);
 425
 426     for(Graph::nodeList::iterator nl=succs.begin(), ne=succs.end();
 427         nl!=ne; ++nl){
 428       int edgeWt=nl->weight;
 429       Node *w=nl->element;
 430       //if chords has v->w
 431       Edge ed(v,w);
 432
 433       bool hasEdge=false;
 434       for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end();
 435           CI!=CE && !hasEdge;++CI){
 436         if(*CI==ed){
 437           hasEdge=true;
 438         }
 439       }
 440       if(hasEdge){
 441         getEdgeCode *edCd=new getEdgeCode();
 442         edCd->setCond(1);
 443         edCd->setInc(edIncrements[ed]);
 444         (*instr)[ed]=edCd;
 445       }
 446       else if((g.getPredNodes(w)).size()==1){
 447         ws.push_back(w);
 448       }
 449       else{
 450         getEdgeCode *edCd=new getEdgeCode();
 451         edCd->setCond(2);
 452         edCd->setInc(0);
 453         (*instr)[ed]=edCd;
 454       }
 455     }
 456   }
 457
 458   /////Memory increment code
 459   ws.push_back(g.getExit());
 460
 461   while(ws.size()>0){
 462     Node *w=ws[0];
 463     ws.erase(&ws[0]);
 464
 465     //for each edge v->w
 466     list<Node *> preds=g.getPredNodes(w);
 467     for(list<Node *>::iterator pd=preds.begin(), pe=preds.end(); pd!=pe; ++pd){
 468       Node *v=*pd;
 469       //if chords has v->w
 470
 471       Edge ed(v,w);
 472       getEdgeCode *edCd=new getEdgeCode();
 473       bool hasEdge=false;
 474       for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end(); CI!=CE;
 475           ++CI){
 476         if(*CI==ed){
 477           hasEdge=true;
 478           break;
 479         }
 480       }
 481       if(hasEdge){
 482         char str[100];
 483         if((*instr)[ed]!=NULL && (*instr)[ed]->getCond()==1){
 484           (*instr)[ed]->setCond(4);
 485         }
 486         else{
 487           edCd->setCond(5);
 488           edCd->setInc(edIncrements[ed]);
 489           (*instr)[ed]=edCd;
 490         }
 491
 492       }
 493       else if(g.getSuccNodes(v).size()==1)
 494         ws.push_back(v);
 495       else{
 496         edCd->setCond(6);
 497         (*instr)[ed]=edCd;
 498       }
 499     }
 500   }
 501
 502   ///// Register increment code
 503   for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end(); CI!=CE; ++CI){
 504     getEdgeCode *edCd=new getEdgeCode();
 505         if((*instr)[*CI]==NULL){
 506           edCd->setCond(3);
 507           edCd->setInc(edIncrements[*CI]);
 508           (*instr)[*CI]=edCd;
 509         }
 510   }
 511
 512   return instr;
 513 }
 514
 515 //Add dummy edges corresponding to the back edges
 516 //If a->b is a backedge
 517 //then incoming dummy edge is root->b
 518 //and outgoing dummy edge is a->exit
 519 void addDummyEdges(vector<Edge > &stDummy,
 520                    vector<Edge > &exDummy,
 521                    Graph &g, vector<Edge > be){
 522   for(vector<Edge >::iterator VI=be.begin(), VE=be.end(); VI!=VE; ++VI){
 523     Edge ed=*VI;
 524     Node *first=ed.getFirst();
 525     Node *second=ed.getSecond();
 526     g.removeEdge(ed);
 527
 528     if(!(*second==*(g.getRoot()))){
 529       Edge *st=new Edge(g.getRoot(), second);
 530
 531       //check if stDummy doesn't have it already
 532       bool hasIt=false;
 533
 534       if(find(stDummy.begin(), stDummy.end(), *st)!=stDummy.end())
 535         hasIt=true;
 536
 537       /*
 538       for(vector<Edge>::iterator DM=stDummy.begin(), DE=stDummy.end(); DM!=DE;
 539           ++DM){
 540         if(*DM==*st){
 541           hasIt=true;
 542           break;
 543         }
 544       }
 545       */
 546
 547       if(!hasIt){
 548         stDummy.push_back(*st);
 549         g.addEdgeForce(*st);
 550       }
 551     }
 552
 553     if(!(*first==*(g.getExit()))){
 554       Edge *ex=new Edge(first, g.getExit());
 555
 556       bool hasIt=false;
 557       if(find(exDummy.begin(), exDummy.end(), *ex)!=exDummy.end())
 558         hasIt=true;
 559
 560       /*
 561       for(vector<Edge>::iterator DM=exDummy.begin(), DE=exDummy.end(); DM!=DE;
 562           ++DM){
 563         if(*DM==*ex){
 564           hasIt=true;
 565           break;
 566         }
 567       }
 568       */
 569
 570       if(!hasIt){
 571         exDummy.push_back(*ex);
 572         g.addEdgeForce(*ex);
 573       }
 574     }
 575   }
 576 }
 577
 578 //print a given edge in the form BB1Label->BB2Label
 579 void printEdge(Edge ed){
 580   cerr<<((ed.getFirst())->getElement())
 581     ->getName()<<"->"<<((ed.getSecond())
 582                           ->getElement())->getName()<<
 583     ":"<<ed.getWeight()<<endl;
 584 }
 585
 586 //Move the incoming dummy edge code and outgoing dummy
 587 //edge code over to the corresponding back edge
 588 static void moveDummyCode(vector<Edge > stDummy,
 589                    vector<Edge > exDummy,
 590                    vector<Edge > be,
 591                    map<Edge, getEdgeCode *> &insertions){
 592   typedef vector<Edge >::iterator vec_iter;
 593
 594 #ifdef DEBUG_PATH_PROFILES
 595   //print all back, st and ex dummy
 596   cerr<<"BackEdges---------------\n";
 597   for(vec_iter VI=be.begin(); VI!=be.end(); ++VI)
 598     printEdge(*VI);
 599   cerr<<"StEdges---------------\n";
 600   for(vec_iter VI=stDummy.begin(); VI!=stDummy.end(); ++VI)
 601     printEdge(*VI);
 602   cerr<<"ExitEdges---------------\n";
 603   for(vec_iter VI=exDummy.begin(); VI!=exDummy.end(); ++VI)
 604     printEdge(*VI);
 605   cerr<<"------end all edges\n";
 606 #endif
 607
 608   std::vector<Edge > toErase;
 609   for(map<Edge,getEdgeCode *>::iterator MI=insertions.begin(),
 610         ME=insertions.end(); MI!=ME; ++MI){
 611     Edge ed=MI->first;
 612     getEdgeCode *edCd=MI->second;
 613     bool dummyHasIt=false;
 614 #ifdef DEBUG_PATH_PROFILES
 615     cerr<<"Current edge considered---\n";
 616     printEdge(ed);
 617 #endif
 618     //now check if stDummy has ed
 619     for(vec_iter VI=stDummy.begin(), VE=stDummy.end(); VI!=VE && !dummyHasIt;
 620         ++VI){
 621       if(*VI==ed){
 622 #ifdef DEBUG_PATH_PROFILES
 623         cerr<<"Edge matched with stDummy\n";
 624 #endif
 625         dummyHasIt=true;
 626         bool dummyInBe=false;
 627         //dummy edge with code
 628         for(vec_iter BE=be.begin(), BEE=be.end(); BE!=BEE && !dummyInBe; ++BE){
 629           Edge backEdge=*BE;
 630           Node *st=backEdge.getSecond();
 631           Node *dm=ed.getSecond();
 632           if(*dm==*st){
 633             //so this is the back edge to use
 634 #ifdef DEBUG_PATH_PROFILES
 635             cerr<<"Moving to backedge\n";
 636             printEdge(backEdge);
 637 #endif
 638             getEdgeCode *ged=new getEdgeCode();
 639             ged->setCdIn(edCd);
 640             toErase.push_back(ed);
 641             insertions[backEdge]=ged;
 642             dummyInBe=true;
 643           }
 644         }
 645         assert(dummyInBe);
 646       }
 647     }
 648     if(!dummyHasIt){
 649       //so exDummy may hv it
 650       bool inExDummy=false;
 651       for(vec_iter VI=exDummy.begin(), VE=exDummy.end(); VI!=VE && !inExDummy;
 652           ++VI){
 653         if(*VI==ed){
 654           inExDummy=true;
 655 #ifdef DEBUG_PATH_PROFILES
 656           cerr<<"Edge matched with exDummy\n";
 657 #endif
 658           bool dummyInBe2=false;
 659           //dummy edge with code
 660           for(vec_iter BE=be.begin(), BEE=be.end(); BE!=BEE && !dummyInBe2;
 661               ++BE){
 662             Edge backEdge=*BE;
 663             Node *st=backEdge.getFirst();
 664             Node *dm=ed.getFirst();
 665             if(*dm==*st){
 666               //so this is the back edge to use
 667               getEdgeCode *ged;
 668               if(insertions[backEdge]==NULL)
 669                 ged=new getEdgeCode();
 670               else
 671                 ged=insertions[backEdge];
 672               toErase.push_back(ed);
 673               ged->setCdOut(edCd);
 674               insertions[backEdge]=ged;
 675               dummyInBe2=true;
 676             }
 677           }
 678           assert(dummyInBe2);
 679         }
 680       }
 681     }
 682   }
 683
 684 #ifdef DEBUG_PATH_PROFILES
 685   cerr<<"size of deletions: "<<toErase.size()<<endl;
 686 #endif
 687
 688   for(vector<Edge >::iterator vmi=toErase.begin(), vme=toErase.end(); vmi!=vme;
 689       ++vmi)
 690     insertions.erase(*vmi);
 691
 692 #ifdef DEBUG_PATH_PROFILES
 693   cerr<<"SIZE OF INSERTIONS AFTER DEL "<<insertions.size()<<endl;
 694 #endif
 695 }
 696
 697
 698 //print the graph (for debugging)
 699 void printGraph(Graph g){
 700   list<Node *> lt=g.getAllNodes();
 701   cerr<<"Graph---------------------\n";
 702   for(list<Node *>::iterator LI=lt.begin();
 703       LI!=lt.end(); ++LI){
 704     cerr<<((*LI)->getElement())->getName()<<"->";
 705     Graph::nodeList nl=g.getNodeList(*LI);
 706     for(Graph::nodeList::iterator NI=nl.begin();
 707         NI!=nl.end(); ++NI){
 708       cerr<<":"<<"("<<(NI->element->getElement())
 709         ->getName()<<":"<<NI->element->getWeight()<<","<<NI->weight<<")";
 710     }
 711     cerr<<"\n";
 712   }
 713   cerr<<"--------------------Graph\n";
 714 }