path: root/lib/Transforms/Instrumentation/ProfilePaths/Graph.cpp

//===--Graph.cpp--- implements Graph class ---------------- ------*- C++ -*--=//
//
// This implements Graph for helping in trace generation
// This graph gets used by "ProfilePaths" class
//
//===----------------------------------------------------------------------===//

#include "Graph.h"
#include "llvm/BasicBlock.h"
#include <algorithm>
#include <iostream>

using std::list;
using std::set;
using std::map;
using std::vector;
using std::cerr;

static 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;
}

static 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::set<Node*> n, std::set<Edge> e, 
	     Node *rt, Node *lt){
  strt=rt;
  ext=lt;
  for(set<Node* >::iterator x=n.begin(), en=n.end(); x!=en; ++x)
    nodes[*x] = list<graphListElement>();

  for(set<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));   
  }
  
}

//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) const{
  if(ed.isNull())
    return false;

  nodeList nli=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) const{
  if(ed.isNull())
    return false;

  Node *nd2=ed.getSecond();
  nodeList nli=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){
  list<Node *> lt=getAllNodes();

  for(list<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE;++LI){
    if(**LI==*nd)
      return;
  }

  nodes[nd] = list<graphListElement>();
}

//add an edge
//this adds an edge ONLY when 
//the edge to be added doesn 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));
}

//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()));
}

//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;
    }
  }
}

//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
list<Node *> Graph::getSuccNodes(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;

  list<Node *> lt;
  for(nodeList::const_iterator NI=nl.begin(), NE=nl.end(); NI!=NE; ++NI)
    lt.push_back(NI->element);

  return lt;
}

//get the list of predecessor nodes
list<Node *> Graph::getPredNodes(Node *nd) const{
  list<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 list of all the vertices in graph
list<Node *> Graph::getAllNodes() const{
  list<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){
  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
  list<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;
  
  map<Node*, Node* > parent;
  map<Node*, int > ed_weight;

  //initialize: wt(root)=0, wt(others)=infinity
  //parent(root)=NULL, parent(others) not defined (but not null)
  for(list<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
    <