test/max_cardinality_search_test.cc
changeset 917 4980b05606bd
child 955 7f6eeffe3cd1
equal deleted inserted replaced
-1:000000000000 0:06119d97efc5
       
     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-2010
       
     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 
       
    21 #include "test_tools.h"
       
    22 #include <lemon/smart_graph.h>
       
    23 #include <lemon/max_cardinality_search.h>
       
    24 #include <lemon/concepts/digraph.h>
       
    25 #include <lemon/concepts/maps.h>
       
    26 #include <lemon/concepts/heap.h>
       
    27 #include <lemon/lgf_reader.h>
       
    28 
       
    29 using namespace lemon;
       
    30 using namespace std;
       
    31 
       
    32 char test_lgf[] =
       
    33   "@nodes\n"
       
    34   "label\n"
       
    35   "0\n"
       
    36   "1\n"
       
    37   "2\n"
       
    38   "3\n"
       
    39   "@arcs\n"
       
    40   "    label capacity\n"
       
    41   "0 1 0     2\n"
       
    42   "1 0 1     2\n"
       
    43   "2 1 2     1\n"
       
    44   "2 3 3     3\n"
       
    45   "3 2 4     3\n"
       
    46   "3 1 5     5\n"
       
    47   "@attributes\n"
       
    48   "s 0\n"
       
    49   "x 1\n"
       
    50   "y 2\n"
       
    51   "z 3\n";
       
    52 
       
    53 void checkMaxCardSearchCompile() {
       
    54 
       
    55   typedef concepts::Digraph Digraph;
       
    56   typedef int Value;
       
    57   typedef Digraph::Node Node;
       
    58   typedef Digraph::Arc Arc;
       
    59   typedef concepts::ReadMap<Arc,Value> CapMap;
       
    60   typedef concepts::ReadWriteMap<Node,Value> CardMap;
       
    61   typedef concepts::ReadWriteMap<Node,bool> ProcMap;
       
    62   typedef Digraph::NodeMap<int> HeapCrossRef;
       
    63 
       
    64   Digraph g;
       
    65   Node n,s;
       
    66   CapMap cap;
       
    67   CardMap card;
       
    68   ProcMap proc;
       
    69   HeapCrossRef crossref(g);
       
    70   
       
    71   typedef MaxCardinalitySearch<Digraph,CapMap>
       
    72     ::SetCapacityMap<CapMap>
       
    73     ::SetCardinalityMap<CardMap>
       
    74     ::SetProcessedMap<ProcMap>
       
    75     ::SetStandardHeap<BinHeap<Value,HeapCrossRef> >
       
    76     ::Create MaxCardType;
       
    77 
       
    78   MaxCardType maxcard(g,cap);
       
    79   const MaxCardType& const_maxcard = maxcard;
       
    80 
       
    81   const MaxCardType::Heap& heap_const = const_maxcard.heap();
       
    82   MaxCardType::Heap& heap = const_cast<MaxCardType::Heap&>(heap_const);
       
    83   maxcard.heap(heap,crossref);
       
    84   
       
    85   maxcard.capacityMap(cap).cardinalityMap(card).processedMap(proc);
       
    86 
       
    87   maxcard.init();
       
    88   maxcard.addSource(s);
       
    89   n = maxcard.nextNode();
       
    90    maxcard.processNextNode();
       
    91    maxcard.start();
       
    92    maxcard.run(s);
       
    93    maxcard.run();
       
    94  }
       
    95 
       
    96  void checkWithIntMap( std::istringstream& input)
       
    97  {
       
    98    typedef SmartDigraph Digraph;
       
    99    typedef Digraph::Node Node;
       
   100    typedef Digraph::ArcMap<int> CapMap;
       
   101 
       
   102    Digraph g;
       
   103    Node s,x,y,z,a;
       
   104    CapMap cap(g);
       
   105 
       
   106    DigraphReader<Digraph>(g,input).
       
   107      arcMap("capacity", cap).
       
   108      node("s",s).
       
   109      node("x",x).
       
   110      node("y",y).
       
   111      node("z",z).
       
   112      run();
       
   113 
       
   114    MaxCardinalitySearch<Digraph,CapMap> maxcard(g,cap);
       
   115 
       
   116    maxcard.init();
       
   117    maxcard.addSource(s);
       
   118    maxcard.start(x);
       
   119 
       
   120    check(maxcard.processed(s) and !maxcard.processed(x) and
       
   121          !maxcard.processed(y), "Wrong processed()!");
       
   122 
       
   123    a=maxcard.nextNode();
       
   124    check(maxcard.processNextNode()==a,
       
   125          "Wrong nextNode() or processNextNode() return value!");
       
   126 
       
   127    check(maxcard.processed(a), "Wrong processNextNode()!");
       
   128 
       
   129    maxcard.start();
       
   130    check(maxcard.cardinality(x)==2 and maxcard.cardinality(y)>=4,
       
   131          "Wrong cardinalities!");
       
   132  }
       
   133 
       
   134  void checkWithConst1Map(std::istringstream &input) {
       
   135    typedef SmartDigraph Digraph;
       
   136    typedef Digraph::Node Node;
       
   137 
       
   138    Digraph g;
       
   139    Node s,x,y,z;
       
   140 
       
   141   DigraphReader<Digraph>(g,input).
       
   142     node("s",s).
       
   143     node("x",x).
       
   144     node("y",y).
       
   145     node("z",z).
       
   146     run();
       
   147 
       
   148   MaxCardinalitySearch<Digraph> maxcard(g);
       
   149   maxcard.run(s);
       
   150   check(maxcard.cardinality(x)==1 &&
       
   151         maxcard.cardinality(y)+maxcard.cardinality(z)==3,
       
   152         "Wrong cardinalities!");
       
   153 }
       
   154 
       
   155 int main() {
       
   156 
       
   157   std::istringstream input1(test_lgf);
       
   158   checkWithIntMap(input1);
       
   159 
       
   160   std::istringstream input2(test_lgf);
       
   161   checkWithConst1Map(input2);
       
   162 }