test/max_cardinality_search_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 15 Mar 2011 19:32:21 +0100
changeset 936 ddd3c0d3d9bf
child 955 7f6eeffe3cd1
permissions -rw-r--r--
Implement the scaling Price Refinement heuristic in CostScaling (#417)
instead of Early Termination.

These two heuristics are similar, but the newer one is faster
and not only makes it possible to skip some epsilon phases, but
it can improve the performance of the other phases, as well.
thoneyvazul@916
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
thoneyvazul@916
     2
 *
thoneyvazul@916
     3
 * This file is a part of LEMON, a generic C++ optimization library.
thoneyvazul@916
     4
 *
thoneyvazul@916
     5
 * Copyright (C) 2003-2010
thoneyvazul@916
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
thoneyvazul@916
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
thoneyvazul@916
     8
 *
thoneyvazul@916
     9
 * Permission to use, modify and distribute this software is granted
thoneyvazul@916
    10
 * provided that this copyright notice appears in all copies. For
thoneyvazul@916
    11
 * precise terms see the accompanying LICENSE file.
thoneyvazul@916
    12
 *
thoneyvazul@916
    13
 * This software is provided "AS IS" with no warranty of any kind,
thoneyvazul@916
    14
 * express or implied, and with no claim as to its suitability for any
thoneyvazul@916
    15
 * purpose.
thoneyvazul@916
    16
 *
thoneyvazul@916
    17
 */
thoneyvazul@916
    18
thoneyvazul@916
    19
#include <iostream>
thoneyvazul@916
    20
thoneyvazul@916
    21
#include "test_tools.h"
thoneyvazul@916
    22
#include <lemon/smart_graph.h>
thoneyvazul@916
    23
#include <lemon/max_cardinality_search.h>
thoneyvazul@916
    24
#include <lemon/concepts/digraph.h>
thoneyvazul@916
    25
#include <lemon/concepts/maps.h>
thoneyvazul@916
    26
#include <lemon/concepts/heap.h>
thoneyvazul@916
    27
#include <lemon/lgf_reader.h>
thoneyvazul@916
    28
thoneyvazul@916
    29
using namespace lemon;
thoneyvazul@916
    30
using namespace std;
thoneyvazul@916
    31
thoneyvazul@916
    32
char test_lgf[] =
thoneyvazul@916
    33
  "@nodes\n"
thoneyvazul@916
    34
  "label\n"
thoneyvazul@916
    35
  "0\n"
thoneyvazul@916
    36
  "1\n"
thoneyvazul@916
    37
  "2\n"
thoneyvazul@916
    38
  "3\n"
thoneyvazul@916
    39
  "@arcs\n"
thoneyvazul@916
    40
  "    label capacity\n"
thoneyvazul@916
    41
  "0 1 0     2\n"
thoneyvazul@916
    42
  "1 0 1     2\n"
thoneyvazul@916
    43
  "2 1 2     1\n"
thoneyvazul@916
    44
  "2 3 3     3\n"
thoneyvazul@916
    45
  "3 2 4     3\n"
thoneyvazul@916
    46
  "3 1 5     5\n"
thoneyvazul@916
    47
  "@attributes\n"
thoneyvazul@916
    48
  "s 0\n"
thoneyvazul@916
    49
  "x 1\n"
thoneyvazul@916
    50
  "y 2\n"
thoneyvazul@916
    51
  "z 3\n";
thoneyvazul@916
    52
thoneyvazul@916
    53
void checkMaxCardSearchCompile() {
thoneyvazul@916
    54
thoneyvazul@916
    55
  typedef concepts::Digraph Digraph;
thoneyvazul@916
    56
  typedef int Value;
thoneyvazul@916
    57
  typedef Digraph::Node Node;
thoneyvazul@916
    58
  typedef Digraph::Arc Arc;
thoneyvazul@916
    59
  typedef concepts::ReadMap<Arc,Value> CapMap;
thoneyvazul@916
    60
  typedef concepts::ReadWriteMap<Node,Value> CardMap;
thoneyvazul@916
    61
  typedef concepts::ReadWriteMap<Node,bool> ProcMap;
thoneyvazul@916
    62
  typedef Digraph::NodeMap<int> HeapCrossRef;
thoneyvazul@916
    63
thoneyvazul@916
    64
  Digraph g;
thoneyvazul@916
    65
  Node n,s;
thoneyvazul@916
    66
  CapMap cap;
thoneyvazul@916
    67
  CardMap card;
thoneyvazul@916
    68
  ProcMap proc;
thoneyvazul@916
    69
  HeapCrossRef crossref(g);
thoneyvazul@916
    70
  
thoneyvazul@916
    71
  typedef MaxCardinalitySearch<Digraph,CapMap>
thoneyvazul@916
    72
    ::SetCapacityMap<CapMap>
thoneyvazul@916
    73
    ::SetCardinalityMap<CardMap>
thoneyvazul@916
    74
    ::SetProcessedMap<ProcMap>
thoneyvazul@916
    75
    ::SetStandardHeap<BinHeap<Value,HeapCrossRef> >
thoneyvazul@916
    76
    ::Create MaxCardType;
thoneyvazul@916
    77
thoneyvazul@916
    78
  MaxCardType maxcard(g,cap);
thoneyvazul@916
    79
  const MaxCardType& const_maxcard = maxcard;
thoneyvazul@916
    80
thoneyvazul@916
    81
  const MaxCardType::Heap& heap_const = const_maxcard.heap();
thoneyvazul@916
    82
  MaxCardType::Heap& heap = const_cast<MaxCardType::Heap&>(heap_const);
thoneyvazul@916
    83
  maxcard.heap(heap,crossref);
thoneyvazul@916
    84
  
thoneyvazul@916
    85
  maxcard.capacityMap(cap).cardinalityMap(card).processedMap(proc);
thoneyvazul@916
    86
thoneyvazul@916
    87
  maxcard.init();
thoneyvazul@916
    88
  maxcard.addSource(s);
thoneyvazul@916
    89
  n = maxcard.nextNode();
thoneyvazul@916
    90
   maxcard.processNextNode();
thoneyvazul@916
    91
   maxcard.start();
thoneyvazul@916
    92
   maxcard.run(s);
thoneyvazul@916
    93
   maxcard.run();
thoneyvazul@916
    94
 }
thoneyvazul@916
    95
thoneyvazul@916
    96
 void checkWithIntMap( std::istringstream& input)
thoneyvazul@916
    97
 {
thoneyvazul@916
    98
   typedef SmartDigraph Digraph;
thoneyvazul@916
    99
   typedef Digraph::Node Node;
thoneyvazul@916
   100
   typedef Digraph::ArcMap<int> CapMap;
thoneyvazul@916
   101
thoneyvazul@916
   102
   Digraph g;
thoneyvazul@916
   103
   Node s,x,y,z,a;
thoneyvazul@916
   104
   CapMap cap(g);
thoneyvazul@916
   105
thoneyvazul@916
   106
   DigraphReader<Digraph>(g,input).
thoneyvazul@916
   107
     arcMap("capacity", cap).
thoneyvazul@916
   108
     node("s",s).
thoneyvazul@916
   109
     node("x",x).
thoneyvazul@916
   110
     node("y",y).
thoneyvazul@916
   111
     node("z",z).
thoneyvazul@916
   112
     run();
thoneyvazul@916
   113
thoneyvazul@916
   114
   MaxCardinalitySearch<Digraph,CapMap> maxcard(g,cap);
thoneyvazul@916
   115
thoneyvazul@916
   116
   maxcard.init();
thoneyvazul@916
   117
   maxcard.addSource(s);
thoneyvazul@916
   118
   maxcard.start(x);
thoneyvazul@916
   119
thoneyvazul@916
   120
   check(maxcard.processed(s) and !maxcard.processed(x) and
thoneyvazul@916
   121
         !maxcard.processed(y), "Wrong processed()!");
thoneyvazul@916
   122
thoneyvazul@916
   123
   a=maxcard.nextNode();
thoneyvazul@916
   124
   check(maxcard.processNextNode()==a,
thoneyvazul@916
   125
         "Wrong nextNode() or processNextNode() return value!");
thoneyvazul@916
   126
thoneyvazul@916
   127
   check(maxcard.processed(a), "Wrong processNextNode()!");
thoneyvazul@916
   128
thoneyvazul@916
   129
   maxcard.start();
thoneyvazul@916
   130
   check(maxcard.cardinality(x)==2 and maxcard.cardinality(y)>=4,
thoneyvazul@916
   131
         "Wrong cardinalities!");
thoneyvazul@916
   132
 }
thoneyvazul@916
   133
thoneyvazul@916
   134
 void checkWithConst1Map(std::istringstream &input) {
thoneyvazul@916
   135
   typedef SmartDigraph Digraph;
thoneyvazul@916
   136
   typedef Digraph::Node Node;
thoneyvazul@916
   137
thoneyvazul@916
   138
   Digraph g;
thoneyvazul@916
   139
   Node s,x,y,z;
thoneyvazul@916
   140
thoneyvazul@916
   141
  DigraphReader<Digraph>(g,input).
thoneyvazul@916
   142
    node("s",s).
thoneyvazul@916
   143
    node("x",x).
thoneyvazul@916
   144
    node("y",y).
thoneyvazul@916
   145
    node("z",z).
thoneyvazul@916
   146
    run();
thoneyvazul@916
   147
thoneyvazul@916
   148
  MaxCardinalitySearch<Digraph> maxcard(g);
thoneyvazul@916
   149
  maxcard.run(s);
thoneyvazul@916
   150
  check(maxcard.cardinality(x)==1 &&
thoneyvazul@916
   151
        maxcard.cardinality(y)+maxcard.cardinality(z)==3,
thoneyvazul@916
   152
        "Wrong cardinalities!");
thoneyvazul@916
   153
}
thoneyvazul@916
   154
thoneyvazul@916
   155
int main() {
thoneyvazul@916
   156
thoneyvazul@916
   157
  std::istringstream input1(test_lgf);
thoneyvazul@916
   158
  checkWithIntMap(input1);
thoneyvazul@916
   159
thoneyvazul@916
   160
  std::istringstream input2(test_lgf);
thoneyvazul@916
   161
  checkWithConst1Map(input2);
thoneyvazul@916
   162
}