reconciliation-algorithms.h

/**************************************************************************
 * Copyright (c) 2009-2012 T. M. Murali                                   *
 * Copyright (c) 2009-2012 Christopher L. Poirel                          *
 * Copyright (c) 2010 Jacqueline Addesa                                   *
 *                                                                        *
 * This file is part of Bioverse.                                         *
 *                                                                        *
 * Bioverse 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 3 of the License, or      *
 * (at your option) any later version.                                    *
 *                                                                        *
 * Bioverse is distributed in the hope that it will be useful,            *
 * but WITHOUT ANY WARRANTY; without even the implied warranty of         *
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the          *
 * GNU General Public License for more details.                           *
 *                                                                        *
 * You should have received a copy of the GNU General Public License      *
 * along with Bioverse.  If not, see <http://www.gnu.org/licenses/>.      *
 *                                                                        *
 **************************************************************************/


#include <stdio.h>
#include <stdlib.h>
#include <fstream>
#include <math.h>

#include "graph.h"   // for graphs
#include "point.h"   // for MyPointSet

#include "boost/algorithm/string.hpp" //for string split

using std::cout;
using std::endl;

void readMultipleNetworks(string file, vector< MyGraph > & graphs);


class AbstractSingleReconciliation
{
protected:
  vector< MyGraph > _graphs;

  MyGraph _currGraphA;

  MyPointSet _weights;

  // reconciliation parameters
  double _q;
  unsigned int _MAX_ITERS;
  double _EPSILON;

  unsigned int _currSampleA;

  string _outputPrefix;


  map< MyNodeId, double >  _initialNodeWeightsA;
  map< MyNodeId, double >  _currNodeWeightsA;
  map< MyNodeId, double >  _prevNodeWeightsA;


  virtual void _initialiseNodeWeights(map < MyNodeId, double > & initial,
                                      map < MyNodeId, double > & current,
                                      map < MyNodeId, double > & previous,
                                      MyGraph & graph,
                                      const MyPointSet & weights,
                                      unsigned int sample,
                                      bool normalize=true);

  virtual void _initialiseNodeWeights(map < MyNodeId, double > & initial,
                                      map < MyNodeId, double > & current,
                                      map < MyNodeId, double > & previous,
                                      MyGraph & graph);

  virtual void _initialiseNodeWeights(map < MyNodeId, double > & initial,
                                      map < MyNodeId, double > & current,
                                      map < MyNodeId, double > & previous,
                                      MyGraph & graph,
                                      double val);


  virtual void _runAlgorithmOnceA();

  virtual bool _checkFinished(unsigned int iters, double maxDiff);

  // not const MyNode& because of problems with MyNode::ConstIncidentEdgeIterator
  virtual void _updateNodeWeightA(MyNode node) = 0;

  virtual void _printNodeWeights(ofstream & ostr);

  virtual void _runForWeights();
  virtual void _runForGraphs();

  virtual pair< double, double > _computeEnergy() { pair< double, double > dummy (0,0); return dummy;  }

public:

  AbstractSingleReconciliation(MyGraph &graph, MyPointSet &weights,
      double q, double maxIters, double epsilon, string outputPrefix)
      : _graphs(), _currGraphA(graph), _weights(weights), _q(q), _MAX_ITERS(maxIters), _EPSILON(epsilon),
        _currSampleA(), _outputPrefix(outputPrefix),
        _initialNodeWeightsA(), _currNodeWeightsA(), _prevNodeWeightsA()
    {
      if (!_weights._isFlipped())
        _weights.flip();
    }

  AbstractSingleReconciliation(vector< MyGraph > & graphs,
      double q, double maxIters, double epsilon, string outputPrefix)
      : _graphs(graphs), _currGraphA(), _weights(), _q(q), _MAX_ITERS(maxIters), _EPSILON(epsilon),
        _currSampleA(), _outputPrefix(outputPrefix),
        _initialNodeWeightsA(), _currNodeWeightsA(), _prevNodeWeightsA()
    {}

  virtual ~AbstractSingleReconciliation()
    {}

  virtual string getName() { return "AbstractSingleReconciliation"; }

  virtual void run();

  void setCurrGraphA(MyGraph & g) { _currGraphA.clear(); _currGraphA = g; }

  void setCurrSampleA(unsigned int n) { _currSampleA = n; }
};


class PageRank : public AbstractSingleReconciliation
{
protected:

  virtual void _updateNodeWeightA(MyNode node);

  pair< double, double > _computeEnergy();

public:

  PageRank(MyGraph &graph, MyPointSet &weights,
      double q, double maxIters, double epsilon, string output)
      : AbstractSingleReconciliation(graph, weights, q, maxIters, epsilon, output)
    {}

  PageRank(vector< MyGraph > & graphs,
      double q, double maxIters, double epsilon, string outputPrefix)
      : AbstractSingleReconciliation(graphs, q, maxIters, epsilon, outputPrefix)
    {}

  virtual ~PageRank()
    {}

  virtual string getName() { return "PageRank"; }
};


class Vanilla : public AbstractSingleReconciliation
{
protected:

  virtual void _updateNodeWeightA(MyNode node);

  virtual pair< double, double > _computeEnergy();

public:

  Vanilla(MyGraph &graph, MyPointSet &weights,
      double q, double maxIters, double epsilon, string output)
      : AbstractSingleReconciliation(graph, weights, q, maxIters, epsilon, output)
    {}

  Vanilla(vector< MyGraph > & graphs,
      double q, double maxIters, double epsilon, string outputPrefix)
      : AbstractSingleReconciliation(graphs, q, maxIters, epsilon, outputPrefix)
    {}

  virtual ~Vanilla()
    {}

  virtual string getName() { return "Vanilla"; }
};


class GeneMANIA : public AbstractSingleReconciliation
{
protected:

  virtual void _updateNodeWeightA(MyNode node);

  virtual pair< double, double > _computeEnergy();

public:

  GeneMANIA(MyGraph &graph, MyPointSet &weights,
      double q, double maxIters, double epsilon, string output)
    : AbstractSingleReconciliation(graph, weights, q, maxIters, epsilon, output)
    {}

  GeneMANIA(vector< MyGraph > & graphs,
      double q, double maxIters, double epsilon, string outputPrefix)
      : AbstractSingleReconciliation(graphs, q, maxIters, epsilon, outputPrefix)
    {}

  virtual ~GeneMANIA()
    {}

  virtual string getName() { return "GeneMANIA"; }
};


class SinkSource : public AbstractSingleReconciliation
{
protected:

  double _LAMBDA;

  virtual void _runAlgorithmOnceA();

  virtual void _updateNodeWeightA(MyNode node);

public:

  SinkSource(MyGraph &graph, MyPointSet &weights,
      double q, double maxIters, double epsilon, double lambda, string output)
      : AbstractSingleReconciliation(graph, weights, q, maxIters, epsilon, output),
        _LAMBDA(lambda)
    {}

  SinkSource(vector< MyGraph > & graphs,
      double q, double maxIters, double epsilon, double lambda, string outputPrefix)
      : AbstractSingleReconciliation(graphs, q, maxIters, epsilon, outputPrefix),
        _LAMBDA(lambda)
    {}

  virtual ~SinkSource()
    {}

  virtual string getName() { return "SinkSource"; }

};


class HeatKernel : public AbstractSingleReconciliation
{
protected:

  double _t;

  virtual void _updateNodeWeightA(MyNode node);

  virtual bool _checkFinished(unsigned int iters, double maxDiff);

public:

  HeatKernel(MyGraph &graph, MyPointSet &weights,
      double q, double maxIters, string outputPrefix)
    : AbstractSingleReconciliation(graph, weights, q, maxIters, 1, outputPrefix)
    {
      if (_q==1)
        _t = 0;
      else
        _t = -log(q)/log(2);
    }

  HeatKernel(vector< MyGraph > & graphs,
      double q, double maxIters, string outputPrefix)
      : AbstractSingleReconciliation(graphs, q, maxIters, 1, outputPrefix),
        _t(-log(q)/log(2))
    {}

  virtual ~HeatKernel()
    {}

  virtual string getName() { return "HeatKernel"; }
};




#if 0 // use preprocessor to ignore unfinished multi-walk work.

class AbstractDoubleReconciliation : public AbstractSingleReconciliation
{
protected:

  MyGraph _currGraphB;

  unsigned int _currSampleB;

  map< MyNodeId, double > _initialNodeWeightsB, _currNodeWeightsB, _prevNodeWeightsB;

  virtual void _runAlgorithmOnceB();

  virtual void _updateNodeWeightB(MyNode node) = 0;

  virtual void _runForWeights();
  virtual void _runForGraphs();

  virtual void _printNodeWeights(ofstream & ostr);

  void _initialiseNodeWeightsAW(map < MyNodeId, double > & initial,
                                map < MyNodeId, double > & current,
                                map < MyNodeId, double > & previous,
                                MyGraph & graph,
                                const MyPointSet & weights,
                                unsigned int sample);

public:

  AbstractDoubleReconciliation(MyGraph &graph, MyPointSet &weights,
      double q, double maxIters, double epsilon, string outputPrefix)
      : AbstractSingleReconciliation(graph, weights, q, maxIters, epsilon, outputPrefix),
        _currGraphB(), _currSampleB(),
        _initialNodeWeightsB(), _currNodeWeightsB(), _prevNodeWeightsB()
    {}

  AbstractDoubleReconciliation(vector< MyGraph > & graphs,
      double q, double maxIters, double epsilon, string outputPrefix)
      : AbstractSingleReconciliation(graphs, q, maxIters, epsilon, outputPrefix),
        _currGraphB(), _currSampleB(),
        _initialNodeWeightsB(), _currNodeWeightsB(), _prevNodeWeightsB()
    {}

  virtual ~AbstractDoubleReconciliation()
    {}

  virtual string getName() { return "AbstractDoubleReconciliation"; }

};


class AbsorbWalkVisit : public AbstractDoubleReconciliation
{
protected:

  double _r;

  double _nodeSum;

  virtual void _runAlgorithmOnceB();

  virtual void _updateNodeSum();

  virtual void _updateNodeWeightA(MyNode node);

  virtual void _updateNodeWeightB(MyNode node);

  virtual void _printNodeWeights(ofstream & ostr);


public:

  AbsorbWalkVisit(MyGraph &graph, MyPointSet &weights,
      double q, double r, double maxIters, double epsilon, string outputPrefix)
      : AbstractDoubleReconciliation(graph, weights, q, maxIters, epsilon, outputPrefix),
        _r(r), _nodeSum(0)
    {}

  AbsorbWalkVisit(vector< MyGraph > &graphs, double q, double r, double maxIters, double epsilon, string outputPrefix)
      : AbstractDoubleReconciliation(graphs, q, maxIters, epsilon, outputPrefix),
        _r(r), _nodeSum(0)
    {}

  virtual ~AbsorbWalkVisit()
    {}

  virtual string getName() { return "AbsorbWalkVisit"; }

  virtual void run();

  virtual void printTransitionMatrix();

};



class AbsorbWalkLife : public AbsorbWalkVisit
{
protected:

  virtual void _updateNodeSum();

  virtual void _updateNodeWeightB(MyNode node);

public:

  AbsorbWalkLife(MyGraph &graph, MyPointSet &weights,
      double q, double r, double maxIters, double epsilon, string outputPrefix)
      : AbsorbWalkVisit(graph, weights, q, r, maxIters, epsilon, outputPrefix)
    {}

  virtual ~AbsorbWalkLife()
    {}

  virtual string getName() { return "AbsorbWalkLife"; }
};



class MultiAbsorbWalkVisit : public AbstractDoubleReconciliation
{
protected:

  double _nodeSum;

  set< MyNodeId > _absorbers;

  map< MyNodeId, double > _nwPrevNodeWeightsA, _nwCurrNodeWeightsA;

  void _runNWOnceA();

  virtual void _runForWeights();

  virtual void _runAlgorithmOnceA();

  virtual void _updateNodeSum();

  virtual void _updateNodeWeightA(MyNode v);

  virtual void _updateNodeWeightB(MyNode v){}

  void _initialiseNodeWeights(map < MyNodeId, double > & initialA,
                              map < MyNodeId, double > & currentA,
                              map < MyNodeId, double > & previousA,
                              map < MyNodeId, double > & initialB,
                              MyGraph & graph, const MyPointSet & weights,
                              unsigned int sampleA, unsigned int sampleB);

  virtual void _printNodeWeights(ofstream & ostr);

//  void _modifyAbsorbingEdges();
//  void _unmodifyAbsorbingEdges();

public:

  MultiAbsorbWalkVisit(MyGraph &graph, MyPointSet &weights,
      double q, double r, double maxIters, double epsilon, string outputPrefix)
      : AbstractDoubleReconciliation(graph, weights, q, maxIters, epsilon, outputPrefix),
        _nodeSum(0)
    {}

  virtual ~MultiAbsorbWalkVisit()
    {}

  virtual void run();

  virtual string getName() { return "MultiAbsorbWalkVisit"; }
};

#endif // end of preprocessor if statement to ignore multi-walks