/* 
   Name:     graph_scanning.cxx
   Author:   Leo Liberti
   Purpose:  graph scanning algorithms
   Source:   C++ implementation
   History:  110123
*/

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <list>
#include <set>
#include <vector>
#include <string>
#include <fstream>
#include "graph_scanning.h"

#define BUFSIZE 1024
#define INVALID -11111111

/**
 * the default class constructor
 */
Graph::Graph() { }

Graph::Graph(std::ifstream& f) {
  fromFile(f);
}

Graph::~Graph() { }

std::set<int>& Graph::getNodeSet(void) {
  return node;
}

void Graph::addArc(int source, int dest, double cost) {
  using namespace std;
  pair<int, int> theArc(source, dest);
  arc.insert(theArc);
  arc_cost[theArc] = cost;
  adj[source].insert(dest);
  node.insert(source);
  node.insert(dest);
}

void Graph::dfs(int v, std::map<int,bool>& visited, 
		std::string& sp, int method) {
  using namespace std;
  if (method == 1) {
    cout << sp << v << endl;
  }
  set<int>::iterator sit = adj[v].begin();
  while(sit != adj[v].end()) {
    if (!visited[*sit]) {
      visited[*sit] = true;
      string spaces = sp + "  ";
      if (method == 2) {
	cout << sp << "(" << v << "," << *sit << ")" << endl;
      }
      dfs(*sit, visited, spaces, method);
      if (method == 3) {
	cout << sp << "(" << v << "," << *sit << ")" << endl;
      }
    }
    sit++;
  }
  if (method == 4) {
    cout << sp << v << endl;
  }    
}

bool Graph::fromFile(std::ifstream& inFile) {
  using namespace std;
  bool ret = true;

  // read in .gph arc list
  char buf[BUFSIZE];
  char* bufptr;
  char* saveptr;
  bool directed = false;
  while(!inFile.eof()) {
    // read line and find first non-blank
    inFile.getline(buf, BUFSIZE);
    bufptr = buf;
    while(*bufptr == ' ' || *bufptr == '\t') {
      bufptr++;
    }
    // if line is not a comment, parse
    if (*bufptr != '#') {
      if (strstr(buf, "Directed")) {
	directed = true;
      } else {
	int source = -1;
	int dest = -1;
	double cost = INVALID;
	// tokenize line and read three values
	char* token = strtok_r(bufptr, " \t", &saveptr);
	if (token) {
	  source = atoi(token);
	  token = strtok_r(NULL, " \t",  &saveptr);
	  if (token) {
	    dest = atoi(token);
	    token = strtok_r(NULL, " \t",  &saveptr);
	    if (token) {
	      cost = atof(token);
	    }
	  }
	}
	if (source != -1 && dest != -1 && cost != INVALID) {
	  // add arc
	  addArc(source, dest, cost);
	}
      }
    }
  }
  return ret;
}

void Graph::print(void) {
  using namespace std;
  pair<int,int> a;
  map<int, set<int> >::iterator mit = adj.begin();
  while(mit != adj.end()) {
    set<int>::iterator sit = mit->second.begin();
    cout << mit->first << ":";
    a.first = mit->first;
    while(sit != mit->second.end()) {
      a.second = *sit;
      cout << "[" << *sit << "," << arc_cost[a] << "]";
      sit++;
    }
    cout << endl;
    mit++;
  }
}