//---------------------------------------------------------------------
//    Automated version of LEDAdijkstra.cc
//---------------------------------------------------------------------


// #define LEDA_CHECKING_OFF
#define LEDA_CHECKING_ON

#define SMPL_SIZ 100       // Find average over how big a sample size

#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;
  edge e;
  pq_item it;
                                                                               
  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..
  { it = PQ.find_min();           // Find node with min. label
    node u = PQ.inf(it);
    int du = dist[u];
    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(int argc, char ** argv)
{
  GRAPH<int,int> G;
  int n, m, M;

  if (argc < 4)
  {
    cout << string("Usage: %s <n> <m> <M>\n", argv[0])
         << "n=#nodes, m=#edges, M=max(cost(edge))"
         << endl
         << "Find avg. time of Dijkstra on 7 implementations of p_queues."
         << endl << "line 1 = p_queue"
         << endl << "line 2 = k_heap"
         << endl << "line 3 = m_heap"
         << endl << "line 4 = list_pq"
         << endl << "line 5 = p_heap"
         << endl << "line 6 = r_heap"
         << endl << "line 7 = bin_heap"
         << endl << "line 8 = LEDA's impl. of Dijkstra" << endl;
    exit(1);
  }
  else
    if (((n = atoi(argv[1])) < 0) ||
        ((m = atoi(argv[2])) < 0) ||
        ((M = atoi(argv[3])) < 0))
      exit(1);

  p_queue<int,node>* PQ[7];        // test 7 implementations of PQ
  float T_avg[8];                  // note: use T_avg[7] for default DIJKSTRA

  for (int i = 0; i < 8; i++) T_avg[i] = 0.0;  

  for (int t = SMPL_SIZ; t > 0; t--)
  {
    random_graph(G,n,m);           // generate random directed graph G
    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);

    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
 
    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();         // default DIJKSTRA
    DIJKSTRA (G,s,cost,dist0,pred);
    T_avg[7] += used_time(T);

    for (int i = 0; i < 7; i++)
    { 

      float T = used_time();       // other implementations
      dijkstra (G,s,cost,dist,pred,*(PQ[i]));
      T_avg[i] += used_time(T);

      node v;                      // verify solution against default DIJKSTRA
      forall_nodes(v,G)
        if( dist[v] != dist0[v]) 
        {
          cout << "Error (" << i << "):";
          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];
  }

  for (int i = 0; i < 8; i++)
    cout << string("%6.4f", T_avg[i]/(float)SMPL_SIZ) << endl;

  return 0;
}