//
// Combinatorial and Graph Algorithms
// by Leong Hon Wai (Sem 1, 1998)
//
// Remember: compile with 
//   g++ -lG -lL ...
//---------------------------------------------------------------------
//    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.
//---------------------------------------------------------------------


// #define LEDA_CHECKING_OFF
#define LEDA_CHECKING_ON


#include <LEDA/graph_alg.h>
#include <LEDA/_p_queue.h>


//---------------------------------------------------------------------
//  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)
//---------------------------------------------------------------------
void dijkstra(graph& G, 
              node s, 
              edge_array<int>&  cost, 
              node_array<int>&  dist,
              node_array<edge>& pred,
              p_queue<int,node>&   PQ)    // additional parameter to specify
{                                         // PQ implementation...
  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
   }
}



#include <LEDA/impl/k_heap.h>
#include <LEDA/impl/bin_heap.h>
#include <LEDA/impl/m_heap.h>
#include <LEDA/impl/p_heap.h>
#include <LEDA/impl/r_heap.h>
#include <LEDA/impl/list_pq.h>


main()
{

   cout << endl;
   cout << " Combinatorial and Graph Algorithms, NUS " << endl;
   cout << " LEDA Assignment 1 (Shortest Path Algorithm)" << 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.
//------------------------------------------------------------
  p_queue<int,node>* PQ[8];

  PQ[0] = new p_queue<int,node>;                  
  PQ[1] = new _p_queue<int,node,k_heap>(n);         
  PQ[2] = new _p_queue<int,node,m_heap>(M);
  PQ[3] = new _p_queue<int,node,list_pq>;
  PQ[4] = new _p_queue<int,node,p_heap>;
  PQ[5] = new _p_queue<int,node,r_heap>(M);
  PQ[6] = new _p_queue<int,node,bin_heap>(n);

  float T  = used_time();                       // begin timing
  DIJKSTRA(G,s,cost,dist0,pred);                // LEDA default Dijkstra algo.

  cout << endl << "The LEDA default DIJKSTRA: ";
  cout << string( " %6.2f sec \n", used_time(T) ) << 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

    if (i>6) exit(0);

    float T  = used_time();
    dijkstra(G,s,cost,dist,pred,*(PQ[i]));                   // use i-th impl. of Dojkstra

    cout << string(" time: %6.2f sec\n", used_time(T) ) << endl;


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

   }

  delete PQ[0];
  delete PQ[1];
  delete PQ[2];
  delete PQ[3];
  delete PQ[4];
  delete PQ[5];
  delete PQ[6];

 }


 return 0;
}