#include <iostream>
#include "dgraph.h"
#include "dgraph_factory.h"  // random graph generation
#include "dijkstra.h"   // Dijkstra's algorithm
#include "heaps/heap_lib.h"  // heaps
#include "timing.h"      // timer

using namespace std;

int main(void)
{
    cout << "Enter maximum edge cost: ";
    int maxEdgeCost;
    cin >> maxEdgeCost;
    
    // Create a random graph of 500000 vertices with an average of 2.5 outgoing
    // edges per vertex.
    DGraphFactory *f = DGraphFactory::instancePtr();
    f->setEdgeCostRange(1,maxEdgeCost);
    DGraph *g = f->newRandomSparse(500000,4.0);

    // Create heap descriptor objects for specifying the kind of heap to be
    // used by Dijkstra's algorithm.  The type of the heap descriptor is
    // specified using the template HeapD<T> where T = BHeap, FHeap, RadixHeap,
    // Heap23, or TriHeap.
    HeapD<RadixHeap> heapD;

    // Create an instance of Dijkstra's algorithm for use with up to 500000
    // vertices.
    Dijkstra *dijkstra = new Dijkstra(500000,&heapD);

    // time a run of Dijkstra's algorithm on the graph
    Timer t1;
    long d[500000];  // result array
    for(int v = 0; v < 500000; v++) d[v] = INFINITE_DIST;  // initialise
    t1.start();
    dijkstra->init(g); // specify the graph
    dijkstra->run(d); // run: this assumes that vertex 0 is the starting vertex
    t1.stop();    
    cout << "Time = ";
    t1.print("%.0f",1);
    cout << " msec" << endl;
    
    // tidy up
    delete dijkstra;
    delete g;
    delete f;
}