//-*-c++-*-
/**
 Author: David Auber
 Email : auber@labri.fr
 Last modification : 31/10/2001
 This program is free software; you can redistribute it and/or modify
 it under the terms of the GNU General Public License as published by  
 the Free Software Foundation; either version 2 of the License, or     
 (at your option) any later version.
*/

#include <tulip/TulipPlugin.h>

using namespace std;

struct PathSumMetric:public Metric
{
  PathSumMetric(PropertyContext *context):Metric(context){}
  ~PathSumMetric(){}

  bool run()
  {
    list<node> fifo;
    STL_EXT_NS::hash_map<node,bool> isIn(superGraph->numberOfNodes());

    metricProxy->setAllNodeValue(0);
    metricProxy->setAllEdgeValue(0);

    Iterator<node> *itN=superGraph->getNodes();
    for (;itN->hasNext();) {
      node itn=itN->next();
      if (superGraph->indeg(itn)==0){
	fifo.push_back(itn);
	metricProxy->setNodeValue(itn,1);
	isIn[itn]=true;
      }
    }delete itN;

    while(!fifo.empty()) {
      node itn=fifo.front();
      fifo.pop_front();
      double curValue=metricProxy->getNodeValue(itn);
      itN=superGraph->getOutNodes(itn);
      for (;itN->hasNext();)
	{
	  node itChild=itN->next();
	  metricProxy->setNodeValue(itChild,metricProxy->getNodeValue(itChild)+curValue);
	  bool addNode=true;
	  Iterator<node> *itN2=superGraph->getInNodes(itChild);
	  for (;itN2->hasNext();) {
	    node inNode=itN2->next();
	    if (isIn.find(inNode)==isIn.end()) {
	      addNode=false;
	      break;
	    }
	  } delete itN2;
	  if (addNode && (isIn.find(itChild)==isIn.end()) )  {
	    fifo.push_back(itChild);
	    isIn[itChild]=true;
	  }
	} delete itN;
    }
    return true;
  }

  bool check(string &errorMsg)
  {
    if (!superGraph->isAcyclic())
      {
	errorMsg="The graph must be acyclic";
	return false;
      }
    return true;
  }
};

METRICPLUGIN(PathSumMetric,"Path Sum","Auber", "31/10/2001","0","0","1");