#include <iostream>
#include <fstream>
#include <string>
#include <list>
#include <map>
#include <queue>
using namespace std;
#include "edge.h"


class graph  
{
	list<edge*> *vertices;			//array of all vertices (ints), the index from below
	map<string, int> vertexNumbers; //maps each name to the index for that vertex
	string *vertexName;				//inverse mapping from vertice index to name.
	int lastVertex;					//number of next vertex to insert

	map<string, int> edgeNumbers;
	string *edgeName;
	int lastEdge;

	int *known;						//These three are the table used to calculate
	int *distance;					// shortest path.
	int *previous;
public:
	void printShortestPath(string name); //prints the shortest path from the current
				//center (which was set when you called calculateShortestPaths) to
				// name.
	void initializeSPTable();		//initalizes known, distance and previous arrays
	void calculateShortestPaths(string center); //implements the shortest path alg.
	void readGraph(istream & is, int c);  //reads the graph from a file.
	int addVertex(string s);		//add a vertex
	int addEdge(string v1, string v2, string label); //add an edge
	graph(int numVertices, int numEdges);
	virtual ~graph();

};