/*******************************************************************************
+
+  LEDA 4.4.1  
+
+
+  shortest_path_time.c
+
+
+  Copyright (c) 1995-2003
+  by Algorithmic Solutions Software GmbH
+  All rights reserved.
+ 
*******************************************************************************/

// $Revision: 1.1.1.1 $  $Date: 2005/09/12 10:00:22 $


#include <LEDA/graph/graph_alg.h>
#include <LEDA/core/random.h>
#include <assert.h>
#include <LEDA/core/stack.h>
#include <LEDA/core/IO_interface.h>

using namespace leda;



IO_interface I("Shortest Paths: Running Times");

void test_all(string t, int n, int m)
{ GRAPH<int,int> G;

   if (t == "g") BF_GEN(G,n,m);
   else
   { random_graph(G,n,m);
     node v; edge e;

     int min = ( t == "r"? -100 : 0);
     forall_edges(e,G) G[e] = rand_int(min,1000);

     forall_nodes(v,G) G[v] = rand_int(1,1000);
     if ( t == "c" )
     { edge e;
       forall_edges(e,G) G[e] = G[e] + G[G.source(e)] - G[G.target(e)];
      }
    }

   node_array<int> dist(G);
   node_array<edge> pred(G);

   float T;



if (t == "n") I.write_demo("non-negative edge costs");
if (t == "c") I.write_demo("arbitrary edge costs, no negative cycle");
if (t == "r") I.write_demo("arbitrary edge costs");
if (t == "g") I.write_demo("BF generator");

T = used_time();

BELLMAN_FORD(G,G.first_node(),G.edge_data(),dist,pred);
I.write_demo("BELLMAN FORD,refined version: " , used_time(T));

if (t != "r" || m <= 10000)
{ BELLMAN_FORD_B(G,G.first_node(),G.edge_data(),dist,pred);
  I.write_demo("BELLMAN FORD, basic version:  " , used_time(T));
}
else
  I.write_demo("BELLMAN FORD, basic version:  too many edges");

if (t == "n" || t == "g")
{ DIJKSTRA(G,G.first_node(),G.edge_data(),dist,pred);
  I.write_demo("DIJKSTRA:                     " , used_time(T));
}

CHECK_SP(G,G.first_node(),G.edge_data(),dist,pred);
I.write_demo("CHECKING:                     " , used_time(T));

/*
if (t != "r" || m <= 10000)
{BELLMAN_FORD(G,G.first_node(),G.edge_data(),dist,pred);
I.write_demo("Stefans time:                 " , used_time(T));
}
else
  I.write_demo("Stefan's time:  too many edges");
*/
}

int main()
{

I.write_demo("We run a comparison of four different shortest-path algorithms \
on four different classes of graph.");

I.write_demo("The algorithms are the basic and the refined version of the \
Bellman--Ford algorithm (see the LEDA book for details), \
Dijkstras algorithm (if applicable), \
and an algorithm that checks \
the results of shortest-path calculations.");

I.write_demo("The four classes of graph are \
random graph with random non-negative edge costs, \
random graph with random edge costs but no negative cycles, \
random graph with random edge costs, \
and graph generated by the generator BF_GEN.");

I.write_demo("The basic Bellman--Ford algorithm is not run if \
there are more than 10000 edges. Even for m less than 10000, \
patience is required.");

  int n = I.read_int("n = ");
  int m = I.read_int("m = ");

  test_all("n",n,m); I.stop();
  test_all("c",n,m); I.stop();
  test_all("r",n,m); I.stop();
  test_all("g",n,m); 
  return 0;
}

