SCC.cpp

Go to the documentation of this file.

//************************** System Include Files ***************************

#include <cassert>

#include <map>
#include <set>
#include <stack>

//*************************** User Include Files ****************************

#include <OpenAnalysis/Utils/SCC.hpp>
#include <OpenAnalysis/Utils/Util.hpp>

//*************************** Forward Declarations **************************

//------------------------------------------------------------------------
// LowLinkState is a private data structure used for finding SCC
// components.
//------------------------------------------------------------------------

namespace OA {

class LowLinkState {
public:
  LowLinkState(OA::OA_ptr<OA::RIFG> rifg_) : rifg(rifg_), mCount(1) { 
    unsigned int sz = rifg->getHighWaterMarkNodeId() + 1;
    mNodeStatus = new SCCNodeStatus[sz];
  }
  
  ~LowLinkState() { 
    delete[] mNodeStatus;
  }
  
  // Mark methods
  void Mark(OA::RIFG::NodeId nid) 
    { mOld.insert(nid); }
  unsigned int IsMarked(OA::RIFG::NodeId nid) { 
    MyNodeIdSet::const_iterator it = mOld.find(nid);
    return (it != mOld.end()); 
  }

  // Lowlink and depth-first methods
  unsigned int& LOWLINK(OA::RIFG::NodeId nid) 
    { return mNodeStatus[nid].lowlink; }

  unsigned int& DFNUMBER(OA::RIFG::NodeId nid) 
    { return mNodeStatus[nid].dfnumber; }
  
  unsigned int& Count() 
    { return mCount; }
  
  // Stack methods
  void Push(OA_ptr<DGraph::Interface::Node> node, OA::RIFG::NodeId nid) {
    mNodeStatus[nid].inStack = true;
    mNodeStack.push(node);
  }
  
  OA_ptr<DGraph::Interface::Node> Top()
    { return mNodeStack.top(); }

  OA_ptr<DGraph::Interface::Node> Pop() {
    OA_ptr<DGraph::Interface::Node> node = mNodeStack.top();
    OA::RIFG::NodeId nid = rifg->getNodeId(node);
    mNodeStack.pop();
    mNodeStatus[nid].inStack = false;
    return node; 
  }
  
  bool IsOnStack(OA::RIFG::NodeId nid) 
    { return mNodeStatus[nid].inStack; }

private:
  
  // SCCNodeStatus is a data structure to describe the current status
  // of a SCC node.
  class SCCNodeStatus {
  public:
    SCCNodeStatus(unsigned int l=0, unsigned int d=0, bool i=false)
      : lowlink(l), dfnumber(d), inStack(i) { }
    
    unsigned int lowlink;
    unsigned int dfnumber;
    bool inStack;
  };

  typedef std::set<OA::RIFG::NodeId> MyNodeIdSet;

  typedef std::stack<OA_ptr<DGraph::Interface::Node> > MyNodeStack;
  
private:
  OA::OA_ptr<OA::RIFG> rifg;

  unsigned int mCount;
  SCCNodeStatus* mNodeStatus; // indexed by OA::RIFG::NodeId
  MyNodeIdSet mOld;
  MyNodeStack mNodeStack;
};

} // end of namespace OA


//*************************** Forward Declarations **************************

static void 
CreateHelper(OA::SCCSet* sccSet, 
             OA::OA_ptr<OA::RIFG> rifg,
             OA::OA_ptr<OA::DGraph::Interface::Node> v, 
             OA::RIFG::NodeId vid,
             OA::LowLinkState* state);


//***************************************************************************


//***************************************************************************
// SCCSet
//***************************************************************************

namespace OA {

SCCSet::SCCSet() 
{
}


SCCSet::SCCSet(OA_ptr<DGraph::Interface> graph,
               OA_ptr<RIFG> rifg) 
{
  if (rifg.ptrEqual(0)) {
    rifg = new OA::RIFG(graph, RIFG::getSourceNode(graph), 
                        RIFG::getSinkNode(graph));
  }
  // assert(rifg->getGraph() == graph);
  Create(graph, rifg);
}


void
SCCSet::Create(OA_ptr<DGraph::Interface> graph,
               OA_ptr<RIFG> rifg)
{
  // Note: We use a RIFG in order to get dense node ids between 1 and n.
  LowLinkState *state = new LowLinkState(rifg);
  //LowLinkState *state = &ST;
  
  // if there exists a node not marked yet, visit it.
  OA_ptr<DGraph::Interface::NodesIterator> it = graph->getNodesIterator();
  for (; it->isValid(); ++(*it)) {
    OA_ptr<DGraph::Interface::Node> node = it->current();
    OA::RIFG::NodeId nid = rifg->getNodeId(node);
    if ( !state->IsMarked(nid) ) {
      CreateHelper(this, rifg, node, nid, state);
    }
  }
}


SCCSet::~SCCSet()
{
  Destroy();
}


void
SCCSet::Destroy()
{
  this->clear();
}


OA_ptr<SCCNodeSet> 
SCCSet::NodeToSCC(const OA_ptr<DGraph::Interface::Node> node)
{
  // N.B.: The implementation is a linear search and direct
  // translation from the DSystem code.  However, if this is going to
  // be used a lot, we should probably create a map.
  for (self_t::const_iterator it = this->begin(); it != this->end(); ++it) {
    OA_ptr<SCCNodeSet> scc = *it;
    if (scc->find(node) != scc->end()) {
      return scc;
    }
  }
  assert(false);               // every node should be in a set
  return OA_ptr<SCCNodeSet>(); // never reached!
}


void 
SCCSet::dump(std::ostream& os)
{
  using std::endl;

  os << "{ SCCSet: num SCC sets: " << this->size() << endl;
  for (self_t::iterator it = this->begin(); it != this->end(); ++it) {
    OA_ptr<SCCNodeSet> scc = *it;
    
    os << "  { SCC: ";
    SCCNodeSet::iterator sccIt = scc->begin();
    for ( ; sccIt != scc->end(); ++sccIt) {
      OA_ptr<DGraph::Interface::Node> node = *sccIt;
      os << node->getId() << " ";
    }
    os << "}" << endl;
  } 
}


} // end of namespace OA


//***************************************************************************
// SCCSet helpers
//***************************************************************************

static void 
CreateHelper(OA::SCCSet* sccSet, 
             OA::OA_ptr<OA::RIFG> rifg,
             OA::OA_ptr<OA::DGraph::Interface::Node> v, 
             OA::RIFG::NodeId vid,
             OA::LowLinkState* state)
{
  using namespace OA;
  
  state->Mark(vid);                           // mark v
  state->DFNUMBER(vid) = state->Count();      // set dfnumber
  state->Count()++;                           // increment count by 1
  state->LOWLINK(vid) = state->DFNUMBER(vid); // set lowlink number
  state->Push(v, vid);                        // push v into stack
  
  // for each w which is on the adjacency list of v, there is an edge v->w
  OA::OA_ptr<OA::DGraph::Interface::NodesIterator> it = 
    v->getSinkNodesIterator();
  for (; it->isValid(); ++(*it)) {
    OA_ptr<DGraph::Interface::Node> w = it->current();
    OA::RIFG::NodeId wid = rifg->getNodeId(w);
    
    // if w is not marked yet
    if (!state->IsMarked(wid)) { 
      CreateHelper(sccSet, rifg, w, wid, state); 
      state->LOWLINK(vid) = OA_MIN(state->LOWLINK(vid), state->LOWLINK(wid));
    } 
    // w is already marked
    else {
      if ( state->DFNUMBER(wid) < state->DFNUMBER(vid) && 
           state->IsOnStack(wid) ) {
        state->LOWLINK(vid) = OA_MIN(state->DFNUMBER(wid), 
                                     state->LOWLINK(vid));
      }
    }
  }

  // if lowlink[v] == DFNumber[v], the current Node in stack above
  // v form a SCC. 
  if ( state->LOWLINK(vid) == state->DFNUMBER(vid) ) {
    OA_ptr<SCCNodeSet> scc; scc = new SCCNodeSet;
    
    // pop x from top of stack, until x == v
    OA_ptr<DGraph::Interface::Node> x;
    do {
      x = state->Pop();
      scc->insert(x);
    } while (x != v);

    // the SCC is complete now, add it to sccSet.
    sccSet->insert(scc);
  }
}

---