// 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.
 */
#include <cstdlib>
#include "graphs.h"

vector<int> GeometricBipartiteGraph::
geometricMinCostAssignment(void) {

    // default implemention is to invoke an external program
    // in working directory/path, input and output files in working dir.

    // should make a proper temp file...later, if this approach works...

    writeDIMACSassignment("shouldBeTempName.dimacs");
    system("csa_s_qm < shouldBeTempName.dimacs >/dev/null");  /* unix-ism */
    return readAssignmentFile("output.flow");
}

void GeometricBipartiteGraph::
writeDIMACSassignment(const char *fName) {
    ofstream os(fName);
    if (!os) {cerr << "cannot create output file"; exit(1);}

    assert(leftInfo.size() == rightInfo.size());  // it's an assignment

    // write the header  (assignment, n1+n2 nodes, n1*n2 arcs)
    os << "p asn " << leftInfo.size() + rightInfo.size() <<
    " " << leftInfo.size() * rightInfo.size() << endl;

    // nodes 0..n1-1  remapped for DIMACS to 1..n1
    for (uint i=0; i < leftInfo.size(); ++i)
        os << "n " << i+1 << endl;

    // arcs between all pairs  (complete bipartite graph).
    for (uint i=0; i < leftInfo.size(); ++i)
        for (uint j=0; j < rightInfo.size(); ++j) {
            double l2dist = MathUtil::L2_dist( leftInfo[i] , rightInfo[j] );
            // an instance of all 0 arc weights made the external program coredump
            // so let's make purely positive arc weights...
            os << "a " << i+1 << " " << (j+1)+leftInfo.size() << " " << l2dist+1 << endl;
        }
    // os.close();
}

vector<int> GeometricBipartiteGraph::
readAssignmentFile( const char *fileName) {

    ifstream ins(fileName);
    if (!ins) {cerr << "bad assignment input file?"; exit(1);}

    vector<int>ans( leftInfo.size(),-1 );  // -1 used as uninitialized flag
    string line;
    string junk;
    int left, right;
    uint ctr = 0;

    while ( getline(ins,line)) {
        istringstream ist(line);
        ist >> junk >> left >> right;
        --left; --right;  // we count nodes from 0, not 1
        right -= leftInfo.size();
        if (ans[left] != -1) {cerr << "this is not a valid assignment"; exit(1);}
        ans[left]=right;
        ++ctr;
    }

    assert(ctr == leftInfo.size());
    // make sure no uninitialized left
    for (uint i = 0; i < leftInfo.size(); ++i)
    if (ans[i] == -1) {cerr << "assignment appears illegal"; exit(1);};

    // ins.close();
    return ans;

}

/***************************************************************/
vector<int> GraphForMatching::implicitMaxMatching  (const EdgeWeightCalculator &ecalc) const
{
  const char *ifname = "/tmp/Rothberg.in";  // fix me later...
  const char *ofname = "/tmp/Rothberg.out";
  writeRothbergGraph(ifname, ecalc);
  system( (string("wmatch ") + string(ifname) + string(" >") + string(ofname)).c_str());  /* unix-isms */
  return readRothbergOutput(ofname);
}

void GraphForMatching::writeRothbergGraph( const char *fn, const EdgeWeightCalculator& ecalc) const
{
    ofstream os(fn);
    if (!os) {cerr << "cannot create output file"; exit(1);}

    int n = vertexInfo.size();
    // header:  nvertices nedges U   (=undirected)

    os << n << " " << int( n * (n-1) / 2) << " U" << endl;

    for (int i=0; i < n; ++i) {
      // vtx info: degree junk junk junk
      os << n-1 << " 0 0 0" << endl;
      for (int j=0; j < n; ++j) {
  if (j==i) continue;
  // edge line info: endpt, weight
  // they number vertices from 1 and don't handle weight-0 edges nicely...
  os << (j+1) << " " << int(1+ecalc.weight(*this, i, j)) << endl;   
      }
    }
}

vector<int> GraphForMatching::readRothbergOutput( const char *fn) const {
  ifstream ins(fn);
  if (!ins) {cerr << "bad/missing matching output?"; exit(1);}
 
  vector<int> answer;
  string line;
  int adam, eve;
  //  uint ctr = 0;
  
  while ( getline(ins,line)) {
    istringstream ist(line);
    ist >> adam >> eve;   // couples...
    assert(adam && eve);  // 0 is a code for "unmatched" in pgm
    adam--; eve--;        // we number from 0, they number from 1
    if (adam >= eve) continue;  // we've already processed it the other way round
    //    cout << "add pair " << adam << " " << eve << endl;
    answer.push_back(adam); answer.push_back(eve);
  }

  return answer;
}
