#include <set>
#include <stdio.h>
#include <math.h>
#include <sstream>
#include <tulip/SuperGraph.h>
#include <tulip/MetaGraphProxy.h>
#include <tulip/SubGraph.h>
#include <tulip/TlpTools.h>
#include <tulip/Cluster.h>

#include "QuotientClustering.h"


CLUSTERINGPLUGIN(QuotientClustering,"QuotientClustering","David Auber","13/06/2001","Alpha","0","1");

using namespace std;

struct edgeS {
  unsigned  source,target;
};

namespace std {
  template <> struct less<edgeS> {
    bool operator()(const edgeS &c,const edgeS &d) const {
      if (c.source<d.source) return true;
      if (c.source>d.source) return false;
      if (c.target<d.target) return true;
      if (c.target>d.target) return false;
      return false;
    }
  };
};
//================================================================================
QuotientClustering::QuotientClustering(ClusterContext context):Clustering(context) {}
//================================================================================
QuotientClustering::~QuotientClustering(){}

namespace STL_EXT_NS {
  template <> struct hash<double> {
    size_t operator()(const double s) const { return (size_t)s; }
  };
};
//===============================================================================
bool QuotientClustering::run() {
  SuperGraph *quotientGraph=TlpTools::newSubGraph(superGraph->getClusterTree()->getRootSubGraph()->getAssociatedSuperGraph());
  SubGraph *quotientSubGraph=quotientGraph->getSubGraph();
  MetaGraphProxy *meta=getProxy<MetaGraphProxy>(quotientGraph,"viewMetaGraph");
  //parcourir tous les sous graphe du graphe courant.
  //et construit les metanoeud dans le quotient graphe.
  SubGraph *graph= superGraph->getSubGraph();
  map<SubGraph*,node> mapping;
  std::list<SubGraph *> *subgraphs=graph->getSubGraphChildren();
  for (std::list<SubGraph *>::iterator it=subgraphs->begin();it!=subgraphs->end();++it) {
    if ((*it)!=quotientSubGraph) {
      node n=quotientGraph->addNode();
      meta->setNodeValue(n,(*it)->getAssociatedSuperGraph());
      mapping[(*it)]=n;
    }
  }

  set<edgeS> myQuotientGraph;
  Iterator<edge>*itE=superGraph->getEdges();
  for (;itE->hasNext();) {
    edge ite=itE->next();
    node source=superGraph->source(ite);
    node target=superGraph->target(ite);
    list<SubGraph *> clusterSource;
    list<SubGraph *> clusterTarget;
    clusterSource.clear();
    clusterTarget.clear();
    
    for (std::list<SubGraph *>::iterator it=subgraphs->begin();it!=subgraphs->end();++it) {
      if (*it!=quotientSubGraph) {
	SuperGraph *tmp=(*it)->getAssociatedSuperGraph();
	if (tmp->isElement(source)) clusterSource.push_back(*it);
	if (tmp->isElement(target)) clusterTarget.push_back(*it);
      }
    }

    for (std::list<SubGraph *>::iterator it1=clusterSource.begin();it1!=clusterSource.end();++it1)
      for (std::list<SubGraph *>::iterator it2=clusterTarget.begin();it2!=clusterTarget.end();++it2) {
	//	cerr << "." ;
	edgeS tmp;
	tmp.source=mapping[*it1].id;
	tmp.target=mapping[*it2].id;
	//	pair< node , node > tmpPair(,mapping[*it2]);
	if ( ((*it1)!=(*it2)) && (myQuotientGraph.find(tmp)==myQuotientGraph.end()) ) {
	  //	  cerr<< "addedge" << endl;
	  myQuotientGraph.insert(tmp);
	  quotientGraph->addEdge(mapping[*it1],mapping[*it2]);
	}
      }
  }delete itE;

  if (dataSet!=0) {
    //    cerr << "Quotient set data set" << endl;
    dataSet->set("quotientGraph",quotientGraph);
  }
  return true;

}
//================================================================================
bool QuotientClustering::check(string &erreurMsg)
{
  erreurMsg="";
  return true;
}
//================================================================================
void QuotientClustering::reset(){}
//================================================================================