// Lemur OLAP library (c) 2003 National Research Council of Canada by Daniel Lemire, and Owen Kaser
 /**
 *  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 (version 2). This
 *  program 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 this program; if not, write to the Free Software Foundation,
 *  Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 */
#ifndef GRAPHS_H
#define GRAPHS_H

#include "lemurcore/common.h"

/*  To solve the assignment problem, you need a package that
 *  accepts DIMACS-format input (on standard input) and 
 *  produces an output file  "output.flow".  One suitable program
 *  is "csa_s_qm" from the CSA-1.2 package by Goldberg and Kennedy,
 *  which is gotten by adding -DMIN_COST and -DSAVE_RESULT to the
 *  appropriate Makefile.  This package could be replaced by any
 *  other fast solver for assignment problems.  Most of the instance
 *  are not very large, so an efficient solver is not so important.
 *
 *  This program will assume that csa_s_qm executable is in the
 *    current working directory (I used a symlink).
 *
 */


class GeometricBipartiteGraph {
public:
    enum {LEFT=0, RIGHT=1};
    virtual ~GeometricBipartiteGraph() {};
GeometricBipartiteGraph( int numOnLeft, int numOnRight) :
    leftInfo(numOnLeft), rightInfo(numOnRight) {}
    void setCoordinates( int where, int which, vector<double> & coord) {
        assert(where == LEFT || where == RIGHT);
        if (where == LEFT) leftInfo.at(which) = coord;  // copy
        else                rightInfo.at(which) = coord;
    }

    virtual vector<int> geometricMinCostAssignment(void);

private:
    void writeDIMACSassignment(const char * fileName);
    vector<int> readAssignmentFile(const char * fileName);
    vector< vector<double> > leftInfo, rightInfo;
};


/***********************************************************
 *  We need to solve weighted matching problems too.
 *  The implemention by Rothberg of Edmonds' algorithm
 *  can be obtained from dimacs.rutgers.edu
 *
 *
 * These classes is not general purpose...  should be templated by kind of info
 * that vtx vectors carry. Initially Boolean but I may want to generalize.  For now, I will
 * use doubles....
 *
 */

class EdgeWeightCalculator;
class GraphForMatching {
public:
    virtual ~GraphForMatching() {};
    // GraphForMatching() : vertexIinfo() {};    default constructor should be okay

    // adds vertices in order
    virtual void addVtx( const vector<double> &info) { vertexInfo.push_back( info);}

    // retrieve info
    virtual const vector<double> getVtxInfo( int v) const { return vertexInfo[v];}

    // output is a linearized sequence of pairs.  Vertices named in order addVtx'ed
    virtual vector<int> implicitMaxMatching (const EdgeWeightCalculator &ecalc) const;

private:
    void writeRothbergGraph(const char * fileName, const EdgeWeightCalculator& ecalc) const;
    vector<int> readRothbergOutput(const char * fileName) const;
    vector< vector<double> > vertexInfo;
};



class EdgeWeightCalculator{
public:
  virtual double weight( const GraphForMatching &g, int v1, int v2)  const = 0;
};

class BitOrWeight : public EdgeWeightCalculator {
  public :
    virtual double weight( const GraphForMatching &g, int v1, int v2) const {
    const vector<double> &d1 = g.getVtxInfo(v1);
    const vector<double> &d2 = g.getVtxInfo(v2);
    // any zeros should be ASSIGNED zeros, not CALCULATED zeros, because I don't epsilon-check
    int zeroCtr = 0;
    for (uint i=0; i < d1.size(); ++i)
      if (d1[i] == 0.0  && d2[i] == 0.0) zeroCtr++;

    return double(zeroCtr);
  }
};

class ChunkingWeight : public EdgeWeightCalculator {
  public :
    ChunkingWeight( uint dim = 0, int scost = 2 ) : dimension(dim), sparseCost(scost) {};
    virtual double weight( const GraphForMatching &g, int v1, int v2) const {
    const vector<double> &d1 = g.getVtxInfo(v1);
    const vector<double> &d2 = g.getVtxInfo(v2);
    double score = 0.0;
    for (uint i=0; i < d1.size(); ++i) {
      double numAlloc = (d1[i]+d2[i]);
      assert(0 <= numAlloc && numAlloc <= (0x1<< (dimension+1)));
      double blockCost = min( double(0x1 << (dimension+1)), sparseCost*numAlloc);
      score += ( double(0x1 << (dimension+1)) - blockCost);
    }
    return score;
  }
 private:
    int dimension;
    int sparseCost;
};
  

#endif
