source: lemon-main/test/heap_test.h @ 187:84c2a2e5cfee

/* -*- 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 <vector>
#include <algorithm>

#include <lemon/dijkstra.h>

class IntIntMap : public std::vector<int> {
public:
  typedef std::vector<int> Parent;

  typedef int Key;
  typedef int Value;

  IntIntMap() : Parent() {}
  IntIntMap(int n) : Parent(n) {}
  IntIntMap(int n, int v) : Parent(n, v) {}

  void set(int key, int value) {
    Parent::operator[](key) = value;
  }
};


template <typename _Heap>
void heapSortTest(int n) {
  typedef _Heap Heap;
  IntIntMap map(n, -1);

  Heap heap(map);
  
  std::vector<int> v(n);

  for (int i = 0; i < n; ++i) {
    v[i] = rnd[1000];
    heap.push(i, v[i]);
  }
  std::sort(v.begin(), v.end());
  for (int i = 0; i < n; ++i) {
    check(v[i] == heap.prio() ,"Wrong order in heap sort.");
    heap.pop();
  }
}

template <typename _Heap>
void heapIncreaseTest(int n) {
  typedef _Heap Heap;
  IntIntMap map(n, -1);

  Heap heap(map);
  
  std::vector<int> v(n);

  for (int i = 0; i < n; ++i) {
    v[i] = rnd[1000];
    heap.push(i, v[i]);
  }
  for (int i = 0; i < n; ++i) {
    v[i] += rnd[1000];
    heap.increase(i, v[i]);
  }
  std::sort(v.begin(), v.end());
  for (int i = 0; i < n; ++i) {
    check(v[i] == heap.prio() ,"Wrong order in heap increase test.");
    heap.pop();
  }
}



template <typename _Digraph, typename _LengthMap, typename _Heap>
void dijkstraHeapTest(_Digraph& digraph, _LengthMap& length,
                      typename _Digraph::Node& start) {

  typedef _Heap Heap;
  typedef _Digraph Digraph;
  typedef _LengthMap LengthMap;

  typedef typename Digraph::Node Node;
  typedef typename Digraph::Arc Arc;
  typedef typename Digraph::NodeIt NodeIt;
  typedef typename Digraph::ArcIt ArcIt;

  typename Dijkstra<Digraph, LengthMap>::template DefStandardHeap<Heap>::
    Create dijkstra(digraph, length);

  dijkstra.run(start);

  for(ArcIt e(digraph); e!=INVALID; ++e) {
    Node u=digraph.source(e); 
    Node v=digraph.target(e);
    if (dijkstra.reached(u)) {
      check( dijkstra.dist(v) - dijkstra.dist(u) <= length[e],
             "Error in a shortest path tree arc!");
    }
  }

  for(NodeIt v(digraph); v!=INVALID; ++v) {
    if ( dijkstra.reached(v) && dijkstra.predArc(v) != INVALID ) {
      Arc e=dijkstra.predArc(v);
      Node u=digraph.source(e);
      check( dijkstra.dist(v) - dijkstra .dist(u) == length[e],
             "Error in a shortest path tree arc!");
    }
  }

}