/******************************************
 ** Dr. Brown's Project 1 class definition
 ** for graphs!
 ******************************************/
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <fstream>
#include <map>
using namespace std;

/*****************************************
 ** Class Vertex:  Each vertex keeps a
 ** list of its neighbors (N) as well as
 ** of all vertices of which it is a
 ** neighbor (P2Me), i.e. all vertices
 ** with edges pointing to it. 
 *****************************************/
class Vertex
{
public:
  //--------------------------//
  //-- Member Data -----------//
  //--------------------------//
  int index, dist, pred;
  char color;
  bool dead;        //-- if true, Vertex is ... dead
  string label;
  vector<int> N;    //-- Vertices I point to!
  vector<int> P2Me; //-- Vertices that point to me!

  //--------------------------//
  //-- Member Functions ------//
  //--------------------------//

  //-- Constructor: inits to index i and --//
  //-- label s. ---------------------------//
  Vertex(int i, string s) : index(i), label(s), dead(false) { } 

  //-- adds edge to w (vertex with index j)//
  void addEdge(int j, Vertex &w);

  //-- informs vertex that an edge from i -//
  //-- to it has been made. ---------------//
  void informNewEdge(int i);

  //-- removes edge to w (which is the ----//
  //-- vertex with index j. ---------------//
  void removeEdge(int j, Vertex &w);

  //-- informs vertex that edge from i to -//
  //-- to it has been removed. ------------//
  void informRemoveEdge(int i);
};

/*****************************************
 ** Class Graph: Vertices in a graph may
 ** be "dead" or "alive".  A "dead" Vertex
 ** simply takes up space in vector V. No
 ** vertex will have edges going to it, and
 ** it has no edges to any other vertex.
 **
 ** "Free" is a queue of indices of dead
 ** vertices, which may be recycled if new
 ** vertices are added.  "M" is phonebook
 ** in which you may lookup a label to get
 ** and index.
 *****************************************/
class Graph
{
public:
  //--------------------------//
  //-- Member Data -----------//
  //--------------------------//
  vector<Vertex> V;  //-- the vertices of the graph
  queue<int> Free;   //-- indices of "dead" vertices
  map<string,int> M; //-- lookup for "label" to get "index"

  //--------------------------//
  //-- Member Functions ------//
  //--------------------------//

  //-- Add vertex with label s. The index -//
  //-- of the new vertex is returned ------//
  int addVertex(string s); 

  //-- Remove vertex with label s ---------//
  void removeVertex(string s);

  //-- Add Edge from v_i to v_j -----------//
  void addEdge(int i, int j);

  //-- Add Edge from vertex L1 to vertex L2//
  void addEdge(string L1, string L2);

  //-- Remove Edge from v_i to v_j --------//
  void removeEdge(int i, int j);

  //-- Remove edge from vertex L1 to L2 ---//
  void removeEdge(string L1, string L2);

  //-- Find shortest path from v_i to v_j--//
  //-- true is returned if path exists, ---//
  //-- false otherwise. Q contains the path//
  bool findPath(int i, int j, vector<int> &Q);

  //-- Find shortest path from L1 to L2 ---//
  //-- true is returned if path exists, ---//
  //-- false otherwise. Q contains the path//   
  bool findPath(string L1, string L2, vector<int> &Q);

  //-- Perform breadth-first search -------//
  //-- starting from vertex i. ------------//
  void BFS(int i);

  //-- Print graph in aisee format to OUT -//
  void print(ostream &OUT);
};