/* 
   Name:     graph_scanning.h
   Author:   Leo Liberti
   Purpose:  graph scanning algorithms
   Source:   C++ header file
   History:  110123
*/

#include <iostream>
#include <string>
#include <fstream>
#include <set>
#include <map>

/**
 * The Graph class stores node IDs in a set (normally consecutive
 * ints numbered from 0), a list of arcs in a set of pairs, the
 * adjacency lists in a map from int to sets of ints, and the arc
 * costs in a map from pairs to doubles
 */
class Graph {

  //! the set of node IDs (normally 0, ..., n-1)
  std::set<int> node;

  //! the set of arcs 
  std::set<std::pair<int, int> > arc;

  //! the adjacency lists
  std::map<int, std::set<int> > adj;

  //! the arc costs
  std::map<std::pair<int, int>, double> arc_cost;

 public:
  /**
   * the default class constructor
   */
  Graph();

  /** 
   * the class constructor reading a graph from a file in .gph format
   * @param f is an input file stream (already opened and set on a
   * valid file with reading permissions set)
   * @see fromFile()
   */
  Graph(std::ifstream& f);

  /**
   * the default class destructor
   */
  ~Graph();

  /**
   * return the set of node IDs
   * @return a reference to the node set
   */
  std::set<int>& getNodeSet(void);

  /**
   * default method for iteratively building the graph: adds source
   * and dest to the list of nodes, adds the pair <source,dest> to the
   * list of arcs, adds the appropriate entry to the arc_cost map, and
   * updates the adjacency list (puts dest in adj[source])
   * @param source is the source node int ID
   * @param dest is the destination node int ID
   * @param cost is the arc cost
   */
  void addArc(int source, int dest, double cost);

  /**
   * parses a .gph file and reads the encoded graph into memory.
   * Format for the .gph file:
   * comments start with #, one line must contain the keyword
   * "Directed" or "Undirected" (in the latter case all edges are
   * interpreted as antiparallel pairs of arcs), and the arc lines
   * have the form "source destination cost", where source and
   * destination are integer node IDs, and cost is a double.
   * @param f is an input file stream (already opened and set on a
   * valid file with reading permissions set)
   */
  bool fromFile(std::ifstream& f);

  /**
   * print the adjacency lists of the graph
   */
  void print(void);

  /**
   * performs a Depth First Search exploration of the graph
   * @param source is the node from which the DFS search starts
   * @param visited keeps track of visited nodes (at the beginning it must
   * map every vertex to false)
   * @param spaces is an internal variable and should be set to the
   * empty string ""
   * @param method can be 1,2,3,4 according as to whether the output
   * should be a node preorder, an arc preorder, an arc postorder,
   * and a node postorder
   */
  void dfs(int source, std::map<int, bool>& visited, 
	   std::string& spaces, int method); 
};