//
// Combinatorial and Graph Algorithms
// by Leong Hon Wai (Sem 1, 1998)
//
// Updated by Melvin Zhang (Aug 30, 2008)
//   now works with LEDA 6.0
//
//---------------------------------------------------------------------
//    LEDA Program for Assignment 1
//    =============================
//     (Expt with Dijkstra's Alg.)
//
//    This code is modified from the LEDA standard distribution. 
//
//    It implements Dijkstra's algorithm using several priority
//    queue data structures..
//
//    The modification touches up the user interface (slightly) and
//    adds in some documentaion.
//---------------------------------------------------------------------


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

// #define LEDA_CHECKING_OFF
#define LEDA_CHECKING_ON

#include <LEDA/graph/graph_alg.h>
#include <LEDA/core/_p_queue.h>
#include <LEDA/core/impl/k_heap.h>
#include <LEDA/core/impl/f_heap.h>
#include <LEDA/core/impl/bin_heap.h>
#include <LEDA/core/impl/m_heap.h>
#include <LEDA/core/impl/p_heap.h>
#include <LEDA/core/impl/r_heap.h>
#include <LEDA/core/impl/list_pq.h>
using namespace leda;

//---------------------------------------------------------------------
//  This version of dijkstra's algorithm allows us to implement the
//  priority queue using different data structures.
//  You should examine this code carefully to learn how the different
//  implementations are done using only one program...  LHW(10/98)
//---------------------------------------------------------------------
template<class pq_impl>
void dijkstra(graph& G, 
              node s, 
              edge_array<int>&  cost, 
              node_array<int>&  dist,
              node_array<edge>& pred,
              p_queue<int,node,pq_impl>& PQ)    // additional parameter to specify
{                                               // PQ implementation...
  typedef typename p_queue<int,node,pq_impl>::item pq_item;
  node_array<pq_item> I(G);
  node v;

  forall_nodes(v,G)                       // Initialization phase
  { pred[v] = nil;
    dist[v] = MAXINT;
   }

  dist[s] = 0;                            // Build the priority queues
  I[s] = PQ.insert(0,s);

  while (! PQ.empty())                    // Main loop..
  { pq_item it = PQ.find_min();           // Find node with min. label
    node u = PQ.inf(it);
    int du = dist[u];
    edge e;
    forall_adj_edges(e,u)                 // Update labels of adj vtxes
    { v = G.target(e);
      int c = du + cost[e];
      if (c < dist[v])
      { if (dist[v] == MAXINT)
          I[v] = PQ.insert(c,v);
        else
          PQ.decrease_p(I[v],c);          // The decrease_key operation
        dist[v] = c;
        pred[v] = e;
       }
     }
    PQ.del_item(it);                       // Delete node from PQ
   }
}


main()
{

   cout << endl;
   cout << " CS5206 Fundamentals in Algorithms, NUS " << endl;
   cout << " LEDA Assignment 1 (Dijkstra Algorithms)" << endl << endl;

   cout << "//-------------------------------------------------------------\n"
        << "//  This program does the following:  \n"
        << "//                                    \n"
        << "//      prompts user;                 \n"
        << "//      generates a random weighted directed graph G    \n"
        << "//      Runs LEDA default DIJKSTRA algorithm on G       \n"
        << "//         prompts user for other implementation        \n"
        << "//         run other implementation of Dijkstra's on G  \n"
        << "//         repeat for other implementation              \n"
        << "//      Repeat for the next random graph G              \n"
        << "//                                                      \n"
        << "//-------------------------------------------------------------\n\n" << endl;

  GRAPH<int,int> G;

  for(;;)         // loop forever
  {

  cout << "/n ============================================================\n"
       << " We will now generate a new random weighted directed graph.  \n" 
       << " To do so, you will input the following parameters: \n" << endl;

  int n = read_int("# nodes (0 to end program) = ");
  if (n==0) break;

  int m = read_int("# edges = ");

  random_graph(G,n,m);             // Generate random directed graph G
                                   // with n nodes and m directed arcs

  edge_array<int>  cost(G);        // build edge-cost array
  node_array<int>  dist0(G);       // Labels computed by default DIJKSTRA
  node_array<int>  dist(G);    
  node_array<edge> pred(G);

  int M = read_int("max edge cost = ");

  edge e;                          // Now assign edge weights randomly
  forall_edges(e,G) G[e] = cost[e] = rand_int(0,M);

  node s = G.choose_node();        // Pick a start node s

  cout << "  Generated new graph with " << n << " nodes and " << m << " edges \n" << endl;


//------------------------------------------------------------
//  Note: The priority_queue PQ can be implemented using
//        different data structures -- giving rise to
//        different implementations of Dijkstra's alg.
//------------------------------------------------------------
  float T  = used_time();                       // begin timing
  DIJKSTRA(G,s,cost,dist0,pred);                // LEDA default Dijkstra algo.

  cout << endl << "The LEDA default DIJKSTRA: ";
  cout << " " << used_time(T) << " sec \n" << endl << endl;

  for(;;)                                       // inner loop
  {

    cout << " Now choose another implementation of dijkstra \n"
         << " (0:f_heap 1:k_heap 2:m_heap 3:list_pq 4:p_heap 5:r_heap 6:bin_heap) \n"
         << "    (type 7 or larger numbers to quit) :" ;

    int i = read_int();            // choose the impl. to run

    float T  = used_time();
	//dijkstra(G,s,cost,dist,pred,*(PQ[i]));                   // use i-th impl. of Dojkstra
	switch (i) {
		case 0: {
					p_queue<int,node,f_heap> PQ;
					dijkstra(G, s, cost, dist, pred, PQ);
					break;
				}
		case 1: {
					p_queue<int,node,k_heap> PQ(n);
					dijkstra(G, s, cost, dist, pred, PQ);
					break;
				}
		case 2: {
					p_queue<int,node,m_heap> PQ(M+1);
					dijkstra(G, s, cost, dist, pred, PQ);
					break;
				}
		case 3: {
					p_queue<int,node,list_pq> PQ;
					dijkstra(G, s, cost, dist, pred, PQ);
					break;
				}
		case 4: {
					p_queue<int,node,p_heap> PQ;
					dijkstra(G, s, cost, dist, pred, PQ);
					break;
				}
		case 5: {
					p_queue<int,node,r_heap> PQ(M);
					dijkstra(G, s, cost, dist, pred, PQ);
					break;
				}
		case 6: {
					p_queue<int,node,bin_heap> PQ(n);
					dijkstra(G, s, cost, dist, pred, PQ);
					break;
				}
		default: exit(0);
	}


    cout << " time: " << used_time(T) << " sec\n" << endl;


    node v;                     // verify that solution is correct -- against DIJKSTRA
    forall_nodes(v,G)
       if( dist[v] != dist0[v]) 
       { G.print_node(v);
         cout << "   dist =  " << dist[v] << "   dist0 = " << dist0[v] << "\n";
        }

   }
 }

 return 0;
}