/*
  Computing the minimum spanning tree of a graph from a given root node 
  - after Dijkstra.

  In this version of the algorithm, which in fact forms the basis of 
  the "Open Shortest Path First" algorithm used on Internet routers, 
  we start with a chosen root node and start to build a spanning tree
  from that node, selecting the minimum cost path along the way.  The
  algorithm computes the shortest possible route from the root node to
  all other nodes.
*/

using namespace std;
#include<vector>
#include<iostream>

#define INF 0x7fffffff
#define UNSEEN 0
#define FRONTIER 1
#define INTERIOR 2

class Vertex;
class Digraph;

/*
  For representing the graph, I chose a compromise approach.  The
  vertex objects are stored in an array (Digraph::V) and can therefore
  be uniquely referred to using the indices of this array.  Each
  vertex object contains a vector of neighbors.  That is, they contain
  a list of integers representing adjacent vertices in the array V.
  The Digraph class also contains a Status matrix, which parallels the
  V matrix, and records whether a vertex is in the UNSEEN, FRONTIER,
  or INTERIOR state.  This way, we don't have to keep separate
  structures for the frontier and interior lists, although this
  approach is slightly inefficient.  The Digraph::Previous array
  contains links to the -last vertex on the shortest path from the
  start/root-.  Initially, Previous[i]=i for every node i.  The costs
  of the edges is stored inside a 2D array.  This may seem
  inefficient, but makes the code much more rational.  It's possible
  to store the costs along the Neighbor indices inside each Vertex
  object, but that would make the coding horrendous and prone to
  errors.  It's also possible to forgo the Neighbor list and just use
  the Cost matrix for both purposes.  However, to implement Dijkstra's
  algorithm, one needs to have on hand the original adjacency list,
  which is what the Neighbor vectors conveniently give us.  In the
  Costs matrix, infinity (INF) is represented using 0x7fffffff, the
  largest 32-bit signed integer.

*/


class Vertex
{
public:
  vector<int> Neighbors;
};


// Note: the class does not contain any data, we will define
// subclasses if we want to have vertices with data.

class Digraph
{
public:
  int n;        // number of vertices
  Vertex* *V;    // Graph as array of pointers to vertices
  int** Costs;  // costs are stored inside a 2D array for convenience
  char *Status;  // UNSEEN, FRONTIER, or INTERIOR
  int *Previous; // links to previous vertices in shortest paths

  // constructor creates arrays.
  Digraph(int n0)
  {
    n = n0;
    V = new Vertex*[n];
    Costs = new int*[n];
    for(int i=0;i<n;i++) Costs[i] = new int[n];
    Status = new char[n];
    Previous = new int[n];
    for(int i=0;i<n;i++) { Status[i] = UNSEEN; Previous[i] = i; }
  }
  ~Digraph()
  {
    for (int i=0;i<n;i++) delete(V[i]);
    delete(V);
    delete(Status);
    delete(Previous);
  }
  
  // function that builds spanning tree from given starting root, returns
  // vector containing indices of all nodes reachable from start:
  void spantree(int start);
  int minfrontier(int start);
  void printpath(int dest);
};  // class Digraph

// finds shortest paths from start to all other nodes.
void Digraph::spantree(int start)
{
  // Assume that all nodes are initially marked UNSEEN
  // for (int i=0;i<n;i++) Status[i] = UNSEEN;
  int current = start;
  Status[start]=FRONTIER; 
  int fsize = 1; // keep track of size of frontier:
  while (fsize > 0)
    {
      // take element with min cost from frontier:
      current = minfrontier(start);
      Status[current] = INTERIOR;  
      fsize--; // just took one node off the frontier list
      // for each immediate neighbor of above vertex: calculate cost
      int ns = (V[current]->Neighbors).size();  // number of neighbors
      for(int i=0;i<ns;i++)
	{ 
	  int j = V[current]->Neighbors[i]; // j is index into V array
	  if (Status[j]!=INTERIOR)
	    {
	      int newcost = Costs[current][j] + Costs[start][current];
	      if (Costs[current][j]==INF || Costs[start][current]==INF)
		newcost = INF;
	      if (newcost<=Costs[start][j]) 
		{ Costs[start][j]=newcost;
                  Previous[j] = current;
		}
	      if (Status[j]!=FRONTIER) 
		{ Status[j] = FRONTIER;  fsize++; }
	    }
	} // for each neighbor of current

      // for tracing: prints status of each node:
      cout << "status: "; 
      for(int i=0;i<n;i++) cout << (int)Status[i] << "  ";
      cout << endl;

    } // while frontier not empty 
} // Digraph::spantree


/////////////////////////////////


// returns index into frontier vector that has least cost from start:
int Digraph::minfrontier(int start)
{
  int i;
  int axi = 0; int cost;
  int ax = INF;
  for(int i=0;i<n;i++)
    {
      if (Status[i]==FRONTIER)
	{
	  cost = Costs[start][i];
	  if (cost<ax) { ax=cost; axi = i;}
	}
    }
  return axi;
} // mincost

// prints path from start to node given destination.  The start node
// depends on what was used the last time spantree was called.
void Digraph::printpath(int dest)
{
  int prev = Previous[dest];
  if (prev==dest) cout << prev;
  else
    {
      printpath(prev);
      cout << " --> " << dest;
    }
}


// simple test: with costs of all edges = 1 except for v1-->v3
int main()
{
  // 4 vertex graph: v0-->v1-->v2, 
  //                      |    |
  //                      v    |
  //                      v3<---
  int n = 4;
  Digraph G(n);
  Vertex *v0 = new Vertex();
  Vertex *v1 = new Vertex();
  Vertex *v2 = new Vertex();
  Vertex *v3 = new Vertex();  
  G.V[0] = v0;  G.V[1] = v1; G.V[2] = v2; G.V[3] = v3;
  v0->Neighbors.push_back(1);
  v1->Neighbors.push_back(2); v1->Neighbors.push_back(3);
  v2->Neighbors.push_back(3);
  for (int i=0;i<n;i++) for(int j=0;j<n;j++)
    G.Costs[i][j] = INF;
  for(int i=0;i<n;i++) G.Costs[i][i] = 0;
  G.Costs[0][1] = 1;
  G.Costs[1][2] = 1;
  G.Costs[1][3] = 6;
  G.Costs[2][3] = 1;
  G.spantree(0); // build spanning tree with 0 as root.

  cout << "final cost vector for root node:\n";
  for (int j=0;j<n;j++) cout << G.Costs[0][j] << "\t";
  cout << endl;
  cout << "optimal path from v0 to v3: ";
  G.printpath(3);  cout << endl;
  return 0;
}

/*
  Pseudocode overview of the spanntree procedure:

  Pick a start node.

  Initially, the interior list is empty and the start node is in the
  frontier list

  loop while the frontier list is not empty:

     1. pick frontier element with minimum cost from the chosen start node,
        as given by the Cost matrix.  Call this node "current".

     2. move current from frontier to interior list

     3. For each immediate neighbor j of current, if j is already in the
        interior list, ignore it.  Otherwise, compute the new cost
        from start to j as the cost from start to current plus the cost
        from current to j.  If this cost is <= current known cost from
	start to j, then update the cost to the better value.  Add j to
        the frontier list if it's not there already, and record that
	j was reach via current (by setting the Previous array value).


 One important thing to keep in mind is that the result of the algorithm
 is only valid with respect to the chosen root node.  
*/