RhodeCode

	  State state;

	  ignore_unused_variable_warning(state);

	  state = heap.state(item);

	  heap.state(item, state);

	  state = heap.state(own_item);

	  state = _Heap::PRE_HEAP;

	  state = _Heap::IN_HEAP;

	  state = _Heap::POST_HEAP;

	test/heap_test.h \

# test_heap_test_SOURCES = test/heap_test.cc

#include <lemon/list_graph.h>

#include <lemon/digraph_reader.h>

#include <lemon/fib_heap.h>

#include <lemon/radix_heap.h>

#include <lemon/bucket_heap.h>

#include "heap_test.h"

#include <lemon/time_measure.h>

  typedef IntIntMap ItemIntMap;

  typedef ListDigraph Digraph;

  typedef Digraph::Arc Arc;

  typedef Digraph::Node Node;

  typedef Digraph::ArcIt ArcIt;

  typedef Digraph::NodeIt NodeIt;

  typedef Digraph::ArcMap<int> LengthMap;

  LengthMap length(digraph);

  Node start;

  /// \todo create own test digraph

  std::string f_name;

  if( getenv("srcdir") )

    f_name = std::string(getenv("srcdir"));

  else f_name = ".";

  f_name += "/test/dijkstra_test.lgf";

  std::ifstream input(f_name.c_str());

  check(input, "Input file '" << f_name << "' not found.");

  DigraphReader<Digraph>(input, digraph).

    readArcMap("capacity", length).

    readNode("source", start).

    std::cout << "Checking Bin Heap" << std::endl;

    heapSortTest<IntHeap>(100);

    heapIncreaseTest<IntHeap>(100);

    typedef FibHeap<Prio, Digraph::NodeMap<int> > NodeHeap;

    checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();

    Timer timer;

    dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);

    std::cout << timer << std::endl;

  }

  {

    std::cout << "Checking Fib Heap" << std::endl;

    typedef FibHeap<Prio, ItemIntMap> IntHeap;

    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();

    heapSortTest<IntHeap>(100);

    heapIncreaseTest<IntHeap>(100);

    typedef FibHeap<Prio, Digraph::NodeMap<int> > NodeHeap;

    checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();

    Timer timer;

    dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);

    std::cout << timer << std::endl;

  }

  {

    std::cout << "Checking Radix Heap" << std::endl;

    typedef RadixHeap<ItemIntMap> IntHeap;

    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();

    heapSortTest<IntHeap>(100);

    heapIncreaseTest<IntHeap>(100);

    typedef RadixHeap<Digraph::NodeMap<int> > NodeHeap;

    checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();

    Timer timer;

    dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);

    std::cout << timer << std::endl;

  }

  {

    std::cout << "Checking Bucket Heap" << std::endl;

    typedef BucketHeap<ItemIntMap> IntHeap;

    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();

    heapSortTest<IntHeap>(100);

    heapIncreaseTest<IntHeap>(100);

    typedef BucketHeap<Digraph::NodeMap<int> > NodeHeap;

    checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();

    Timer timer;

    dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);

    std::cout << timer << std::endl;

/* -*- 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!");

    }

  }

}