COIN-OR::LEMON - Graph Library

source: lemon-0.x/test/all_pairs_shortest_path_test.cc @ 2180:d5544c9409e4

Last change on this file since 2180:d5544c9409e4 was 1956:a055123339d5, checked in by Alpar Juttner, 18 years ago

Unified copyright notices

File size: 3.6 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#include <iostream>
20#include <vector>
21
22#include <cmath>
23#include <cstdlib>
24
25#include <lemon/smart_graph.h>
26#include <lemon/dijkstra.h>
27#include <lemon/floyd_warshall.h>
28#include <lemon/johnson.h>
29
30#include <lemon/fib_heap.h>
31
32#include <lemon/time_measure.h>
33#include "test_tools.h"
34
35using namespace lemon;
36using namespace std;
37
38int main(int argc, const char *argv[]) {
39  srand(time(0));
40  typedef SmartGraph Graph;
41  typedef Graph::Node Node;
42  typedef Graph::Edge Edge;
43  typedef Graph::NodeIt NodeIt;
44  typedef Graph::EdgeIt EdgeIt;
45
46  typedef Graph::EdgeMap<double> LengthMap;
47  typedef Graph::NodeMap<double> DistMap;
48
49  const int n = argc > 1 ? atoi(argv[1]) : 20;
50  const int e = argc > 2 ? atoi(argv[2]) : (int)(n * log((double)n));
51  const double m = argc > 3 ? (double)atoi(argv[3]) : 100.0;
52
53  Graph graph;
54  LengthMap length(graph);
55  vector<Node> nodes;
56 
57  DistMap shift(graph);
58  for (int i = 0; i < n; ++i) {
59    Node node = graph.addNode();
60    nodes.push_back(node);
61    shift[node] = m * (double)rand() / (RAND_MAX + 1.0);
62  }
63
64  for (int i = 0; i < e; ++i) {
65    int s = (int)(n * (double)rand() / (RAND_MAX + 1.0));
66    int t = (int)(n * (double)rand() / (RAND_MAX + 1.0));
67    double c = m * (double)rand() / (RAND_MAX + 1.0);
68    Edge edge = graph.addEdge(nodes[s], nodes[t]);
69    length[edge] = c - shift[nodes[s]] + shift[nodes[t]];
70  }
71
72  Johnson<Graph, LengthMap> johnson(graph, length);
73  {
74    Timer timer;
75    johnson.run();
76    cout << "Johnson: " << timer << endl;
77  }
78
79  typedef FibHeap<Node, double, Graph::NodeMap<int> > DoubleFibHeap;
80  Johnson<Graph, LengthMap>::DefStandardHeap<DoubleFibHeap>
81    ::Create fibJohnson(graph, length);
82  {
83    Timer timer;
84    fibJohnson.run();
85    cout << "Johnson with fibonacci heap: " << timer << endl;
86  }
87
88  FloydWarshall<Graph, LengthMap> floyd(graph, length);
89  {
90    Timer timer;
91    floyd.run();
92    cout << "FloydWarshall: " << timer << endl;
93  }   
94
95  for (NodeIt it(graph); it != INVALID; ++it) {
96    for (NodeIt jt(graph); jt != INVALID; ++jt) {
97      check(johnson.connected(it, jt) == floyd.connected(it, jt),
98            "Wrong connection in all pairs shortest path");
99      check(johnson.connected(it, jt) == fibJohnson.connected(it, jt),
100            "Wrong connection in all pairs shortest path");
101      if (johnson.connected(it, jt)) {
102        check(johnson.dist(it, jt) == floyd.dist(it, jt),
103              "Wrong distance in all pairs shortest path");
104        check(johnson.dist(it, jt) == fibJohnson.dist(it, jt),
105              "Wrong distance in all pairs shortest path");
106        if (it != jt) {
107          check(johnson.dist(it, jt) ==
108                johnson.dist(it, johnson.predNode(it, jt)) +
109                length[johnson.predEdge(it, jt)],
110                "Wrong edge in all pairs shortest path");
111          check(fibJohnson.dist(it, jt) ==
112                fibJohnson.dist(it, fibJohnson.predNode(it, jt)) +
113                length[fibJohnson.predEdge(it, jt)],
114                "Wrong edge in all pairs shortest path");
115          check(floyd.dist(it, jt) ==
116                floyd.dist(it, floyd.predNode(it, jt)) +
117                length[floyd.predEdge(it, jt)],
118                "Wrong edge in all pairs shortest path");
119        }
120      }
121    }
122  }
123
124  return 0;
125}
Note: See TracBrowser for help on using the repository browser.