source: lemon-0.x/test/all_pairs_shortest_path_test.cc @ 2629:84354c78b068

/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2008
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

#include <iostream>
#include <vector>

#include <lemon/math.h>
#include <cstdlib>

#include <lemon/smart_graph.h>
#include <lemon/dijkstra.h>
#include <lemon/floyd_warshall.h>
#include <lemon/johnson.h>

#include <lemon/fib_heap.h>

#include <lemon/path.h>

#include <lemon/time_measure.h>
#include "test_tools.h"

using namespace lemon;
using namespace std;

int main(int argc, const char *argv[]) {
  typedef SmartGraph Graph;
  typedef Graph::Node Node;
  typedef Graph::Edge Edge;
  typedef Graph::NodeIt NodeIt;
  typedef Graph::EdgeIt EdgeIt;

  typedef Graph::EdgeMap<int> LengthMap;
  typedef Graph::NodeMap<int> DistMap;

  const int n = argc > 1 ? atoi(argv[1]) : 20;
  const int e = argc > 2 ? atoi(argv[2]) : int(n * log(double(n)));
  const int m = argc > 3 ? atoi(argv[3]) : 100;

  Graph graph;
  LengthMap length(graph);
  vector<Node> nodes;
  
  DistMap shift(graph);
  for (int i = 0; i < n; ++i) {
    Node node = graph.addNode();
    nodes.push_back(node);
    shift[node] = rnd[m];
  }

  for (int i = 0; i < e; ++i) {
    int s = rnd[n];
    int t = rnd[n];
    Edge edge = graph.addEdge(nodes[s], nodes[t]);
    length[edge] = rnd[m] - shift[nodes[s]] + shift[nodes[t]];
  }

  Johnson<Graph, LengthMap> johnson(graph, length);
  {
    Timer timer;
    johnson.run();
    cout << "Johnson: " << timer << endl;
  }

  typedef FibHeap<int, Graph::NodeMap<int> > IntFibHeap;
  Johnson<Graph, LengthMap>::DefStandardHeap<IntFibHeap>
    ::Create fibJohnson(graph, length);
  {
    Timer timer;
    fibJohnson.run();
    cout << "Johnson with fibonacci heap: " << timer << endl;
  }

  FloydWarshall<Graph, LengthMap> floyd(graph, length);
  {
    Timer timer;
    floyd.run();
    cout << "FloydWarshall: " << timer << endl;
  }    

  bool checked_path = false;

  for (NodeIt it(graph); it != INVALID; ++it) {
    for (NodeIt jt(graph); jt != INVALID; ++jt) {
      check(johnson.connected(it, jt) == floyd.connected(it, jt),
            "Wrong connection in all pairs shortest path");
      check(johnson.connected(it, jt) == fibJohnson.connected(it, jt),
            "Wrong connection in all pairs shortest path");
      if (johnson.connected(it, jt)) {
        if (it != jt && !checked_path) {
          {
            Path<Graph> path = johnson.path(it, jt);
            check(checkPath(graph, path), "Wrong path.");
            check(pathSource(graph, path) == it, "Wrong path.");
            check(pathTarget(graph, path) == jt, "Wrong path.");
          }
          {
            Path<Graph> path = floyd.path(it, jt);
            check(checkPath(graph, path), "Wrong path.");
            check(pathSource(graph, path) == it, "Wrong path.");
            check(pathTarget(graph, path) == jt, "Wrong path.");
          }
          checked_path = true;
          std::cout << "Path checked" << std::endl;
        }
        check(johnson.dist(it, jt) == floyd.dist(it, jt),
              "Wrong distance in all pairs shortest path");
        check(johnson.dist(it, jt) == fibJohnson.dist(it, jt),
              "Wrong distance in all pairs shortest path");
        if (it != jt) {
          check(johnson.dist(it, jt) == 
                johnson.dist(it, johnson.predNode(it, jt)) +
                length[johnson.predEdge(it, jt)],
                "Wrong edge in all pairs shortest path");
          check(fibJohnson.dist(it, jt) == 
                fibJohnson.dist(it, fibJohnson.predNode(it, jt)) +
                length[fibJohnson.predEdge(it, jt)],
                "Wrong edge in all pairs shortest path");
          check(floyd.dist(it, jt) == 
                floyd.dist(it, floyd.predNode(it, jt)) +
                length[floyd.predEdge(it, jt)],
                "Wrong edge in all pairs shortest path");
        }
      }
    }
  }

  return 0;
}