COIN-OR::LEMON - Graph Library

source: lemon-0.x/test/all_pairs_shortest_path_test.cc @ 2242:16523135943d

Last change on this file since 2242:16523135943d was 2242:16523135943d, checked in by Balazs Dezso, 17 years ago

New random interface
Switching to the new interface

File size: 3.4 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  typedef SmartGraph Graph;
40  typedef Graph::Node Node;
41  typedef Graph::Edge Edge;
42  typedef Graph::NodeIt NodeIt;
43  typedef Graph::EdgeIt EdgeIt;
44
45  typedef Graph::EdgeMap<int> LengthMap;
46  typedef Graph::NodeMap<int> DistMap;
47
48  const int n = argc > 1 ? atoi(argv[1]) : 20;
49  const int e = argc > 2 ? atoi(argv[2]) : (int)(n * log((double)n));
50  const int m = argc > 3 ? atoi(argv[3]) : 100;
51
52  Graph graph;
53  LengthMap length(graph);
54  vector<Node> nodes;
55 
56  DistMap shift(graph);
57  for (int i = 0; i < n; ++i) {
58    Node node = graph.addNode();
59    nodes.push_back(node);
60    shift[node] = rnd[m];
61  }
62
63  for (int i = 0; i < e; ++i) {
64    int s = rnd[n];
65    int t = rnd[n];
66    Edge edge = graph.addEdge(nodes[s], nodes[t]);
67    length[edge] = rnd[m] - shift[nodes[s]] + shift[nodes[t]];
68  }
69
70  Johnson<Graph, LengthMap> johnson(graph, length);
71  {
72    Timer timer;
73    johnson.run();
74    cout << "Johnson: " << timer << endl;
75  }
76
77  typedef FibHeap<Node, int, Graph::NodeMap<int> > IntFibHeap;
78  Johnson<Graph, LengthMap>::DefStandardHeap<IntFibHeap>
79    ::Create fibJohnson(graph, length);
80  {
81    Timer timer;
82    fibJohnson.run();
83    cout << "Johnson with fibonacci heap: " << timer << endl;
84  }
85
86  FloydWarshall<Graph, LengthMap> floyd(graph, length);
87  {
88    Timer timer;
89    floyd.run();
90    cout << "FloydWarshall: " << timer << endl;
91  }   
92
93  for (NodeIt it(graph); it != INVALID; ++it) {
94    for (NodeIt jt(graph); jt != INVALID; ++jt) {
95      check(johnson.connected(it, jt) == floyd.connected(it, jt),
96            "Wrong connection in all pairs shortest path");
97      check(johnson.connected(it, jt) == fibJohnson.connected(it, jt),
98            "Wrong connection in all pairs shortest path");
99      if (johnson.connected(it, jt)) {
100        check(johnson.dist(it, jt) == floyd.dist(it, jt),
101              "Wrong distance in all pairs shortest path");
102        check(johnson.dist(it, jt) == fibJohnson.dist(it, jt),
103              "Wrong distance in all pairs shortest path");
104        if (it != jt) {
105          check(johnson.dist(it, jt) ==
106                johnson.dist(it, johnson.predNode(it, jt)) +
107                length[johnson.predEdge(it, jt)],
108                "Wrong edge in all pairs shortest path");
109          check(fibJohnson.dist(it, jt) ==
110                fibJohnson.dist(it, fibJohnson.predNode(it, jt)) +
111                length[fibJohnson.predEdge(it, jt)],
112                "Wrong edge in all pairs shortest path");
113          check(floyd.dist(it, jt) ==
114                floyd.dist(it, floyd.predNode(it, jt)) +
115                length[floyd.predEdge(it, jt)],
116                "Wrong edge in all pairs shortest path");
117        }
118      }
119    }
120  }
121
122  return 0;
123}
Note: See TracBrowser for help on using the repository browser.