lemon-0.x: test/all_pairs_shortest_path

     1 #include <iostream>

     2 #include <vector>

     4 #include <cmath>

     5 #include <cstdlib>

     7 #include <lemon/smart_graph.h>

     8 #include <lemon/dijkstra.h>

     9 #include <lemon/floyd_warshall.h>

    10 #include <lemon/johnson.h>

    12 #include <lemon/fib_heap.h>

    14 #include <lemon/time_measure.h>

    15 #include "test_tools.h"

    17 using namespace lemon;

    18 using namespace std;

    20 int main(int argc, const char *argv[]) {

    21   srand(time(0));

    22   typedef SmartGraph Graph;

    23   typedef Graph::Node Node;

    24   typedef Graph::Edge Edge;

    25   typedef Graph::NodeIt NodeIt;

    26   typedef Graph::EdgeIt EdgeIt;

    28   typedef Graph::EdgeMap<double> LengthMap;

    29   typedef Graph::NodeMap<double> DistMap;

    31   const int n = argc > 1 ? atoi(argv[1]) : 20;

    32   const int e = argc > 2 ? atoi(argv[2]) : (int)(n * log((double)n));

    33   const double m = argc > 3 ? (double)atoi(argv[3]) : 100.0;

    35   Graph graph;

    36   LengthMap length(graph);

    37   vector<Node> nodes;

    39   DistMap shift(graph);

    40   for (int i = 0; i < n; ++i) {

    41     Node node = graph.addNode();

    42     nodes.push_back(node);

    43     shift[node] = m * (double)rand() / (RAND_MAX + 1.0);

    44   }

    46   for (int i = 0; i < e; ++i) {

    47     int s = (int)(n * (double)rand() / (RAND_MAX + 1.0));

    48     int t = (int)(n * (double)rand() / (RAND_MAX + 1.0));

    49     double c = m * (double)rand() / (RAND_MAX + 1.0);

    50     Edge edge = graph.addEdge(nodes[s], nodes[t]);

    51     length[edge] = c - shift[nodes[s]] + shift[nodes[t]];

    52   }

    54   Johnson<Graph, LengthMap> johnson(graph, length);

    55   {

    56     Timer timer;

    57     johnson.run();

    58     cout << "Johnson: " << timer << endl;

    59   }

    61   typedef FibHeap<Node, double, Graph::NodeMap<int> > DoubleFibHeap;

    62   Johnson<Graph, LengthMap>::DefStandardHeap<DoubleFibHeap>

    63     ::Create fibJohnson(graph, length);

    64   {

    65     Timer timer;

    66     fibJohnson.run();

    67     cout << "Johnson with fibonacci heap: " << timer << endl;

    68   }

    70   FloydWarshall<Graph, LengthMap> floyd(graph, length);

    71   {

    72     Timer timer;

    73     floyd.run();

    74     cout << "FloydWarshall: " << timer << endl;

    75   }

    77   for (NodeIt it(graph); it != INVALID; ++it) {

    78     for (NodeIt jt(graph); jt != INVALID; ++jt) {

    79       check(johnson.connected(it, jt) == floyd.connected(it, jt),

    80 	    "Wrong connection in all pairs shortest path");

    81       check(johnson.connected(it, jt) == fibJohnson.connected(it, jt),

    82 	    "Wrong connection in all pairs shortest path");

    83       if (johnson.connected(it, jt)) {

    84 	check(johnson.dist(it, jt) == floyd.dist(it, jt),

    85 	      "Wrong distance in all pairs shortest path");

    86 	check(johnson.dist(it, jt) == fibJohnson.dist(it, jt),

    87 	      "Wrong distance in all pairs shortest path");

    88 	if (it != jt) {

    89  	  check(johnson.dist(it, jt) ==

    90 		johnson.dist(it, johnson.predNode(it, jt)) +

    91 		length[johnson.predEdge(it, jt)],

    92 		"Wrong edge in all pairs shortest path");

    93  	  check(fibJohnson.dist(it, jt) ==

    94 		fibJohnson.dist(it, fibJohnson.predNode(it, jt)) +

    95 		length[fibJohnson.predEdge(it, jt)],

    96 		"Wrong edge in all pairs shortest path");

    97 	  check(floyd.dist(it, jt) ==

    98 		floyd.dist(it, floyd.predNode(it, jt)) +

    99 		length[floyd.predEdge(it, jt)],

   100 		"Wrong edge in all pairs shortest path");

   101 	}

   102       }

   103     }

   104   }

   106   return 0;

   107 }

author	hegyi
	Mon, 09 Jan 2006 12:41:06 +0000
changeset 1887	22fdc00894aa
parent 1745	d356e54bdafc
child 1956	a055123339d5
permissions	-rw-r--r--