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