test/max_cardinality_search_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Tue, 16 Nov 2010 07:46:01 +0100
changeset 917 4980b05606bd
child 955 7f6eeffe3cd1
permissions -rw-r--r--
Merge
     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 }