compare.h

#ifndef COMP_H
#define COMP_H

#include "MySets.h"
#include "MyTools.h"

#include "distance.h"

class Compare{
public:
  virtual double operator () (vector <set <string> >* Cl1, vector < set <string> >* Cl2){return 0;};
  
  Compare* Produce(string s);
  
  void setDist(string s){
    dist* creator = new dist();
    d = creator->Produce(s);
    delete creator;
  };
  
  Compare(){};
  Compare(int size){graphSize = size;};
  
  int getNodes(vector <set <string> >* Cl1, vector < set <string> >* Cl2){
    set<string> S1;
    set<string>::iterator it_ss;
    
    for (sui t = 0; t < Cl1->size(); t++){
      for (it_ss = (*Cl1)[t].begin(); it_ss != (*Cl1)[t].end(); it_ss++){
        S1.insert(*it_ss);
      }
    }
    
    for (sui t = 0; t < Cl2->size(); t++){
      for (it_ss = (*Cl2)[t].begin(); it_ss != (*Cl2)[t].end(); it_ss++){
        S1.insert(*it_ss);
      }
    }
    
    return S1.size();
  };
  
  double graphSize; 
  dist* d;  
};

class BestMatch:public Compare{
public:
  double operator () (vector <set < string > >* Cl1, vector<set <string> >* Cl2){ 
    pair <map <int, set <int> >, map <int, set < int > > > Reduced = getSim(Cl1, Cl2);
    
    if (d->type > 3){
      cerr << "Invalid Similarity type for BestMatch measure" << endl;
      exit(3);
    }
    double total = 0, current = 0, min;
    
    map <int, set <int> >::iterator it_m;
    set <int>::iterator it_si;
    int nodeCount = getNodes(Cl1, Cl2);
    
    for (sui t = 0; t < Cl1->size(); t++){
      if ((it_m = Reduced.first.find(t)) != Reduced.first.end()){
        min = 10000000;
        for (it_si = it_m->second.begin(); it_si != it_m->second.end(); it_si++){
          if ((current = (*d)((*Cl1)[it_m->first], (*Cl2)[*it_si], graphSize)) < min)
            min = current;
        }
        total += min;
      }else{
        total += Cl1->at(t).size();
      }
    }
    
    for (sui t = 0; t < Cl2->size(); t++){
      if ((it_m = Reduced.second.find(t)) != Reduced.second.end()){
        min = 10000000;
        for (it_si = it_m->second.begin(); it_si != it_m->second.end(); it_si++){
          if ((current = (*d)((*Cl1)[*it_si], (*Cl2)[it_m->first], nodeCount)) < min)
            min = current;
        }
        total += min;
      }else{
        total += Cl2->at(t).size();
      }
    }
    
    return (double)(total) / (double)(Cl1->size() + Cl2->size());
  };
  
private:
  pair <map <int, set <int> >, map <int, set < int > > > getSim (vector <set < string > >* Cl1, vector<set <string> >* Cl2){
  set<string>::iterator it_sl;
   set<int>::iterator it_si, it_si2;
   
   map <string, set <int> > first, second;
   map <string, set <int> >::iterator it_f, it_s;
   
    for (sui t = 0; t < Cl1->size(); t++){
      for (it_sl = Cl1->at(t).begin(); it_sl != Cl1->at(t).end(); it_sl++){
        if ((it_f = first.find(*it_sl)) != first.end()){
          it_f->second.insert(t);
        } else {
          set <int> tmp;
          tmp.insert(t);
          first.insert(make_pair<string, set<int> >(*it_sl, tmp));
        }
      }
    }
    
    for (sui t = 0; t < Cl2->size(); t++){
      for (it_sl = Cl2->at(t).begin(); it_sl != Cl2->at(t).end(); it_sl++){
        if ((it_f = second.find(*it_sl)) != second.end()){
          it_f->second.insert(t);
        } else {
          set <int> tmp;
          tmp.insert(t);
          second.insert(make_pair<string, set<int> >(*it_sl, tmp));
        }
      }
    }
    
    map <int, set <int> > A, B;
    map <int, set <int> >::iterator it_a;
    
    for (it_f = first.begin(); it_f != first.end(); it_f++){
      if ((it_s = second.find(it_f->first)) == second.end()) continue;
      
      for (it_si = it_f->second.begin(); it_si != it_f->second.end(); it_si++){
        if ((it_a = A.find(*it_si)) == A.end()){
          set <int> tmp;
          A.insert(make_pair<int, set<int> > (*it_si, tmp));
          it_a = A.find(*it_si);
        }
        for (it_si2 = it_s->second.begin(); it_si2 != it_s->second.end(); it_si2++){
          it_a->second.insert(*it_si2);
        }
      }
    }
    
    for (it_f = second.begin(); it_f != second.end(); it_f++){
      if ((it_s = first.find(it_f->first)) == first.end()) continue;
      
      for (it_si = it_f->second.begin(); it_si != it_f->second.end(); it_si++){
        if ((it_a = B.find(*it_si)) == B.end()){
          set <int> tmp;
          B.insert(make_pair<int, set<int> > (*it_si, tmp));
          it_a = B.find(*it_si);
        }
        for (it_si2 = it_s->second.begin(); it_si2 != it_s->second.end(); it_si2++){
          it_a->second.insert(*it_si2);
        }
      }
    }
  
  return make_pair< map <int, set <int> >, map <int, set < int > > >(A, B);
  }
};

class KCenter:public Compare{
public:
  
  void setDist(string s){
    dist* creator = new dist();
    d = creator->Produce(s);
    distType = s;
    delete creator;
  };
  
  double operator() (vector<set<string> >* Cl1, vector<set<string> >* Cl2){
    if (d->type > 3){
      cerr << "Invalid Similarity type for KCenter measure" << endl;
      exit(3);
    }
    
    BestMatch* BM = new BestMatch();
    BM->setDist(distType);
    
    int K = 0.75 * (Cl1->size() + Cl2->size()) / 2;
    int N = getNodes(Cl1, Cl2);
    vector <set <string> > KC1 = getCenter(Cl1, K, N), KC2 = getCenter(Cl2, K, N);
    
    cerr << "Retreived Centers" << endl;
    
    return (*BM)(&KC1, &KC2);
  };
  
private:
  
  string distType; 
  vector<set<string> > getCenter(vector<set<string> >* Cl, sui K, int N){
    if (K < 1 || K > Cl->size()){
      cerr << "Invalid K for centers" << endl;
      exit(3);
    }
    
    vector< set <string> > ret;
    vector < double > dsts;
    dsts.resize(Cl->size(), 9999999);
    set <string> empty;
    
     /*
     * Add First Cluster
     */
     
    double max = 0, index = 0, weight = 0;
    
    for (sui t = 0; t < Cl->size(); t++){
        if ((weight = (*d)(empty, (*Cl)[t], N)) > max){
          max = weight;
          index = t;
        }
    }
    
    ret.push_back((*Cl)[index]);
    empty = (*Cl)[index];
    
    /*
     * Greedily increase the center
     */
    while (ret.size() != K){
      /*
       * Recalculate Distances
       */
      for (sui t = 0; t < Cl->size(); t++){
        if ((weight = (*d)(empty, (*Cl)[t], N)) < dsts[t])
          dsts[t] = weight;
      }
      /*
       * Add cluster furthest away
       */
      max = dsts[0];
      for (sui t = 0; t < dsts.size(); t++){
        if (dsts[t] > max){
          max = dsts[t];
          index = t;
        }
      }
      
      empty = (*Cl)[index];
      ret.push_back(empty);
    }
    
    return ret;
  };
};

class Interaction:public Compare{
public:
  double operator() (vector<set<string> >* Cl1, vector<set<string> >* Cl2){
    if (d->type < 4){
      cerr << "Invalid Similarity type for Interaction measure" << endl;
      exit(3);
    }
    map < string, set <int> > S1, S2;
    map < string, set <int> >::iterator it_m, it_m2;
    set <int>::iterator it_si;
    set<string>::iterator it_ss, it_ss2;
    
    for (sui t = 0; t < Cl1->size(); t++){
      for (it_ss = (*Cl1)[t].begin(); it_ss != (*Cl1)[t].end(); it_ss++){
        if ((it_m = S1.find(*it_ss)) != S1.end()){
          it_m->second.insert(t);
        } else {
          set <int> tmp;
          tmp.insert(t);
          S1.insert(make_pair<string, set <int> >(*it_ss, tmp));
        }
      }
    }
    
    for (sui t = 0; t < Cl2->size(); t++){
      for (it_ss = (*Cl2)[t].begin(); it_ss != (*Cl2)[t].end(); it_ss++){
        if ((it_m = S2.find(*it_ss)) != S2.end()){
          it_m->second.insert(t);
        } else {
          set <int> tmp;
          tmp.insert(t);
          S2.insert(make_pair<string, set <int> >(*it_ss, tmp));
        }
      }
    }
    
    int SC1 = S1.size(), SC2 = S2.size();
    double cP = 0, prod = 0;
    
    for (it_m = S1.begin(); it_m != S1.end(); it_m++){
      it_m2 = it_m;
      for (++it_m2; it_m2 != S1.end(); it_m2++){
        set <int> Int = Intersection< set<int> >(it_m->second, it_m2->second);
        prod = 1;
        for (it_si = Int.begin(); it_si != Int.end(); it_si++){
          prod *= (1.0/double((*Cl1)[*it_si].size()));
        }
        cP = 1 - (1 - (1.0 / (double)SC1)) * prod;
        
        pair <string, string> curr = make_pair<string, string> (it_m->first, it_m2->first);
        if ((it_p = P.find(curr)) != P.end()){
          it_p->second.first = cP;
        } else {
          P.insert(make_pair<pair <string, string>, pair <double, double> >(curr, make_pair<double, double>(cP, 0.0)));
        }
      }
    }
    
    for (it_m = S2.begin(); it_m != S2.end(); it_m++){
      it_m2 = it_m;
      for (++it_m2; it_m2 != S2.end(); it_m2++){
        set <int> Int = Intersection< set<int> >(it_m->second, it_m2->second);
        prod = 1;
        for (it_si = Int.begin(); it_si != Int.end(); it_si++){
          prod *= (1.0/double((*Cl2)[*it_si].size()));
        }
        cP = 1 - (1 - (1.0 / (double)SC2)) * prod;
        
        pair <string, string> curr = make_pair<string, string> (it_m->first, it_m2->first);
        if ((it_p = P.find(curr)) != P.end()){
          it_p->second.second = cP;
        } else {
          P.insert(make_pair<pair <string, string>, pair <double, double> >(curr, make_pair<double, double>(0.0, cP)));
        }
      }
    }
    
    /*
     * Put in a nice form
     */
    vector <double> A, B;
    for (it_p = P.begin(); it_p != P.end(); it_p++){
      A.push_back(it_p->second.first);
      B.push_back(it_p->second.second);
    }
    
    P.clear();
    /*
     * Calculate
     */
    return (*d)(A, B, getNodes(Cl1, Cl2));
 }
  
private:
  map <pair <string, string>, pair <double, double> > P; 
  map <pair <string, string>, pair <double, double> >::iterator it_p; 
};

class FScore:public Compare{
public:
  double operator () (vector <set <string> >* Cl1, vector < set <string> >* Cl2){
    int tp = 0;
    set <int> ttp;
    for (sui i = 0; i < Cl2->size(); i++){
      for (sui j = 0; j < Cl1->size(); j++){
        if (getScore(Cl2->at(i), Cl1->at(j)) > 0.9){
          tp++;
          ttp.insert(j);
        }
      }
    }
    
    int fn = Cl1->size() - ttp.size();
    int fp = Cl2->size() - tp;
    
    double p = (double)tp / (double)(tp + fp);
    double r = (double)tp / (double)(tp + fn);
    
    return (2 * p * r)/(p + r);
  }
  
private:
  double getScore (set <string> c1, set <string> c2){    
    set <string> inter = Intersection<set <string> >(c1, c2);
    
    int tp = inter.size();
    int fp = c2.size() - tp;
    int fn = c1.size() - tp;
    
    double p = (double)tp / (double)(tp + fp);
    double r = (double)tp / (double)(tp + fn);
    
    return (2 * p * r)/(p + r);
  }
};

class NMI:public Compare{
public:
  double operator () (vector <set <string> >* Cl1, vector < set <string> >* Cl2){
    if (d->type != 3)
    {
      cerr << "Entropy Required as comparison" << endl;
      exit(22);
    }
    
    double Hy = 0, Hx = 0;
    for (sui i = 0; i < Cl2->size(); i++){
      Hy += (((*(entropy*)d)).h((*Cl2)[i].size(), graphSize) + ((*(entropy*)d)).h(graphSize - (*Cl2)[i].size(), graphSize));
    }
    
    for (sui i = 0; i < Cl1->size(); i++){
      Hx += (((*(entropy*)d)).h((*Cl1)[i].size(), graphSize) + ((*(entropy*)d)).h(graphSize - (*Cl1)[i].size(), graphSize));
    }
    
    set <string>::iterator it_s;
    map <string, set <int> > m1, m2;
    map <string, set <int> >::iterator it_mm;
    sui minC1 = 0, minC2 = 0;
    sui minC1Size = numeric_limits<unsigned short int>::max();
    sui minC2Size = minC1Size;
    /*Membership maps*/
    for (sui i = 0; i < Cl1->size(); i++){
      if ((*Cl1)[i].size() < minC1Size){
        minC1 = i;
        minC1Size = (*Cl1)[i].size();
      }
      
      for (it_s = (*Cl1)[i].begin(); it_s != (*Cl1)[i].end(); it_s++){
        if ((it_mm = m1.find(*it_s)) != m1.end()){
          it_mm->second.insert(i);
        } else {
          set <int> temp;
          temp.insert(i);
          m1.insert(make_pair<string, set <int> > (*it_s, temp));
        }
      }
    }
    
    for (sui i = 0; i < Cl2->size(); i++){
      if ((*Cl2)[i].size() < minC2Size){
        minC2 = i;
        minC2Size = (*Cl2)[i].size();
      }
      
      for (it_s = (*Cl2)[i].begin(); it_s != (*Cl2)[i].end(); it_s++){
        if ((it_mm = m2.find(*it_s)) != m2.end()){
          it_mm->second.insert(i);
        } else {
          set <int> temp;
          temp.insert(i);
          m2.insert(make_pair<string, set <int> > (*it_s, temp));
        }
      }
    }
    
    double Hxy = 0;
    for (sui i = 0; i < Cl1->size(); i++){
      set <int> potents;
      for (it_s = (*Cl1)[i].begin(); it_s != (*Cl1)[i].end(); it_s++){
        if ((it_mm = m2.find(*it_s)) != m2.end()){
          potents.insert(it_mm->second.begin(), it_mm->second.end());
        }
      }
      
      if (potents.size() == 0){
        Hxy += (*d)((*Cl1)[i], (*Cl2)[minC2], graphSize);
        continue;
      }
      
      double minimum = numeric_limits<double>::max();
      for (set <int>::iterator j = potents.begin(); j != potents.end(); j++)
        //for (sui j = 0; j < Cl2->size(); j++)
      {
        double current = (*d)((*Cl1)[i], (*Cl2)[*j], graphSize);
        if (current < minimum)
          minimum = current;
      }
      
      Hxy += minimum;
    }
    
    double Hyx = 0;
    for (sui i = 0; i < Cl2->size(); i++){
      set <int> potents;
      for (it_s = (*Cl2)[i].begin(); it_s != (*Cl2)[i].end(); it_s++){
        if ((it_mm = m1.find(*it_s)) != m1.end()){
          potents.insert(it_mm->second.begin(), it_mm->second.end());
        }
      }
      
      if (potents.size() == 0){
        Hxy += (*d)((*Cl2)[i], (*Cl1)[minC1], graphSize);
        continue;
      }
      
      double minimum = numeric_limits<double>::max();
      for (set <int>::iterator j = potents.begin(); j != potents.end(); j++){
      //for (sui j = 0; j < Cl1->size(); j++)
      
        double current = (*d)((*Cl2)[i], (*Cl1)[*j], graphSize);
        if (current < minimum)
          minimum = current;
      }
      Hyx += minimum;
    }
    
   double Ixy = (Hx - Hxy + Hy - Hyx) / 2;
    
    return (Ixy / max(Hx, Hy));
  };
  
private:
  
};

Compare* Compare::Produce(string s){
  if ((strcmp(s.c_str(), "best")) == 0){
    return new BestMatch();
  } else if ((strcmp(s.c_str(), "kcent")) == 0){
    return new KCenter();
  } else if ((strcmp(s.c_str(), "inter")) == 0){
    return new Interaction();
  } else if ((strcmp(s.c_str(), "fscore")) == 0){
    return new FScore();
  } else if ((strcmp(s.c_str(), "nmi")) == 0){
    return new NMI();
  } else {
    cerr << "Invalid comparison method chosen" << endl;
    exit(4);
  }
};

#endif