test/max_cardinality_search_test.cc
author Balazs Dezso <deba@inf.elte.hu>
Thu, 25 Nov 2010 22:45:29 +0100
changeset 1024 b84e68af8248
parent 916 70bee017b584
child 1092 dceba191c00d
permissions -rw-r--r--
LGF reader and writer for bipartite graphs (#69)
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
kpeter@955
   120
   check(maxcard.processed(s) && !maxcard.processed(x) &&
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();
kpeter@955
   130
   check(maxcard.cardinality(x)==2 && 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
}