dominatorTreesAndDominanceFrontiers/SimpleDirectedGraph.h

Go to the documentation of this file.

#ifndef _SIMPLE_DIRECTED_GRAPH_H_
#define _SIMPLE_DIRECTED_GRAPH_H_

#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <stack>

// DQ (12/30/2005): This is a Bad Bad thing to do (I can explain)
// it hides names in the global namespace and causes errors in 
// otherwise valid and useful code. Where it is needed it should
// appear only in *.C files (and only ones not included for template 
// instantiation reasons) else they effect user who use ROSE unexpectedly.
// using namespace std;

class SimpleDirectedGraphNode {
      

public:
  
      ~SimpleDirectedGraphNode() {}
      
  std::set<SimpleDirectedGraphNode *> getSuccessors() {return _succs;}
  std::set<SimpleDirectedGraphNode *> getPredecessors() {return _preds;}
  
  void addSuccessor(SimpleDirectedGraphNode * n) {_succs.insert(n);}
  void addPredecessor(SimpleDirectedGraphNode * n) {_preds.insert(n);}
  
  bool hasSuccessor(SimpleDirectedGraphNode * n) {return _succs.count(n) != 0;}
  bool hasPredecessor(SimpleDirectedGraphNode * n) {return _preds.count(n) != 0;}

  int numSuccessors() {return _succs.size();}
  int numPredecessors() {return _preds.size();}
  
  virtual void writeOut(std::ostream & os) {
    char buf[sizeof(SimpleDirectedGraphNode *)*2 + 3];
    sprintf(buf, "%p", this);
    os << buf;
  }
  
 private:
  
  std::set<SimpleDirectedGraphNode *> _succs;
  std::set<SimpleDirectedGraphNode *> _preds;
  
};


class SimpleDirectedGraph {

public:

      ~SimpleDirectedGraph() {}

  std::set<SimpleDirectedGraphNode *> getNodes() {return _nodes;}

  virtual void addNode(SimpleDirectedGraphNode * node) {
    _nodes.insert(node);
  }

  virtual void addLink(SimpleDirectedGraphNode * from, SimpleDirectedGraphNode * to) {

    // Add "to" to the successors of "from" and "from" to the
    // predecessors of "to" to initialize the edge in the graph
    from->addSuccessor(to);
    to->addPredecessor(from);
  }

  bool nodeExists(SimpleDirectedGraphNode * node) {
    return _nodes.count(node) > 0;
  }

  bool linkExists(SimpleDirectedGraphNode * from, SimpleDirectedGraphNode * to) {
    return from->hasSuccessor(to);
  }
  
  void printGraph() {
    std::set<SimpleDirectedGraphNode *>::iterator i;
    for (i = _nodes.begin(); i != _nodes.end(); i++) {
      _displayData(*i, std::cout);
      std::cout << ":" << std::endl;
      std::set<SimpleDirectedGraphNode *> succs = (*i)->getSuccessors();
      std::set<SimpleDirectedGraphNode *>::iterator j;
      for (j = succs.begin(); j != succs.end(); j++) {
        std::cout << "    succ: ";
        _displayData(*j, std::cout);
        std::cout << std::endl;
      }
      std::set<SimpleDirectedGraphNode *> preds = (*i)->getPredecessors();
      for (j = preds.begin(); j != preds.end(); j++) {
        std::cout << "    pred: ";
        _displayData(*j, std::cout);
        std::cout << std::endl;
      }
      std::cout << std::endl;
    }
  }

  virtual void writeDot(char * filename) {

    std::ofstream f(filename);

    f << "digraph \"G" << filename << "\" {" << std::endl;
    //output all of the nodes
    std::set<SimpleDirectedGraphNode *>::iterator i;
    for (i = _nodes.begin(); i != _nodes.end(); i++) {
      SimpleDirectedGraphNode * d = *i;
      char buf[sizeof(SimpleDirectedGraphNode *)*2 + 3];
      sprintf(buf, "%p", d);
      f << "\"" << buf << "\" [label = \"";
      _displayData(d, f);
      f << "\"];" << std::endl;
    }

    //output all of the edges (we'll just use successor edges
    for (i = _nodes.begin(); i != _nodes.end(); i++) {
      SimpleDirectedGraphNode * d1 = *i;
      std::set<SimpleDirectedGraphNode *> succs = d1->getSuccessors();
      std::set<SimpleDirectedGraphNode *>::iterator j;
      for (j = succs.begin(); j != succs.end(); j++) {
        SimpleDirectedGraphNode * d2 = *j;
        
        char buf1[sizeof(SimpleDirectedGraphNode *)*2 + 3];
        char buf2[sizeof(SimpleDirectedGraphNode *)*2 + 3];
        
        sprintf(buf1, "%p", d1);
        sprintf(buf2, "%p", d2);

        f << "\"" << buf1 << "\" -> \"" << buf2 << "\";" << std::endl;
      }
    }

    f << "}" << std::endl;
  }
  
  enum TraverseDirection // NO_STRINGIFY
  {
    FORWARD  = 1,    
    BACKWARD = 2   
  };

  std::set<SimpleDirectedGraphNode *> getReachable(SimpleDirectedGraphNode * start, TraverseDirection dir) {
    
    std::set<SimpleDirectedGraphNode *> reachables;
    std::stack<SimpleDirectedGraphNode *> remaining;

    remaining.push(start);

    //Simple DFS on graph to find reachable nodes
    while (remaining.size() != 0) {
      //Get the first node on the stack
      SimpleDirectedGraphNode * curr = remaining.top();
      remaining.pop();
      
      //if we haven't already seen it, add it to our return list, and
      //push its children onto the stack
      if (reachables.count(curr) == 0) {
        reachables.insert(curr);

        //depending on TraverseDirection, children should either be
        //the successors or predecessors of curr
        std::set<SimpleDirectedGraphNode *> children;
        switch(dir) {
        case FORWARD:
          children = curr->getSuccessors();
          break;
        case BACKWARD:
          children = curr->getPredecessors();
          break;
        default:
          //This should never happen
          abort();
          break;
        }

        //push the children onto the stack
        std::set<SimpleDirectedGraphNode *>::iterator i;
        for (i = children.begin(); i != children.end(); i++) {
          remaining.push(*i);
        }
      } else {
        //Do nothing - we've already seen this node
      }
    }

    return reachables;
  }

protected:
  
  virtual void _displayData(SimpleDirectedGraphNode * node, std::ostream & os) {
    node->writeOut(os);
  }
  
  std::set<SimpleDirectedGraphNode *> _nodes;
  
};

#endif