diff options
9 files changed, 0 insertions, 3043 deletions
diff --git a/lib/Transforms/Instrumentation/ProfilePaths/CombineBranch.cpp b/lib/Transforms/Instrumentation/ProfilePaths/CombineBranch.cpp deleted file mode 100644 index 5e4264ebfd..0000000000 --- a/lib/Transforms/Instrumentation/ProfilePaths/CombineBranch.cpp +++ /dev/null @@ -1,189 +0,0 @@ -//===-- CombineBranch.cpp -------------------------------------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// Combine multiple back-edges going to the same sink into a single -// back-edge. This introduces a new basic block and back-edge branch for each -// such sink. -// -//===----------------------------------------------------------------------===// - -#include "llvm/Support/CFG.h" -#include "llvm/Instructions.h" -#include "llvm/Function.h" -#include "llvm/Pass.h" -#include "llvm/Type.h" - -namespace llvm { - -namespace { - struct CombineBranches : public FunctionPass { - private: - /// Possible colors that a vertex can have during depth-first search for - /// back-edges. - /// - enum Color { WHITE, GREY, BLACK }; - - void getBackEdgesVisit(BasicBlock *u, - std::map<BasicBlock *, Color > &color, - std::map<BasicBlock *, int > &d, - int &time, - std::map<BasicBlock *, BasicBlock *> &be); - void removeRedundant(std::map<BasicBlock *, BasicBlock *> &be); - public: - bool runOnFunction(Function &F); - }; - - RegisterOpt<CombineBranches> - X("branch-combine", "Multiple backedges going to same target are merged"); -} - -/// getBackEdgesVisit - Get the back-edges of the control-flow graph for this -/// function. We proceed recursively using depth-first search. We get -/// back-edges by associating a time and a color with each vertex. The time of a -/// vertex is the time when it was first visited. The color of a vertex is -/// initially WHITE, changes to GREY when it is first visited, and changes to -/// BLACK when ALL its neighbors have been visited. So we have a back edge when -/// we meet a successor of a node with smaller time, and GREY color. -/// -void CombineBranches::getBackEdgesVisit(BasicBlock *u, - std::map<BasicBlock *, Color > &color, - std::map<BasicBlock *, int > &d, - int &time, - std::map<BasicBlock *, BasicBlock *> &be) { - - color[u]=GREY; - time++; - d[u]=time; - - for (succ_iterator vl = succ_begin(u), ve = succ_end(u); vl != ve; ++vl){ - BasicBlock *BB = *vl; - - if(color[BB]!=GREY && color[BB]!=BLACK) - getBackEdgesVisit(BB, color, d, time, be); - - //now checking for d and f vals - else if(color[BB]==GREY){ - //so v is ancestor of u if time of u > time of v - if(d[u] >= d[BB]) // u->BB is a backedge - be[u] = BB; - } - } - color[u]=BLACK;//done with visiting the node and its neighbors -} - -/// removeRedundant - Remove all back-edges that are dominated by other -/// back-edges in the set. -/// -void CombineBranches::removeRedundant(std::map<BasicBlock *, BasicBlock *> &be){ - std::vector<BasicBlock *> toDelete; - std::map<BasicBlock *, int> seenBB; - - for(std::map<BasicBlock *, BasicBlock *>::iterator MI = be.begin(), - ME = be.end(); MI != ME; ++MI){ - - if(seenBB[MI->second]) - continue; - - seenBB[MI->second] = 1; - - std::vector<BasicBlock *> sameTarget; - sameTarget.clear(); - - for(std::map<BasicBlock *, BasicBlock *>::iterator MMI = be.begin(), - MME = be.end(); MMI != MME; ++MMI){ - - if(MMI->first == MI->first) - continue; - - if(MMI->second == MI->second) - sameTarget.push_back(MMI->first); - - } - - //so more than one branch to same target - if(sameTarget.size()){ - - sameTarget.push_back(MI->first); - - BasicBlock *newBB = new BasicBlock("newCommon", MI->first->getParent()); - BranchInst *newBranch = new BranchInst(MI->second, newBB); - - std::map<PHINode *, std::vector<unsigned int> > phiMap; - - for(std::vector<BasicBlock *>::iterator VBI = sameTarget.begin(), - VBE = sameTarget.end(); VBI != VBE; ++VBI){ - - BranchInst *ti = cast<BranchInst>((*VBI)->getTerminator()); - unsigned char index = 1; - if(ti->getSuccessor(0) == MI->second) - index = 0; - - ti->setSuccessor(index, newBB); - - for(BasicBlock::iterator BB2Inst = MI->second->begin(), - BBend = MI->second->end(); BB2Inst != BBend; ++BB2Inst){ - - if (PHINode *phiInst = dyn_cast<PHINode>(BB2Inst)){ - int bbIndex; - bbIndex = phiInst->getBasicBlockIndex(*VBI); - if(bbIndex>=0) - phiMap[phiInst].push_back(bbIndex); - } - } - } - - for(std::map<PHINode *, std::vector<unsigned int> >::iterator - PI = phiMap.begin(), PE = phiMap.end(); PI != PE; ++PI){ - - PHINode *phiNode = new PHINode(PI->first->getType(), "phi", newBranch); - for(std::vector<unsigned int>::iterator II = PI->second.begin(), - IE = PI->second.end(); II != IE; ++II){ - phiNode->addIncoming(PI->first->getIncomingValue(*II), - PI->first->getIncomingBlock(*II)); - } - - std::vector<BasicBlock *> tempBB; - for(std::vector<unsigned int>::iterator II = PI->second.begin(), - IE = PI->second.end(); II != IE; ++II){ - tempBB.push_back(PI->first->getIncomingBlock(*II)); - } - - for(std::vector<BasicBlock *>::iterator II = tempBB.begin(), - IE = tempBB.end(); II != IE; ++II){ - PI->first->removeIncomingValue(*II); - } - - PI->first->addIncoming(phiNode, newBB); - } - } - } -} - -/// runOnFunction - Per function pass for combining branches. -/// -bool CombineBranches::runOnFunction(Function &F){ - if (F.isExternal ()) - return false; - - // Find and remove "redundant" back-edges. - std::map<BasicBlock *, Color> color; - std::map<BasicBlock *, int> d; - std::map<BasicBlock *, BasicBlock *> be; - int time = 0; - getBackEdgesVisit (F.begin (), color, d, time, be); - removeRedundant (be); - - return true; // FIXME: assumes a modification was always made. -} - -FunctionPass *createCombineBranchesPass () { - return new CombineBranches(); -} - -} // End llvm namespace diff --git a/lib/Transforms/Instrumentation/ProfilePaths/EdgeCode.cpp b/lib/Transforms/Instrumentation/ProfilePaths/EdgeCode.cpp deleted file mode 100644 index bf94943788..0000000000 --- a/lib/Transforms/Instrumentation/ProfilePaths/EdgeCode.cpp +++ /dev/null @@ -1,368 +0,0 @@ -//===-- EdgeCode.cpp - generate LLVM instrumentation code -----------------===// -// -// The LLVM Compiler Infrastructure -// -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -//It implements the class EdgeCode: which provides -//support for inserting "appropriate" instrumentation at -//designated points in the graph -// -//It also has methods to insert initialization code in -//top block of cfg -//===----------------------------------------------------------------------===// - -#include "Graph.h" -#include "llvm/Constants.h" -#include "llvm/DerivedTypes.h" -#include "llvm/Instructions.h" -#include "llvm/Module.h" - -#define INSERT_LOAD_COUNT -#define INSERT_STORE - - -using std::vector; - -namespace llvm { - -static void getTriggerCode(Module *M, BasicBlock *BB, int MethNo, Value *pathNo, - Value *cnt, Instruction *rInst){ - - vector<Value *> tmpVec; - tmpVec.push_back(Constant::getNullValue(Type::LongTy)); - tmpVec.push_back(Constant::getNullValue(Type::LongTy)); - Instruction *Idx = new GetElementPtrInst(cnt, tmpVec, "");//, - BB->getInstList().push_back(Idx); - - const Type *PIntTy = PointerType::get(Type::IntTy); - Function *trigMeth = M->getOrInsertFunction("trigger", Type::VoidTy, - Type::IntTy, Type::IntTy, - PIntTy, PIntTy, (Type *)0); - assert(trigMeth && "trigger method could not be inserted!"); - - vector<Value *> trargs; - - trargs.push_back(ConstantSInt::get(Type::IntTy,MethNo)); - trargs.push_back(pathNo); - trargs.push_back(Idx); - trargs.push_back(rInst); - - Instruction *callInst=new CallInst(trigMeth, trargs, "");//, BB->begin()); - BB->getInstList().push_back(callInst); - //triggerInst = new CallInst(trigMeth, trargs, "");//, InsertPos); -} - - -//get the code to be inserted on the edge -//This is determined from cond (1-6) -void getEdgeCode::getCode(Instruction *rInst, Value *countInst, - Function *M, BasicBlock *BB, - vector<Value *> &retVec){ - - //Instruction *InsertPos = BB->getInstList().begin(); - - //now check for cdIn and cdOut - //first put cdOut - if(cdOut!=NULL){ - cdOut->getCode(rInst, countInst, M, BB, retVec); - } - - if(cdIn!=NULL){ - cdIn->getCode(rInst, countInst, M, BB, retVec); - } - - //case: r=k code to be inserted - switch(cond){ - case 1:{ - Value *val=ConstantSInt::get(Type::IntTy,inc); -#ifdef INSERT_STORE - Instruction *stInst=new StoreInst(val, rInst);//, InsertPos); - BB->getInstList().push_back(stInst); -#endif - break; - } - - //case: r=0 to be inserted - case 2:{ -#ifdef INSERT_STORE - Instruction *stInst = new StoreInst(ConstantSInt::getNullValue(Type::IntTy), rInst);//, InsertPos); - BB->getInstList().push_back(stInst); -#endif - break; - } - - //r+=k - case 3:{ - Instruction *ldInst = new LoadInst(rInst, "ti1");//, InsertPos); - BB->getInstList().push_back(ldInst); - Value *val = ConstantSInt::get(Type::IntTy,inc); - Instruction *addIn = BinaryOperator::create(Instruction::Add, ldInst, val, - "ti2");//, InsertPos); - BB->getInstList().push_back(addIn); -#ifdef INSERT_STORE - Instruction *stInst = new StoreInst(addIn, rInst);//, InsertPos); - BB->getInstList().push_back(stInst); -#endif - break; - } - - //count[inc]++ - case 4:{ - vector<Value *> tmpVec; - tmpVec.push_back(Constant::getNullValue(Type::LongTy)); - tmpVec.push_back(ConstantSInt::get(Type::LongTy, inc)); - Instruction *Idx = new GetElementPtrInst(countInst, tmpVec, "");//, - - //Instruction *Idx = new GetElementPtrInst(countInst, - // vector<Value*>(1,ConstantSInt::get(Type::LongTy, inc)), - // "");//, InsertPos); - BB->getInstList().push_back(Idx); - - Instruction *ldInst=new LoadInst(Idx, "ti1");//, InsertPos); - BB->getInstList().push_back(ldInst); - - Value *val = ConstantSInt::get(Type::IntTy, 1); - //Instruction *addIn = - Instruction *newCount = - BinaryOperator::create(Instruction::Add, ldInst, val,"ti2"); - BB->getInstList().push_back(newCount); - - -#ifdef INSERT_STORE - //Instruction *stInst=new StoreInst(addIn, Idx, InsertPos); - Instruction *stInst=new StoreInst(newCount, Idx);//, InsertPos); - BB->getInstList().push_back(stInst); -#endif - - Value *trAddIndex = ConstantSInt::get(Type::IntTy,inc); - - retVec.push_back(newCount); - retVec.push_back(trAddIndex); - //insert trigger - //getTriggerCode(M->getParent(), BB, MethNo, - // ConstantSInt::get(Type::IntTy,inc), newCount, triggerInst); - //end trigger code - - assert(inc>=0 && "IT MUST BE POSITIVE NOW"); - break; - } - - //case: count[r+inc]++ - case 5:{ - - //ti1=inc+r - Instruction *ldIndex=new LoadInst(rInst, "ti1");//, InsertPos); - BB->getInstList().push_back(ldIndex); - - Value *val=ConstantSInt::get(Type::IntTy,inc); - Instruction *addIndex=BinaryOperator:: - create(Instruction::Add, ldIndex, val,"ti2");//, InsertPos); - BB->getInstList().push_back(addIndex); - - //now load count[addIndex] - Instruction *castInst=new CastInst(addIndex, - Type::LongTy,"ctin");//, InsertPos); - BB->getInstList().push_back(castInst); - - vector<Value *> tmpVec; - tmpVec.push_back(Constant::getNullValue(Type::LongTy)); - tmpVec.push_back(castInst); - Instruction *Idx = new GetElementPtrInst(countInst, tmpVec, "");//, - // InsertPos); - BB->getInstList().push_back(Idx); - - Instruction *ldInst=new LoadInst(Idx, "ti3");//, InsertPos); - BB->getInstList().push_back(ldInst); - - Value *cons=ConstantSInt::get(Type::IntTy,1); - //count[addIndex]++ - //std::cerr<<"Type ldInst:"<<ldInst->getType()<<"\t cons:"<<cons->getType()<<"\n"; - Instruction *newCount = BinaryOperator::create(Instruction::Add, ldInst, - cons,""); - BB->getInstList().push_back(newCount); - -#ifdef INSERT_STORE - Instruction *stInst = new StoreInst(newCount, Idx);//, InsertPos); - BB->getInstList().push_back(stInst); -#endif - - retVec.push_back(newCount); - retVec.push_back(addIndex); - //insert trigger - //getTriggerCode(M->getParent(), BB, MethNo, addIndex, newCount, triggerInst); - //end trigger code - - break; - } - - //case: count[r]+ - case 6:{ - //ti1=inc+r - Instruction *ldIndex=new LoadInst(rInst, "ti1");//, InsertPos); - BB->getInstList().push_back(ldIndex); - - //now load count[addIndex] - Instruction *castInst2=new CastInst(ldIndex, Type::LongTy,"ctin"); - BB->getInstList().push_back(castInst2); - - vector<Value *> tmpVec; - tmpVec.push_back(Constant::getNullValue(Type::LongTy)); - tmpVec.push_back(castInst2); - Instruction *Idx = new GetElementPtrInst(countInst, tmpVec, "");//, - - //Instruction *Idx = new GetElementPtrInst(countInst, - // vector<Value*>(1,castInst2), ""); - - BB->getInstList().push_back(Idx); - - Instruction *ldInst=new LoadInst(Idx, "ti2");//, InsertPos); - BB->getInstList().push_back(ldInst); - - Value *cons=ConstantSInt::get(Type::IntTy,1); - - //count[addIndex]++ - Instruction *newCount = BinaryOperator::create(Instruction::Add, ldInst, - cons,"ti3"); - BB->getInstList().push_back(newCount); - -#ifdef INSERT_STORE - Instruction *stInst = new StoreInst(newCount, Idx);//, InsertPos); - BB->getInstList().push_back(stInst); -#endif - - retVec.push_back(newCount); - retVec.push_back(ldIndex); - break; - } - - } -} - - - -//Insert the initialization code in the top BB -//this includes initializing r, and count -//r is like an accumulator, that -//keeps on adding increments as we traverse along a path -//and at the end of the path, r contains the path -//number of that path -//Count is an array, where Count[k] represents -//the number of executions of path k -void insertInTopBB(BasicBlock *front, - int k, - Instruction *rVar, Value *threshold){ - //rVar is variable r, - //countVar is count[] - - Value *Int0 = ConstantInt::get(Type::IntTy, 0); - - //now push all instructions in front of the BB - BasicBlock::iterator here=front->begin(); - front->getInstList().insert(here, rVar); - //front->getInstList().insert(here,countVar); - - //Initialize Count[...] with 0 - - //for (int i=0;i<k; i++){ - //Value *GEP2 = new GetElementPtrInst(countVar, - // vector<Value *>(1,ConstantSInt::get(Type::LongTy, i)), - // "", here); - //new StoreInst(Int0, GEP2, here); - //} - - //store uint 0, uint *%R - new StoreInst(Int0, rVar, here); -} - - -//insert a basic block with appropriate code -//along a given edge -void insertBB(Edge ed, - getEdgeCode *edgeCode, - Instruction *rInst, - Value *countInst, - int numPaths, int Methno, Value *threshold){ - - BasicBlock* BB1=ed.getFirst()->getElement(); - BasicBlock* BB2=ed.getSecond()->getElement(); - -#ifdef DEBUG_PATH_PROFILES - //debugging info - cerr<<"Edges with codes ######################\n"; - cerr<<BB1->getName()<<"->"<<BB2->getName()<<"\n"; - cerr<<"########################\n"; -#endif - - //We need to insert a BB between BB1 and BB2 - TerminatorInst *TI=BB1->getTerminator(); - BasicBlock *newBB=new BasicBlock("counter", BB1->getParent()); - - //get code for the new BB - vector<Value *> retVec; - - edgeCode->getCode(rInst, countInst, BB1->getParent(), newBB, retVec); - - BranchInst *BI = cast<BranchInst>(TI); - - //Is terminator a branch instruction? - //then we need to change branch destinations to include new BB - - if(BI->isUnconditional()){ - BI->setUnconditionalDest(newBB); - } - else{ - if(BI->getSuccessor(0)==BB2) - BI->setSuccessor(0, newBB); - - if(BI->getSuccessor(1)==BB2) - BI->setSuccessor(1, newBB); - } - - BasicBlock *triggerBB = NULL; - if(retVec.size()>0){ - triggerBB = new BasicBlock("trigger", BB1->getParent()); - getTriggerCode(BB1->getParent()->getParent(), triggerBB, Methno, - retVec[1], countInst, rInst);//retVec[0]); - - //Instruction *castInst = new CastInst(retVec[0], Type::IntTy, ""); - Instruction *etr = new LoadInst(threshold, "threshold"); - - //std::cerr<<"type1: "<<etr->getType()<<" type2: "<<retVec[0]->getType()<<"\n"; - Instruction *cmpInst = new SetCondInst(Instruction::SetLE, etr, - retVec[0], ""); - Instruction *newBI2 = new BranchInst(triggerBB, BB2, cmpInst); - //newBB->getInstList().push_back(castInst); - newBB->getInstList().push_back(etr); - newBB->getInstList().push_back(cmpInst); - newBB->getInstList().push_back(newBI2); - - //triggerBB->getInstList().push_back(triggerInst); - new BranchInst(BB2, 0, 0, triggerBB); - } - else{ - new BranchInst(BB2, 0, 0, newBB); - } - - //now iterate over BB2, and set its Phi nodes right - for(BasicBlock::iterator BB2Inst = BB2->begin(), BBend = BB2->end(); - BB2Inst != BBend; ++BB2Inst){ - - if(PHINode *phiInst=dyn_cast<PHINode>(BB2Inst)){ - int bbIndex=phiInst->getBasicBlockIndex(BB1); - assert(bbIndex>=0); - phiInst->setIncomingBlock(bbIndex, newBB); - - ///check if trigger!=null, then add value corresponding to it too! - if(retVec.size()>0){ - assert(triggerBB && "BasicBlock with trigger should not be null!"); - Value *vl = phiInst->getIncomingValue((unsigned int)bbIndex); - phiInst->addIncoming(vl, triggerBB); - } - } - } -} - -} // End llvm namespace diff --git a/lib/Transforms/Instrumentation/ProfilePaths/Graph.cpp b/lib/Transforms/Instrumentation/ProfilePaths/Graph.cpp deleted file mode 100644 index c8b1a0dfce..0000000000 --- a/lib/Transforms/Instrumentation/ProfilePaths/Graph.cpp +++ /dev/null @@ -1,569 +0,0 @@ -//===-- Graph.cpp - Implements Graph class --------------------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This implements Graph for helping in trace generation This graph gets used by -// "ProfilePaths" class. -// -//===----------------------------------------------------------------------===// - -#include "Graph.h" -#include "llvm/Instructions.h" -#include "llvm/Support/Debug.h" -#include <algorithm> - -using std::vector; - -namespace llvm { - -const graphListElement *findNodeInList(const Graph::nodeList &NL, - Node *N) { - for(Graph::nodeList::const_iterator NI = NL.begin(), NE=NL.end(); NI != NE; - ++NI) - if (*NI->element== *N) - return &*NI; - return 0; -} - -graphListElement *findNodeInList(Graph::nodeList &NL, Node *N) { - for(Graph::nodeList::iterator NI = NL.begin(), NE=NL.end(); NI != NE; ++NI) - if (*NI->element== *N) - return &*NI; - return 0; -} - -//graph constructor with root and exit specified -Graph::Graph(std::vector<Node*> n, std::vector<Edge> e, - Node *rt, Node *lt){ - strt=rt; - ext=lt; - for(vector<Node* >::iterator x=n.begin(), en=n.end(); x!=en; ++x) - //nodes[*x] = list<graphListElement>(); - nodes[*x] = vector<graphListElement>(); - - for(vector<Edge >::iterator x=e.begin(), en=e.end(); x!=en; ++x){ - Edge ee=*x; - int w=ee.getWeight(); - //nodes[ee.getFirst()].push_front(graphListElement(ee.getSecond(),w, ee.getRandId())); - nodes[ee.getFirst()].push_back(graphListElement(ee.getSecond(),w, ee.getRandId())); - } - -} - -//sorting edgelist, called by backEdgeVist ONLY!!! -Graph::nodeList &Graph::sortNodeList(Node *par, nodeList &nl, vector<Edge> &be){ - assert(par && "null node pointer"); - BasicBlock *bbPar = par->getElement(); - - if(nl.size()<=1) return nl; - if(getExit() == par) return nl; - - for(nodeList::iterator NLI = nl.begin(), NLE = nl.end()-1; NLI != NLE; ++NLI){ - nodeList::iterator min = NLI; - for(nodeList::iterator LI = NLI+1, LE = nl.end(); LI!=LE; ++LI){ - //if LI < min, min = LI - if(min->element->getElement() == LI->element->getElement() && - min->element == getExit()){ - - //same successors: so might be exit??? - //if it is exit, then see which is backedge - //check if LI is a left back edge! - - TerminatorInst *tti = par->getElement()->getTerminator(); - BranchInst *ti = cast<BranchInst>(tti); - - assert(ti && "not a branch"); - assert(ti->getNumSuccessors()==2 && "less successors!"); - - BasicBlock *tB = ti->getSuccessor(0); - BasicBlock *fB = ti->getSuccessor(1); - //so one of LI or min must be back edge! - //Algo: if succ(0)!=LI (and so !=min) then succ(0) is backedge - //and then see which of min or LI is backedge - //THEN if LI is in be, then min=LI - if(LI->element->getElement() != tB){//so backedge must be made min! - for(vector<Edge>::iterator VBEI = be.begin(), VBEE = be.end(); - VBEI != VBEE; ++VBEI){ - if(VBEI->getRandId() == LI->randId){ - min = LI; - break; - } - else if(VBEI->getRandId() == min->randId) - break; - } - } - else{// if(LI->element->getElement() != fB) - for(vector<Edge>::iterator VBEI = be.begin(), VBEE = be.end(); - VBEI != VBEE; ++VBEI){ - if(VBEI->getRandId() == min->randId){ - min = LI; - break; - } - else if(VBEI->getRandId() == LI->randId) - break; - } - } - } - - else if (min->element->getElement() != LI->element->getElement()){ - TerminatorInst *tti = par->getElement()->getTerminator(); - BranchInst *ti = cast<BranchInst>(tti); - assert(ti && "not a branch"); - - if(ti->getNumSuccessors()<=1) continue; - - assert(ti->getNumSuccessors()==2 && "less successors!"); - - BasicBlock *tB = ti->getSuccessor(0); - BasicBlock *fB = ti->getSuccessor(1); - - if(tB == LI->element->getElement() || fB == min->element->getElement()) - min = LI; - } - } - - graphListElement tmpElmnt = *min; - *min = *NLI; - *NLI = tmpElmnt; - } - return nl; -} - -//check whether graph has an edge -//having an edge simply means that there is an edge in the graph -//which has same endpoints as the given edge -bool Graph::hasEdge(Edge ed){ - if(ed.isNull()) - return false; - - nodeList &nli= nodes[ed.getFirst()]; //getNodeList(ed.getFirst()); - Node *nd2=ed.getSecond(); - - return (findNodeInList(nli,nd2)!=NULL); - -} - - -//check whether graph has an edge, with a given wt -//having an edge simply means that there is an edge in the graph -//which has same endpoints as the given edge -//This function checks, moreover, that the wt of edge matches too -bool Graph::hasEdgeAndWt(Edge ed){ - if(ed.isNull()) - return false; - - Node *nd2=ed.getSecond(); - nodeList &nli = nodes[ed.getFirst()];//getNodeList(ed.getFirst()); - - for(nodeList::iterator NI=nli.begin(), NE=nli.end(); NI!=NE; ++NI) - if(*NI->element == *nd2 && ed.getWeight()==NI->weight) - return true; - - return false; -} - -//add a node -void Graph::addNode(Node *nd){ - vector<Node *> lt=getAllNodes(); - - for(vector<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE;++LI){ - if(**LI==*nd) - return; - } - //chng - nodes[nd] =vector<graphListElement>(); //list<graphListElement>(); -} - -//add an edge -//this adds an edge ONLY when -//the edge to be added does not already exist -//we "equate" two edges here only with their -//end points -void Graph::addEdge(Edge ed, int w){ - nodeList &ndList = nodes[ed.getFirst()]; - Node *nd2=ed.getSecond(); - - if(findNodeInList(nodes[ed.getFirst()], nd2)) - return; - - //ndList.push_front(graphListElement(nd2,w, ed.getRandId())); - ndList.push_back(graphListElement(nd2,w, ed.getRandId()));//chng - //sortNodeList(ed.getFirst(), ndList); - - //sort(ndList.begin(), ndList.end(), NodeListSort()); -} - -//add an edge EVEN IF such an edge already exists -//this may make a multi-graph -//which does happen when we add dummy edges -//to the graph, for compensating for back-edges -void Graph::addEdgeForce(Edge ed){ - //nodes[ed.getFirst()].push_front(graphListElement(ed.getSecond(), - //ed.getWeight(), ed.getRandId())); - nodes[ed.getFirst()].push_back - (graphListElement(ed.getSecond(), ed.getWeight(), ed.getRandId())); - - //sortNodeList(ed.getFirst(), nodes[ed.getFirst()]); - //sort(nodes[ed.getFirst()].begin(), nodes[ed.getFirst()].end(), NodeListSort()); -} - -//remove an edge -//Note that it removes just one edge, -//the first edge that is encountered -void Graph::removeEdge(Edge ed){ - nodeList &ndList = nodes[ed.getFirst()]; - Node &nd2 = *ed.getSecond(); - - for(nodeList::iterator NI=ndList.begin(), NE=ndList.end(); NI!=NE ;++NI) { - if(*NI->element == nd2) { - ndList.erase(NI); - break; - } - } -} - -//remove an edge with a given wt -//Note that it removes just one edge, -//the first edge that is encountered -void Graph::removeEdgeWithWt(Edge ed){ - nodeList &ndList = nodes[ed.getFirst()]; - Node &nd2 = *ed.getSecond(); - - for(nodeList::iterator NI=ndList.begin(), NE=ndList.end(); NI!=NE ;++NI) { - if(*NI->element == nd2 && NI->weight==ed.getWeight()) { - ndList.erase(NI); - break; - } - } -} - -//set the weight of an edge -void Graph::setWeight(Edge ed){ - graphListElement *El = findNodeInList(nodes[ed.getFirst()], ed.getSecond()); - if (El) - El->weight=ed.getWeight(); -} - - - -//get the list of successor nodes -vector<Node *> Graph::getSuccNodes(Node *nd){ - nodeMapTy::const_iterator nli = nodes.find(nd); - assert(nli != nodes.end() && "Node must be in nodes map"); - const nodeList &nl = getNodeList(nd);//getSortedNodeList(nd); - - vector<Node *> lt; - for(nodeList::const_iterator NI=nl.begin(), NE=nl.end(); NI!=NE; ++NI) - lt.push_back(NI->element); - - return lt; -} - -//get the number of outgoing edges -int Graph::getNumberOfOutgoingEdges(Node *nd) const { - nodeMapTy::const_iterator nli = nodes.find(nd); - assert(nli != nodes.end() && "Node must be in nodes map"); - const nodeList &nl = nli->second; - - int count=0; - for(nodeList::const_iterator NI=nl.begin(), NE=nl.end(); NI!=NE; ++NI) - count++; - - return count; -} - -//get the list of predecessor nodes -vector<Node *> Graph::getPredNodes(Node *nd){ - vector<Node *> lt; - for(nodeMapTy::const_iterator EI=nodes.begin(), EE=nodes.end(); EI!=EE ;++EI){ - Node *lnode=EI->first; - const nodeList &nl = getNodeList(lnode); - - const graphListElement *N = findNodeInList(nl, nd); - if (N) lt.push_back(lnode); - } - return lt; -} - -//get the number of predecessor nodes -int Graph::getNumberOfIncomingEdges(Node *nd){ - int count=0; - for(nodeMapTy::const_iterator EI=nodes.begin(), EE=nodes.end(); EI!=EE ;++EI){ - Node *lnode=EI->first; - const nodeList &nl = getNodeList(lnode); - for(Graph::nodeList::const_iterator NI = nl.begin(), NE=nl.end(); NI != NE; - ++NI) - if (*NI->element== *nd) - count++; - } - return count; -} - -//get the list of all the vertices in graph -vector<Node *> Graph::getAllNodes() const{ - vector<Node *> lt; - for(nodeMapTy::const_iterator x=nodes.begin(), en=nodes.end(); x != en; ++x) - lt.push_back(x->first); - - return lt; -} - -//get the list of all the vertices in graph -vector<Node *> Graph::getAllNodes(){ - vector<Node *> lt; - for(nodeMapTy::const_iterator x=nodes.begin(), en=nodes.end(); x != en; ++x) - lt.push_back(x->first); - - return lt; -} - -//class to compare two nodes in graph -//based on their wt: this is used in -//finding the maximal spanning tree -struct compare_nodes { - bool operator()(Node *n1, Node *n2){ - return n1->getWeight() < n2->getWeight(); - } -}; - - -static void printNode(Node *nd){ - std::cerr<<"Node:"<<nd->getElement()->getName()<<"\n"; -} - -//Get the Maximal spanning tree (also a graph) -//of the graph -Graph* Graph::getMaxSpanningTree(){ - //assume connected graph - - Graph *st=new Graph();//max spanning tree, undirected edges - int inf=9999999;//largest key - vector<Node *> lt = getAllNodes(); - - //initially put all vertices in vector vt - //assign wt(root)=0 - //wt(others)=infinity - // - //now: - //pull out u: a vertex frm vt of min wt - //for all vertices w in vt, - //if wt(w) greater than - //the wt(u->w), then assign - //wt(w) to be wt(u->w). - // - //make parent(u)=w in the spanning tree - //keep pulling out vertices from vt till it is empty - - vector<Node *> vt; - - std::map<Node*, Node* > parent; - std::map<Node*, int > ed_weight; - - //initialize: wt(root)=0, wt(others)=infinity - //parent(root)=NULL, parent(others) not defined (but not null) - for(vector<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE; ++LI){ - Node *thisNode=*LI; - if(*thisNode == *getRoot()){ - thisNode->setWeight(0); - parent[thisNode]=NULL; - ed_weight[thisNode]=0; - } - else{ - thisNode->setWeight(inf); - } - st->addNode(thisNode);//add all nodes to spanning tree - //we later need to assign edges in the tree - vt.push_back(thisNode); //pushed all nodes in vt - } - - //keep pulling out vertex of min wt from vt - while(!vt.empty()){ - Node *u=*(std::min_element(vt.begin(), vt.end(), compare_nodes())); - DEBUG(std::cerr<<"popped wt"<<(u)->getWeight()<<"\n"; - printNode(u)); - - if(parent[u]!=NULL){ //so not root - Edge edge(parent[u],u, ed_weight[u]); //assign edge in spanning tree - st->addEdge(edge,ed_weight[u]); - - DEBUG(std::cerr<<"added:\n"; - printEdge(edge)); - } - - //vt.erase(u); - - //remove u frm vt - for(vector<Node *>::iterator VI=vt.begin(), VE=vt.end(); VI!=VE; ++VI){ - if(**VI==*u){ - vt.erase(VI); - break; - } - } - - //assign wt(v) to all adjacent vertices v of u - //only if v is in vt - Graph::nodeList &nl = getNodeList(u); - for(nodeList::iterator NI=nl.begin(), NE=nl.end(); NI!=NE; ++NI){ - Node *v=NI->element; - int weight=-NI->weight; - //check if v is in vt - bool contains=false; - for(vector<Node *>::iterator VI=vt.begin(), VE=vt.end(); VI!=VE; ++VI){ - if(**VI==*v){ - contains=true; - break; - } - } - DEBUG(std::cerr<<"wt:v->wt"<<weight<<":"<<v->getWeight()<<"\n"; - printNode(v);std::cerr<<"node wt:"<<(*v).weight<<"\n"); - - //so if v in in vt, change wt(v) to wt(u->v) - //only if wt(u->v)<wt(v) - if(contains && weight<v->getWeight()){ - parent[v]=u; - ed_weight[v]=weight; - v->setWeight(weight); - - DEBUG(std::cerr<<v->getWeight()<<":Set weight------\n"; - printGraph(); - printEdge(Edge(u,v,weight))); - } - } - } - return st; -} - -//print the graph (for debugging) -void Graph::printGraph(){ - vector<Node *> lt=getAllNodes(); - std::cerr<<"Graph---------------------\n"; - for(vector<Node *>::iterator LI=lt.begin(), |