1 //===--Graph.cpp--- implements Graph class ---------------- ------*- C++ -*--=//
3 // This implements Graph for helping in trace generation
4 // This graph gets used by "PathProfile" class
6 //===----------------------------------------------------------------------===//
9 #include "llvm/BasicBlock.h"
12 static const graphListElement *findNodeInList(const Graph::nodeList &NL,
14 for(Graph::nodeList::const_iterator NI = NL.begin(), NE=NL.end(); NI != NE;
16 if (*NI->element== *N)
21 static graphListElement *findNodeInList(Graph::nodeList &NL, Node *N) {
22 for(Graph::nodeList::iterator NI = NL.begin(), NE=NL.end(); NI != NE; ++NI)
23 if (*NI->element== *N)
28 //graph constructor with root and exit specified
29 Graph::Graph(std::set<Node*> n, std::set<Edge> e,
33 for(set<Node* >::iterator x=n.begin(), en=n.end(); x!=en; ++x)
34 nodes[*x] = list<graphListElement>();
36 for(set<Edge >::iterator x=e.begin(), en=e.end(); x!=en; ++x){
39 nodes[ee.getFirst()].push_front(graphListElement(ee.getSecond(),w));
44 //check whether graph has an edge
45 //having an edge simply means that there is an edge in the graph
46 //which has same endpoints as the given edge
47 bool Graph::hasEdge(Edge ed) const{
51 nodeList nli=getNodeList(ed.getFirst());
52 Node *nd2=ed.getSecond();
54 return (findNodeInList(nli,nd2)!=NULL);
59 //check whether graph has an edge, with a given wt
60 //having an edge simply means that there is an edge in the graph
61 //which has same endpoints as the given edge
62 //This function checks, moreover, that the wt of edge matches too
63 bool Graph::hasEdgeAndWt(Edge ed) const{
67 Node *nd2=ed.getSecond();
68 nodeList nli=getNodeList(ed.getFirst());
70 for(nodeList::iterator NI=nli.begin(), NE=nli.end(); NI!=NE; ++NI)
71 if(*NI->element == *nd2 && ed.getWeight()==NI->weight)
78 void Graph::addNode(Node *nd){
79 list<Node *> lt=getAllNodes();
81 for(list<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE;++LI){
86 nodes[nd] = list<graphListElement>();
90 //this adds an edge ONLY when
91 //the edge to be added doesn not already exist
92 //we "equate" two edges here only with their
94 void Graph::addEdge(Edge ed, int w){
95 nodeList &ndList = nodes[ed.getFirst()];
96 Node *nd2=ed.getSecond();
98 if(findNodeInList(nodes[ed.getFirst()], nd2))
101 ndList.push_front(graphListElement(nd2,w));
104 //add an edge EVEN IF such an edge already exists
105 //this may make a multi-graph
106 //which does happen when we add dummy edges
107 //to the graph, for compensating for back-edges
108 void Graph::addEdgeForce(Edge ed){
109 nodes[ed.getFirst()].push_front(graphListElement(ed.getSecond(),
114 //Note that it removes just one edge,
115 //the first edge that is encountered
116 void Graph::removeEdge(Edge ed){
117 nodeList &ndList = nodes[ed.getFirst()];
118 Node &nd2 = *ed.getSecond();
120 for(nodeList::iterator NI=ndList.begin(), NE=ndList.end(); NI!=NE ;++NI) {
121 if(*NI->element == nd2) {
128 //set the weight of an edge
129 void Graph::setWeight(Edge ed){
130 graphListElement *El = findNodeInList(nodes[ed.getFirst()], ed.getSecond());
132 El->weight=ed.getWeight();
137 //get the list of successor nodes
138 list<Node *> Graph::getSuccNodes(Node *nd) const {
139 nodeMapTy::const_iterator nli = nodes.find(nd);
140 assert(nli != nodes.end() && "Node must be in nodes map");
141 const nodeList &nl = nli->second;
144 for(nodeList::const_iterator NI=nl.begin(), NE=nl.end(); NI!=NE; ++NI)
145 lt.push_back(NI->element);
150 //get the list of predecessor nodes
151 list<Node *> Graph::getPredNodes(Node *nd) const{
153 for(nodeMapTy::const_iterator EI=nodes.begin(), EE=nodes.end(); EI!=EE ;++EI){
154 Node *lnode=EI->first;
155 const nodeList &nl = getNodeList(lnode);
157 const graphListElement *N = findNodeInList(nl, nd);
158 if (N) lt.push_back(lnode);
163 //get the list of all the vertices in graph
164 list<Node *> Graph::getAllNodes() const{
166 for(nodeMapTy::const_iterator x=nodes.begin(), en=nodes.end(); x != en; ++x)
167 lt.push_back(x->first);
173 //class to compare two nodes in graph
174 //based on their wt: this is used in
175 //finding the maximal spanning tree
176 struct compare_nodes {
177 bool operator()(Node *n1, Node *n2){
178 return n1->getWeight() < n2->getWeight();
183 void printNode(Node *nd){
184 cerr<<"Node:"<<nd->getElement()->getName()<<endl;
187 //Get the Maximal spanning tree (also a graph)
189 Graph* Graph::getMaxSpanningTree(){
190 //assume connected graph
192 Graph *st=new Graph();//max spanning tree, undirected edges
193 int inf=9999999;//largest key
194 list<Node *> lt = getAllNodes();
196 //initially put all vertices in vector vt
198 //wt(others)=infinity
201 //pull out u: a vertex frm vt of min wt
202 //for all vertices w in vt,
203 //if wt(w) greater than
204 //the wt(u->w), then assign
205 //wt(w) to be wt(u->w).
207 //make parent(u)=w in the spanning tree
208 //keep pulling out vertices from vt till it is empty
212 map<Node*, Node* > parent;
213 map<Node*, int > ed_weight;
215 //initialize: wt(root)=0, wt(others)=infinity
216 //parent(root)=NULL, parent(others) not defined (but not null)
217 for(list<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE; ++LI){
219 if(*thisNode == *getRoot()){
220 thisNode->setWeight(0);
221 parent[thisNode]=NULL;
222 ed_weight[thisNode]=0;
225 thisNode->setWeight(inf);
227 st->addNode(thisNode);//add all nodes to spanning tree
228 //we later need to assign edges in the tree
229 vt.push_back(thisNode); //pushed all nodes in vt
232 //keep pulling out vertex of min wt from vt
234 Node *u=*(min_element(vt.begin(), vt.end(), compare_nodes()));
235 #ifdef DEBUG_PATH_PROFILES
236 cerr<<"popped wt"<<(u)->getWeight()<<endl;
239 if(parent[u]!=NULL){ //so not root
240 Edge edge(parent[u],u, ed_weight[u]); //assign edge in spanning tree
241 st->addEdge(edge,ed_weight[u]);
242 #ifdef DEBUG_PATH_PROFILES
251 for(vector<Node *>::iterator VI=vt.begin(), VE=vt.end(); VI!=VE; ++VI){
258 //assign wt(v) to all adjacent vertices v of u
260 Graph::nodeList nl=getNodeList(u);
261 for(nodeList::iterator NI=nl.begin(), NE=nl.end(); NI!=NE; ++NI){
263 int weight=-NI->weight;
264 //check if v is in vt
266 for(vector<Node *>::iterator VI=vt.begin(), VE=vt.end(); VI!=VE; ++VI){
272 #ifdef DEBUG_PATH_PROFILES
273 cerr<<"wt:v->wt"<<weight<<":"<<v->getWeight()<<endl;
274 printNode(v);cerr<<"node wt:"<<(*v).weight<<endl;
276 //so if v in in vt, change wt(v) to wt(u->v)
277 //only if wt(u->v)<wt(v)
278 if(contains && weight<v->getWeight()){
281 v->setWeight(weight);
282 #ifdef DEBUG_PATH_PROFILES
283 cerr<<v->getWeight()<<":Set weight------\n";
285 printEdge(Edge(u,v,weight));
293 //print the graph (for debugging)
294 void Graph::printGraph(){
295 list<Node *> lt=getAllNodes();
296 cerr<<"Graph---------------------\n";
297 for(list<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE; ++LI){
298 cerr<<((*LI)->getElement())->getName()<<"->";
299 Graph::nodeList nl=getNodeList(*LI);
300 for(Graph::nodeList::iterator NI=nl.begin(), NE=nl.end(); NI!=NE; ++NI){
301 cerr<<":"<<"("<<(NI->element->getElement())
302 ->getName()<<":"<<NI->element->getWeight()<<","<<NI->weight<<")";
309 //get a list of nodes in the graph
310 //in r-topological sorted order
311 //note that we assumed graph to be connected
312 list<Node *> Graph::reverseTopologicalSort() const{
313 list <Node *> toReturn;
314 list<Node *> lt=getAllNodes();
315 for(list<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE; ++LI){
316 if((*LI)->getWeight()!=GREY && (*LI)->getWeight()!=BLACK)
317 DFS_Visit(*LI, toReturn);
322 //a private method for doing DFS traversal of graph
323 //this is used in determining the reverse topological sort
325 void Graph::DFS_Visit(Node *nd, list<Node *> &toReturn) const {
327 list<Node *> lt=getSuccNodes(nd);
328 for(list<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE; ++LI){
329 if((*LI)->getWeight()!=GREY && (*LI)->getWeight()!=BLACK)
330 DFS_Visit(*LI, toReturn);
332 toReturn.push_back(nd);
335 //Ordinarily, the graph is directional
336 //this converts the graph into an
337 //undirectional graph
338 //This is done by adding an edge
339 //v->u for all existing edges u->v
340 void Graph::makeUnDirectional(){
341 list<Node* > allNodes=getAllNodes();
342 for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
344 nodeList nl=getNodeList(*NI);
345 for(nodeList::iterator NLI=nl.begin(), NLE=nl.end(); NLI!=NLE; ++NLI){
346 Edge ed(NLI->element, *NI, NLI->weight);
347 if(!hasEdgeAndWt(ed)){
348 #ifdef DEBUG_PATH_PROFILES
349 cerr<<"######doesn't hv\n";
358 //reverse the sign of weights on edges
359 //this way, max-spanning tree could be obtained
360 //usin min-spanning tree, and vice versa
361 void Graph::reverseWts(){
362 list<Node *> allNodes=getAllNodes();
363 for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
365 nodeList node_list=getNodeList(*NI);
366 for(nodeList::iterator NLI=nodes[*NI].begin(), NLE=nodes[*NI].end();
368 NLI->weight=-NLI->weight;
373 //getting the backedges in a graph
374 //Its a variation of DFS to get the backedges in the graph
375 //We get back edges by associating a time
376 //and a color with each vertex.
377 //The time of a vertex is the time when it was first visited
378 //The color of a vertex is initially WHITE,
379 //Changes to GREY when it is first visited,
380 //and changes to BLACK when ALL its neighbors
382 //So we have a back edge when we meet a successor of
383 //a node with smaller time, and GREY color
384 void Graph::getBackEdges(vector<Edge > &be) const{
385 map<Node *, Color > color;
387 list<Node *> allNodes=getAllNodes();
389 for(list<Node *>::const_iterator NI=allNodes.begin(), NE=allNodes.end();
391 if(color[*NI]!=GREY && color[*NI]!=BLACK)
392 getBackEdgesVisit(*NI, be, color, d, time);
396 //helper function to get back edges: it is called by
397 //the "getBackEdges" function above
398 void Graph::getBackEdgesVisit(Node *u, vector<Edge > &be,
399 map<Node *, Color > &color,
400 map<Node *, int > &d, int &time) const{
404 list<Node *> succ_list=getSuccNodes(u);
406 for(list<Node *>::const_iterator v=succ_list.begin(), ve=succ_list.end();
408 if(color[*v]!=GREY && color[*v]!=BLACK){
409 getBackEdgesVisit(*v, be, color, d, time);
412 //now checking for d and f vals
414 //so v is ancestor of u if time of u > time of v
416 Edge *ed=new Edge(u, *v);
417 if (!(*u == *getExit() && **v == *getRoot()))
418 be.push_back(*ed); // choose the forward edges
422 color[u]=BLACK;//done with visiting the node and its neighbors