// Copyright (C) 1996 DIMACS Center, Rutgers, The State University of New Jersey
// Author(s): Elizabeth Johnson (Indiana University)

// This software is copyrighted by the DIMACS Center at Rutgers, The State
// University of New Jersey.  IT IS PROVIDED AS IS, AND THE AUTHORS, DIMACS, AND
// RUTGERS, THE STATE UNIVERSITY OF NEW JERSEY  DISCLAIM
// ALL LIABILITY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
// DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION, OR ANY
// DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED OF THE
// POSSIBILITY OF SUCH DAMAGE.

// THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
// INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE, AND NON-INFRINGEMENT.  THIS SOFTWARE
// IS PROVIDED ON AN "AS IS" BASIS, AND THE AUTHORS AND DISTRIBUTORS HAVE
// NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR
// MODIFICATIONS.

// The authors hereby grant permission to use, copy, modify, distribute,
// and license this software and its documentation for any purpose, provided
// that existing copyright notices are retained in all copies and that this
// notice is included verbatim in any distributions. No written agreement,
// license, or royalty fee is required for any of the authorized uses.
// Modifications to this software may be copyrighted by their authors
// and need not follow the licensing terms described here, provided that
// the new terms are clearly indicated on the first page of each file where
// they apply.

// Last File Update: 31-Jul-1996
// 


#include <fstream.h>
#include <LINK/graph/UBinGraph.h>
#include <LINK/graph/Vertex.h>
#include <LINK/graph/Edge.h>
#include <LINK/graph/Attribute.h>
#include <stdlib.h>
#include <string.h>
    
//=================================================================
// finds next word (after place) in substring where words are
// separated by spaces

int findNextWord(char* name, char* word1, int &place) {
  int foundword=0;
  int i=0;
  int len=strlen(name);
  int j;
  for(j=place; j <= len; j++) {
    if(j==len || name[j] == '\0' || name[j] == ' ' || name[j]=='\n') {
      place=j+1;
      word1[i]='\0';
      break;
    }
    else {
      foundword=1;
      word1[i]=name[j];
      i++;
    }
  }
  return foundword;
}

//=================================================================

Graph*
LoadDimacsGraph(char* filename)
{
  ifstream inFile;

  inFile.open(filename,ios::in);

  if(inFile.fail()) {
    cout << "Error: could not open file" << endl;
    return NULL;
  }

  UBinGraph* graph = new UBinGraph();

  char* inLine=new char[BUFSIZE];
  Vertex** vertices;
  
  int n=0;
  int m=0;
  char* word=new char[BUFSIZE];
  int foundword=0;
  int i1;
  int u, v;
  double metric;

  while(inFile.getline(inLine,BUFSIZE)) {
    switch (inLine[0]) {
    case 'c':
      // comment
      break;
    case 'p':
      // record with graph type, n, and m
      i1=2;
      // ignore graph type for now
      foundword=findNextWord(inLine,word,i1);
      foundword=findNextWord(inLine,word,i1);
      if(foundword==0) {
	cout << "Error: n not found" << endl;
	return NULL;
      }
      n=atoi(word);
      graph->addVertices(n);
      vertices = graph->vertexStart();
      break;
    case 'e':
      {
      // record with edge info: from to weight
      i1=2;
      foundword=findNextWord(inLine,word,i1);
      if(foundword==0) {
	cout << "Error: edge vertex not found" << endl;
	return NULL;
      }
      u=atoi(word);
      foundword=findNextWord(inLine,word,i1);
      if(foundword==0) {
	cout << "Error: edge vertex not found" << endl;
	return NULL;
      }
      v=atoi(word);
      Set<Vertex*> s;
      s.insert(vertices[u-1]);
      s.insert(vertices[v-1]);
      Edge* edge = graph->addEdge(s);
      foundword=findNextWord(inLine,word,i1);
      if(foundword!=0) {
	metric=atof(word);
	setAttribute((GraphObject*) edge,"weight",metric);
      }
      
      break;
      }
    default:
      cout << "Error: unknown record type: " << inLine[0] << endl;
    }
  }

  inFile.close();
  delete word;
  delete inLine;
  return graph;
}