source: lemon-main/test/heap_test.cc @ 208:4317d277ba21

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

#include <lemon/concept_check.h>
#include <lemon/concepts/heap.h>

#include <lemon/smart_graph.h>

#include <lemon/lgf_reader.h>
#include <lemon/dijkstra.h>
#include <lemon/maps.h>

#include <lemon/bin_heap.h>

#include "test_tools.h"

using namespace lemon;
using namespace lemon::concepts;

typedef ListDigraph Digraph;
DIGRAPH_TYPEDEFS(Digraph);

char test_lgf[] = 
  "@nodes\n" 
  "label\n"     
  "0\n" 
  "1\n" 
  "2\n" 
  "3\n" 
  "4\n" 
  "5\n" 
  "6\n" 
  "7\n" 
  "8\n" 
  "9\n" 
  "@arcs\n" 
  "             label   capacity\n"     
  "0    5       0       94\n"   
  "3    9       1       11\n"   
  "8    7       2       83\n"   
  "1    2       3       94\n"   
  "5    7       4       35\n"   
  "7    4       5       84\n"   
  "9    5       6       38\n"   
  "0    4       7       96\n"   
  "6    7       8       6\n"    
  "3    1       9       27\n"   
  "5    2       10      77\n"   
  "5    6       11      69\n"   
  "6    5       12      41\n"   
  "4    6       13      70\n"   
  "3    2       14      45\n"   
  "7    9       15      93\n"   
  "5    9       16      50\n"   
  "9    0       17      94\n"   
  "9    6       18      67\n"   
  "0    9       19      86\n"   
  "@attributes\n" 
  "source 3\n";

int test_seq[] = { 2, 28, 19, 27, 33, 25, 13, 41, 10, 26,  1,  9,  4, 34};
int test_inc[] = {20, 28, 34, 16,  0, 46, 44,  0, 42, 32, 14,  8,  6, 37};

int test_len = sizeof(test_seq) / sizeof(test_seq[0]);

template <typename Heap>
void heapSortTest() {
  RangeMap<int> map(test_len, -1);

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

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

template <typename Heap>
void heapIncreaseTest() {
  RangeMap<int> map(test_len, -1);

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

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



template <typename Heap>
void dijkstraHeapTest(const Digraph& digraph, const IntArcMap& length, 
                      Node source) {
  
  typename Dijkstra<Digraph, IntArcMap>::template DefStandardHeap<Heap>::
    Create dijkstra(digraph, length);

  dijkstra.run(source);

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

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

}

int main() {

  typedef int Item;
  typedef int Prio;
  typedef RangeMap<int> ItemIntMap;
  
  Digraph digraph;
  IntArcMap length(digraph);
  Node source;

  std::istringstream input(test_lgf);
  digraphReader(input, digraph).
    arcMap("capacity", length).
    node("source", source).
    run();  
 
  {
    typedef BinHeap<Prio, ItemIntMap> IntHeap;
    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
    heapSortTest<IntHeap>();
    heapIncreaseTest<IntHeap>();
    
    typedef BinHeap<Prio, IntNodeMap > NodeHeap;
    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
    dijkstraHeapTest<NodeHeap>(digraph, length, source);
  }

  return 0;
}