DGraphIterativeDFP.cpp

Go to the documentation of this file.

#include "DGraphIterativeDFP.hpp"
#include <Utils/Util.hpp>

#include <iostream>

namespace OA {
  namespace DataFlow {

static bool debug = false;

//*********************************************************************
// class DGraphIterativeDFP
//*********************************************************************

DGraphIterativeDFP::DGraphIterativeDFP()
{ 
    OA_DEBUG_CTRL_MACRO("DEBUG_DGraphIterativeDFP:ALL", debug);
    numIter = 0;
}


DGraphIterativeDFP::~DGraphIterativeDFP()
{
}


//-----------------------------------------------------------------------
// general default solver 
//-----------------------------------------------------------------------
void DGraphIterativeDFP::solve(OA_ptr<DGraph::DGraphInterface> dg, 
                               DGraph::DGraphEdgeDirection alongFlow) 
{

  //---------------------------------------------------------------
  // initialize dataflow information at each of the nodes and edges
  //---------------------------------------------------------------
  initialize(dg);


  //---------------------------------------------------------------
  // Kildall style iterative solver: iterate until dataflow 
  // information at each node and edge stabilizes
  //---------------------------------------------------------------
  unsigned int changed;

  OA_ptr<DGraph::NodeInterface> node;

  // get iterator for desired direction
  OA_ptr<DGraph::NodesIteratorInterface> nodeIterPtr
     = dg->getReversePostDFSIterator(alongFlow);  

  // loop until there are no changes
  int iterCnt = 0;
  do {
    changed = 0;
    iterCnt++;
    if (debug) {
        std::cout << "DGraphIterativeDFP (in loop), iterCnt = " << iterCnt << std::endl;
    }
    for (; nodeIterPtr->isValid(); ++(*nodeIterPtr)) {
      node = nodeIterPtr->current();
      if (debug) {
        std::cout << "node: Id = " << node->getId();
        std::cout << ", num_outgoing = " << node->num_outgoing();
        std::cout << ", OA_ptr::dump = ";
        node.dump(std::cout);
        std::cout << std::endl;
      }

      //--------------------------------------------------
      // compute dataflow information at node based on
      // what is coming into the node along the dataflow
      // direction
      //--------------------------------------------------
      changed |= atDGraphNode(node, alongFlow);

      //--------------------------------------------------
      // compute dataflow information going out of the node
      // along dataflow direction
      //--------------------------------------------------

      OA_ptr<DGraph::EdgesIteratorInterface> edgeIterPtr;
      if (alongFlow==DGraph::DEdgeOrg) {  // follows original orientation of edges

        OA_ptr<DGraph::EdgesIteratorInterface> it = 
          node->getOutgoingEdgesIterator();  
        edgeIterPtr = it;
      } else {
        
       
        OA_ptr<DGraph::EdgesIteratorInterface> it =
          node->getIncomingEdgesIterator();  
        edgeIterPtr = it;
      }
      for (; edgeIterPtr->isValid(); ++(*edgeIterPtr)) {
        changed |= atDGraphEdge(edgeIterPtr->current(), alongFlow);
      }

    } // end for all nodes

    nodeIterPtr->reset();

  } while (changed);


  //---------------------------------------------------------------
  // finalize dataflow information at each of the nodes and edges
  //---------------------------------------------------------------
  for (; nodeIterPtr->isValid(); ++(*nodeIterPtr)) {
    node = nodeIterPtr->current();
    finalizeNode(node);

    OA::OA_ptr<DGraph::EdgesIteratorInterface> edgeIterPtr;
    if (alongFlow==DGraph::DEdgeOrg) {  // follows original orientation of edges

        OA::OA_ptr<DGraph::EdgesIteratorInterface> it =
            node->getOutgoingEdgesIterator();  
      edgeIterPtr = it;
    } else {

      OA_ptr<DGraph::EdgesIteratorInterface> it =
          node->getIncomingEdgesIterator();
      edgeIterPtr = it;
    }
    for (; edgeIterPtr->isValid(); ++(*edgeIterPtr)) {
      finalizeEdge(edgeIterPtr->current());
    }

  }

  numIter = iterCnt; // set value for retrieval
  if (debug) { 
      std::cout << "DGraphIterativeDFP: iterCnt = " << iterCnt << std::endl;
  }
  return;

}


//-----------------------------------------------------------------------
// solver callbacks
//-----------------------------------------------------------------------
bool DGraphIterativeDFP::atDGraphNode
     (OA_ptr<DGraph::NodeInterface>, DGraph::DGraphEdgeDirection)
{
    
    return false;
}



bool DGraphIterativeDFP::atDGraphEdge
     (OA_ptr<DGraph::EdgeInterface>, DGraph::DGraphEdgeDirection)
{
    return false;
}



//-----------------------------------------------------------------------
// finalization callbacks
//-----------------------------------------------------------------------


 void DGraphIterativeDFP::finalizeEdge(OA_ptr<DGraph::EdgeInterface>)
{
}


 void DGraphIterativeDFP::finalizeNode(OA_ptr<DGraph::NodeInterface>)
{
}

  } // end of DataFlow namespace
}  // end of OA namespace