#include <math.h>
#include <stdio.h>
#include <sstream>
#include <string>
#include <list>
#include <map>
#include <iostream>
#include <tulip/SuperGraph.h>
#include <tulip/SelectionProxy.h>
#include <tulip/MetaGraphProxy.h>
#include <tulip/SubGraph.h>
#include <tulip/TlpTools.h>
#include <tulip/GraphMeasure.h>
#include <tulip/Cluster.h>

#include "StrengthClustering.h"

CLUSTERINGPLUGIN(StrengthClustering,"Strength","David Auber","27/01/2003","Alpha","0","1");

using namespace std;

//================================================================================
StrengthClustering::StrengthClustering(ClusterContext context):Clustering(context) {}
//================================================================================
StrengthClustering::~StrengthClustering() {}
//================================================================================
double StrengthClustering::e(set<node> &U,set<node> &V) {
  set<node>::const_iterator itU;
  double result=0;
  for (itU=U.begin();itU!=U.end();++itU) {
    Iterator<node> *itN=superGraph->getInOutNodes(*itU);
    for (;itN->hasNext();) {
      node itn=itN->next();
      if (V.find(itn)!=V.end()) result+=1;
    }delete itN;
  }
  return result;
}
//==============================================================================
double StrengthClustering::e(set<node> &U) {
  set<node>::const_iterator itU;
  double result=0;
  for (itU=U.begin();itU!=U.end();++itU) {
    Iterator<node> *itN=superGraph->getInOutNodes(*itU);
    for (;itN->hasNext();) {
      node itn=itN->next();
      if (U.find(itn)!=U.end()) result+=1;
    }delete itN;
  }
  return result/2;
}
//==============================================================================
double StrengthClustering::s(set<node> &U,set<node> &V) {
  if ((U.size()==0) || (V.size()==0)) return 0;
  return (e(U,V) / (U.size()*V.size()));
}
//==============================================================================
double StrengthClustering::s(set<node> &U) {
  if (U.size()<2) return 0;
  return  (e(U)) * 2 / (U.size()*(U.size()-1));
}
//==============================================================================
double StrengthClustering::computeMQValue(vector<set<node> > partition) {
  double positive=0;
  for (int i=0;i<partition.size();++i) {
    positive+=s(partition[i]);
  }
  positive/=partition.size();
  double negative=0;
  for (int i=0;i<partition.size()-1;++i)
    for (int j=i+1;j<partition.size();++j) {
      negative+=s(partition[i],partition[j]);
    }
  if (partition.size()>1)
    negative/=partition.size()*(partition.size()-1)/2;
  //  cout << "positive :"<< positive << " , negative :" << negative << endl;
  return positive-negative;
}
//==============================================================================
vector< set<node> > StrengthClustering::computeNodePartition(double threshold) {
  bool cached,results;
  string errMsg;
  MetricProxy *values=getLocalProxy<MetricProxy>(superGraph,"Strength",cached,results,errMsg);  
  // double threshold=2;
  // step One build a filtered subgraph
  // All edges with a values less than the threshold are removed
  // cerr << "1" << endl << flush;
  SuperGraph *tmpGraph=TlpTools::newCloneSubGraph(superGraph);
  Iterator<edge> *itE=superGraph->getEdges();
  for (;itE->hasNext();) {
    edge ite=itE->next();
    if (values->getEdgeValue(ite)<threshold) {
      if (superGraph->deg(superGraph->source(ite))>1 && superGraph->deg(superGraph->target(ite))>1)
	tmpGraph->delEdge(ite);
    }
  } delete itE;
  

  set<node> singleton;
  // Select SubGraph singleton in superGraph
  // cerr << "2" << endl << flush;
  Iterator<node> *itN=tmpGraph->getNodes();
  for (;itN->hasNext();) {
    node itn=itN->next();
    if (tmpGraph->deg(itn)==0) singleton.insert(itn);
  }delete itN;
  
  // restore edges to reconnect singleton by computing induced subgraph 
  itE=superGraph->getEdges();
  for (;itE->hasNext();) {
    edge ite=itE->next();
    if (singleton.find(superGraph->source(ite))!=singleton.end() && singleton.find(superGraph->target(ite))!=singleton.end()) {
      tmpGraph->addEdge(ite);
    }
  }delete itE;

  //Extract connected componnent
  //cerr << "5" << endl << flush;
  MetricProxy *connected=getLocalProxy<MetricProxy>(tmpGraph,"Connected Component",cached,results,errMsg);
  if (cached) connected->recompute(errMsg);
  //Put individual nodes in the same cluster
  double val=-1;
  itN=tmpGraph->getNodes();
  for (;itN->hasNext();) {
    node itn=itN->next();
    if (tmpGraph->deg(itn)==0) {
      if (val==-1) val=connected->getNodeValue(itn);
      else
	connected->setNodeValue(itn,val);
    }
  } delete itN;

  //Compute the node partition
  vector< set<node > > result;
  int index=0;
  map<double,int> resultIndex;
  itN=tmpGraph->getNodes();
  for (;itN->hasNext();) {
    node itn=itN->next();
    double val=connected->getNodeValue(itn);
    if (resultIndex.find(val)!=resultIndex.end())
      result[resultIndex[val]].insert(itn);
    else {
      set<node> tmp;
      result.push_back(tmp);
      resultIndex[val]=index;
      result[index].insert(itn);
      ++index;
    }
  }delete itN;

  tmpGraph->getPropertyProxyContainer()->delLocalProxy("Connected Component");
  superGraph->delAllView(tmpGraph->getSubGraph());
  return result;
}

void drawGraph(SuperGraph *tmpg) {
  bool cached,result;
  string errMsg;
  string layoutName="GEM (Frick)";
  string sizesName="Auto_sizing";
  *getLocalProxy<LayoutProxy>(tmpg, "viewLayout") = *getLocalProxy<LayoutProxy>(tmpg, layoutName,
										result, cached,
										errMsg);
  *getLocalProxy<SizesProxy>(tmpg, "viewSize") = *getLocalProxy<SizesProxy>(tmpg, sizesName,
									    result, cached,
									    errMsg);
  tmpg->getPropertyProxyContainer()->delLocalProxy(layoutName);
  tmpg->getPropertyProxyContainer()->delLocalProxy(sizesName);
}

//==============================================================================
bool StrengthClustering::run() {
  //  cerr << __PRETTY_FUNCTION__ << " Start" << endl;
  //  cout << "Average Path Length :" << TlpTools::averagePathLength(superGraph) << endl;
  //  cout << "Average clustering :" <<  TlpTools::averageCluster(superGraph) << endl; 
  bool cached,result;
  string errMsg;
  MetricProxy *values=getLocalProxy<MetricProxy>(superGraph,"Strength",cached,result,errMsg);
  double maxMQ=0;
  int numberOfStep=100;
  double threshold=0;
  double deltaThreshold=(values->getEdgeMax(superGraph)-values->getEdgeMin(superGraph))/numberOfStep;
  int debugI=1;
  //  cerr << debugI++ << " ....." << endl;
  for (double i=values->getEdgeMin(superGraph);i<values->getEdgeMax(superGraph);i+=deltaThreshold) {
    vector< set<node > > tmp;
    tmp=computeNodePartition(i);
    double mq=computeMQValue(tmp);

    if (mq>maxMQ) {
      threshold=i;
      maxMQ=mq;
    }
  }
  cout << " MQ value for clustering : " << maxMQ << endl << flush;
  //  cerr << debugI++ << " ....." << endl;
  vector< set<node > > tmp;
  tmp.clear();
  //  threshold=(values->getEdgeMax())*80/step;
  tmp=computeNodePartition(threshold);

  if (tmp.size()==1) {
    drawGraph(superGraph);
    if (dataSet!=0) {
      dataSet->set("strengthGraph",superGraph);
    }
    return true;
  }

  SuperGraph *tmpGraph=TlpTools::newCloneSubGraph(superGraph); 

  //  cerr << debugI++ << " ....." << endl;
  map<SuperGraph *,SuperGraph *> mapGraph;
  for (int i=0;i<tmp.size();++i) {
    SuperGraph *tmpg=TlpTools::inducedSubGraph(tmpGraph,tmp[i]);
    double avPath=TlpTools::averagePathLength(tmpg);
    double avCluster=TlpTools::averageCluster(tmpg);
    /*    cout << "Average Path Length :" << avPath << endl;
    cout << "Average clustering  :" <<  avCluster << endl; 
    cout << "Number of nodes     :" <<  tmpg->numberOfNodes() << endl; 
    cout << "Number of edges     :" <<  tmpg->numberOfEdges() << endl; 
    */
    SuperGraph *tmpGr=tmpg;
    if ( tmp.size()>1 && avPath>1 && avPath<4 && avCluster>0.25 && tmpg->numberOfNodes()>10) {
      DataSet tmpData;
      TlpTools::clusterizeGraph(tmpg,errMsg,&tmpData,"Strength");
      tmpData.get("strengthGraph",tmpGr);
    }
    mapGraph[tmpg]=tmpGr;
    if (tmpg==tmpGr) {
      drawGraph(tmpg);
    }
    tmpg=tmpGr;
  }
  //  cerr << debugI++ << " ....." << endl;
  DataSet tmpData;
  TlpTools::clusterizeGraph(tmpGraph,errMsg,&tmpData,"QuotientClustering");
  superGraph->getPropertyProxyContainer()->delLocalProxy("Strength");
  SuperGraph *quotientGraph;
  tmpData.get<SuperGraph *>("quotientGraph",quotientGraph);
  drawGraph(quotientGraph);
  if (dataSet!=0) {
    dataSet->set("strengthGraph",quotientGraph);
  }
  if (quotientGraph!=superGraph) {
    //  cerr << debugI++ << " .....A" << endl;
    SuperGraph *rootGraph=superGraph->getClusterTree()->getRootSubGraph()->getAssociatedSuperGraph();
    MetaGraphProxy *meta=getProxy<MetaGraphProxy>(rootGraph,"viewMetaGraph");
    MetaGraphProxy *meta2=getProxy<MetaGraphProxy>(rootGraph,"strengthMetaGraph");
    //  cerr << debugI++ << " .....B" << endl;
    
    Iterator<node> *itN=quotientGraph->getNodes();
    for (;itN->hasNext();) {
      node itn=itN->next();
      meta2->setNodeValue(itn,meta->getNodeValue(itn));
      meta->setNodeValue(itn,mapGraph[meta->getNodeValue(itn)]);
    } delete itN;
    //  cerr << __PRETTY_FUNCTION__ << " End" << endl;
  }


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