test/heap_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 17 Apr 2009 18:04:36 +0200
changeset 609 e6927fe719e6
parent 293 47fbc814aa31
child 681 532697c9fa53
permissions -rw-r--r--
Support >= and <= constraints in NetworkSimplex (#219, #234)

By default the same inequality constraints are supported as by
Circulation (the GEQ form), but the LEQ form can also be selected
using the problemType() function.

The documentation of the min. cost flow module is reworked and
extended with important notes and explanations about the different
variants of the problem and about the dual solution and optimality
conditions.
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2009
     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 <fstream>
    21 #include <string>
    22 #include <vector>
    23 
    24 #include <lemon/concept_check.h>
    25 #include <lemon/concepts/heap.h>
    26 
    27 #include <lemon/smart_graph.h>
    28 
    29 #include <lemon/lgf_reader.h>
    30 #include <lemon/dijkstra.h>
    31 #include <lemon/maps.h>
    32 
    33 #include <lemon/bin_heap.h>
    34 
    35 #include "test_tools.h"
    36 
    37 using namespace lemon;
    38 using namespace lemon::concepts;
    39 
    40 typedef ListDigraph Digraph;
    41 DIGRAPH_TYPEDEFS(Digraph);
    42 
    43 char test_lgf[] =
    44   "@nodes\n"
    45   "label\n"
    46   "0\n"
    47   "1\n"
    48   "2\n"
    49   "3\n"
    50   "4\n"
    51   "5\n"
    52   "6\n"
    53   "7\n"
    54   "8\n"
    55   "9\n"
    56   "@arcs\n"
    57   "                label   capacity\n"
    58   "0       5       0       94\n"
    59   "3       9       1       11\n"
    60   "8       7       2       83\n"
    61   "1       2       3       94\n"
    62   "5       7       4       35\n"
    63   "7       4       5       84\n"
    64   "9       5       6       38\n"
    65   "0       4       7       96\n"
    66   "6       7       8       6\n"
    67   "3       1       9       27\n"
    68   "5       2       10      77\n"
    69   "5       6       11      69\n"
    70   "6       5       12      41\n"
    71   "4       6       13      70\n"
    72   "3       2       14      45\n"
    73   "7       9       15      93\n"
    74   "5       9       16      50\n"
    75   "9       0       17      94\n"
    76   "9       6       18      67\n"
    77   "0       9       19      86\n"
    78   "@attributes\n"
    79   "source 3\n";
    80 
    81 int test_seq[] = { 2, 28, 19, 27, 33, 25, 13, 41, 10, 26,  1,  9,  4, 34};
    82 int test_inc[] = {20, 28, 34, 16,  0, 46, 44,  0, 42, 32, 14,  8,  6, 37};
    83 
    84 int test_len = sizeof(test_seq) / sizeof(test_seq[0]);
    85 
    86 template <typename Heap>
    87 void heapSortTest() {
    88   RangeMap<int> map(test_len, -1);
    89 
    90   Heap heap(map);
    91 
    92   std::vector<int> v(test_len);
    93 
    94   for (int i = 0; i < test_len; ++i) {
    95     v[i] = test_seq[i];
    96     heap.push(i, v[i]);
    97   }
    98   std::sort(v.begin(), v.end());
    99   for (int i = 0; i < test_len; ++i) {
   100     check(v[i] == heap.prio() ,"Wrong order in heap sort.");
   101     heap.pop();
   102   }
   103 }
   104 
   105 template <typename Heap>
   106 void heapIncreaseTest() {
   107   RangeMap<int> map(test_len, -1);
   108 
   109   Heap heap(map);
   110 
   111   std::vector<int> v(test_len);
   112 
   113   for (int i = 0; i < test_len; ++i) {
   114     v[i] = test_seq[i];
   115     heap.push(i, v[i]);
   116   }
   117   for (int i = 0; i < test_len; ++i) {
   118     v[i] += test_inc[i];
   119     heap.increase(i, v[i]);
   120   }
   121   std::sort(v.begin(), v.end());
   122   for (int i = 0; i < test_len; ++i) {
   123     check(v[i] == heap.prio() ,"Wrong order in heap increase test.");
   124     heap.pop();
   125   }
   126 }
   127 
   128 
   129 
   130 template <typename Heap>
   131 void dijkstraHeapTest(const Digraph& digraph, const IntArcMap& length,
   132                       Node source) {
   133 
   134   typename Dijkstra<Digraph, IntArcMap>::template SetStandardHeap<Heap>::
   135     Create dijkstra(digraph, length);
   136 
   137   dijkstra.run(source);
   138 
   139   for(ArcIt a(digraph); a != INVALID; ++a) {
   140     Node s = digraph.source(a);
   141     Node t = digraph.target(a);
   142     if (dijkstra.reached(s)) {
   143       check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a],
   144              "Error in a shortest path tree!");
   145     }
   146   }
   147 
   148   for(NodeIt n(digraph); n != INVALID; ++n) {
   149     if ( dijkstra.reached(n) && dijkstra.predArc(n) != INVALID ) {
   150       Arc a = dijkstra.predArc(n);
   151       Node s = digraph.source(a);
   152       check( dijkstra.dist(n) - dijkstra.dist(s) == length[a],
   153              "Error in a shortest path tree!");
   154     }
   155   }
   156 
   157 }
   158 
   159 int main() {
   160 
   161   typedef int Item;
   162   typedef int Prio;
   163   typedef RangeMap<int> ItemIntMap;
   164 
   165   Digraph digraph;
   166   IntArcMap length(digraph);
   167   Node source;
   168 
   169   std::istringstream input(test_lgf);
   170   digraphReader(digraph, input).
   171     arcMap("capacity", length).
   172     node("source", source).
   173     run();
   174 
   175   {
   176     typedef BinHeap<Prio, ItemIntMap> IntHeap;
   177     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
   178     heapSortTest<IntHeap>();
   179     heapIncreaseTest<IntHeap>();
   180 
   181     typedef BinHeap<Prio, IntNodeMap > NodeHeap;
   182     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
   183     dijkstraHeapTest<NodeHeap>(digraph, length, source);
   184   }
   185 
   186   return 0;
   187 }