thoneyvazul@1020: /* -*- mode: C++; indent-tabs-mode: nil; -*-
thoneyvazul@1020:  *
thoneyvazul@1020:  * This file is a part of LEMON, a generic C++ optimization library.
thoneyvazul@1020:  *
thoneyvazul@1020:  * Copyright (C) 2003-2010
thoneyvazul@1020:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
thoneyvazul@1020:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
thoneyvazul@1020:  *
thoneyvazul@1020:  * Permission to use, modify and distribute this software is granted
thoneyvazul@1020:  * provided that this copyright notice appears in all copies. For
thoneyvazul@1020:  * precise terms see the accompanying LICENSE file.
thoneyvazul@1020:  *
thoneyvazul@1020:  * This software is provided "AS IS" with no warranty of any kind,
thoneyvazul@1020:  * express or implied, and with no claim as to its suitability for any
thoneyvazul@1020:  * purpose.
thoneyvazul@1020:  *
thoneyvazul@1020:  */
thoneyvazul@1020: 
thoneyvazul@1020: #include <iostream>
thoneyvazul@1020: 
thoneyvazul@1020: #include "test_tools.h"
thoneyvazul@1020: #include <lemon/smart_graph.h>
thoneyvazul@1020: #include <lemon/max_cardinality_search.h>
thoneyvazul@1020: #include <lemon/concepts/digraph.h>
thoneyvazul@1020: #include <lemon/concepts/maps.h>
thoneyvazul@1020: #include <lemon/concepts/heap.h>
thoneyvazul@1020: #include <lemon/lgf_reader.h>
thoneyvazul@1020: 
thoneyvazul@1020: using namespace lemon;
thoneyvazul@1020: using namespace std;
thoneyvazul@1020: 
thoneyvazul@1020: char test_lgf[] =
thoneyvazul@1020:   "@nodes\n"
thoneyvazul@1020:   "label\n"
thoneyvazul@1020:   "0\n"
thoneyvazul@1020:   "1\n"
thoneyvazul@1020:   "2\n"
thoneyvazul@1020:   "3\n"
thoneyvazul@1020:   "@arcs\n"
thoneyvazul@1020:   "    label capacity\n"
thoneyvazul@1020:   "0 1 0     2\n"
thoneyvazul@1020:   "1 0 1     2\n"
thoneyvazul@1020:   "2 1 2     1\n"
thoneyvazul@1020:   "2 3 3     3\n"
thoneyvazul@1020:   "3 2 4     3\n"
thoneyvazul@1020:   "3 1 5     5\n"
thoneyvazul@1020:   "@attributes\n"
thoneyvazul@1020:   "s 0\n"
thoneyvazul@1020:   "x 1\n"
thoneyvazul@1020:   "y 2\n"
thoneyvazul@1020:   "z 3\n";
thoneyvazul@1020: 
thoneyvazul@1020: void checkMaxCardSearchCompile() {
thoneyvazul@1020: 
thoneyvazul@1020:   typedef concepts::Digraph Digraph;
thoneyvazul@1020:   typedef int Value;
thoneyvazul@1020:   typedef Digraph::Node Node;
thoneyvazul@1020:   typedef Digraph::Arc Arc;
thoneyvazul@1020:   typedef concepts::ReadMap<Arc,Value> CapMap;
thoneyvazul@1020:   typedef concepts::ReadWriteMap<Node,Value> CardMap;
thoneyvazul@1020:   typedef concepts::ReadWriteMap<Node,bool> ProcMap;
thoneyvazul@1020:   typedef Digraph::NodeMap<int> HeapCrossRef;
thoneyvazul@1020: 
thoneyvazul@1020:   Digraph g;
thoneyvazul@1020:   Node n,s;
thoneyvazul@1020:   CapMap cap;
thoneyvazul@1020:   CardMap card;
thoneyvazul@1020:   ProcMap proc;
thoneyvazul@1020:   HeapCrossRef crossref(g);
thoneyvazul@1020:   
thoneyvazul@1020:   typedef MaxCardinalitySearch<Digraph,CapMap>
thoneyvazul@1020:     ::SetCapacityMap<CapMap>
thoneyvazul@1020:     ::SetCardinalityMap<CardMap>
thoneyvazul@1020:     ::SetProcessedMap<ProcMap>
thoneyvazul@1020:     ::SetStandardHeap<BinHeap<Value,HeapCrossRef> >
thoneyvazul@1020:     ::Create MaxCardType;
thoneyvazul@1020: 
thoneyvazul@1020:   MaxCardType maxcard(g,cap);
thoneyvazul@1020:   const MaxCardType& const_maxcard = maxcard;
thoneyvazul@1020: 
thoneyvazul@1020:   const MaxCardType::Heap& heap_const = const_maxcard.heap();
thoneyvazul@1020:   MaxCardType::Heap& heap = const_cast<MaxCardType::Heap&>(heap_const);
thoneyvazul@1020:   maxcard.heap(heap,crossref);
thoneyvazul@1020:   
thoneyvazul@1020:   maxcard.capacityMap(cap).cardinalityMap(card).processedMap(proc);
thoneyvazul@1020: 
thoneyvazul@1020:   maxcard.init();
thoneyvazul@1020:   maxcard.addSource(s);
thoneyvazul@1020:   n = maxcard.nextNode();
thoneyvazul@1020:    maxcard.processNextNode();
thoneyvazul@1020:    maxcard.start();
thoneyvazul@1020:    maxcard.run(s);
thoneyvazul@1020:    maxcard.run();
thoneyvazul@1020:  }
thoneyvazul@1020: 
thoneyvazul@1020:  void checkWithIntMap( std::istringstream& input)
thoneyvazul@1020:  {
thoneyvazul@1020:    typedef SmartDigraph Digraph;
thoneyvazul@1020:    typedef Digraph::Node Node;
thoneyvazul@1020:    typedef Digraph::ArcMap<int> CapMap;
thoneyvazul@1020: 
thoneyvazul@1020:    Digraph g;
thoneyvazul@1020:    Node s,x,y,z,a;
thoneyvazul@1020:    CapMap cap(g);
thoneyvazul@1020: 
thoneyvazul@1020:    DigraphReader<Digraph>(g,input).
thoneyvazul@1020:      arcMap("capacity", cap).
thoneyvazul@1020:      node("s",s).
thoneyvazul@1020:      node("x",x).
thoneyvazul@1020:      node("y",y).
thoneyvazul@1020:      node("z",z).
thoneyvazul@1020:      run();
thoneyvazul@1020: 
thoneyvazul@1020:    MaxCardinalitySearch<Digraph,CapMap> maxcard(g,cap);
thoneyvazul@1020: 
thoneyvazul@1020:    maxcard.init();
thoneyvazul@1020:    maxcard.addSource(s);
thoneyvazul@1020:    maxcard.start(x);
thoneyvazul@1020: 
thoneyvazul@1020:    check(maxcard.processed(s) and !maxcard.processed(x) and
thoneyvazul@1020:          !maxcard.processed(y), "Wrong processed()!");
thoneyvazul@1020: 
thoneyvazul@1020:    a=maxcard.nextNode();
thoneyvazul@1020:    check(maxcard.processNextNode()==a,
thoneyvazul@1020:          "Wrong nextNode() or processNextNode() return value!");
thoneyvazul@1020: 
thoneyvazul@1020:    check(maxcard.processed(a), "Wrong processNextNode()!");
thoneyvazul@1020: 
thoneyvazul@1020:    maxcard.start();
thoneyvazul@1020:    check(maxcard.cardinality(x)==2 and maxcard.cardinality(y)>=4,
thoneyvazul@1020:          "Wrong cardinalities!");
thoneyvazul@1020:  }
thoneyvazul@1020: 
thoneyvazul@1020:  void checkWithConst1Map(std::istringstream &input) {
thoneyvazul@1020:    typedef SmartDigraph Digraph;
thoneyvazul@1020:    typedef Digraph::Node Node;
thoneyvazul@1020: 
thoneyvazul@1020:    Digraph g;
thoneyvazul@1020:    Node s,x,y,z;
thoneyvazul@1020: 
thoneyvazul@1020:   DigraphReader<Digraph>(g,input).
thoneyvazul@1020:     node("s",s).
thoneyvazul@1020:     node("x",x).
thoneyvazul@1020:     node("y",y).
thoneyvazul@1020:     node("z",z).
thoneyvazul@1020:     run();
thoneyvazul@1020: 
thoneyvazul@1020:   MaxCardinalitySearch<Digraph> maxcard(g);
thoneyvazul@1020:   maxcard.run(s);
thoneyvazul@1020:   check(maxcard.cardinality(x)==1 &&
thoneyvazul@1020:         maxcard.cardinality(y)+maxcard.cardinality(z)==3,
thoneyvazul@1020:         "Wrong cardinalities!");
thoneyvazul@1020: }
thoneyvazul@1020: 
thoneyvazul@1020: int main() {
thoneyvazul@1020: 
thoneyvazul@1020:   std::istringstream input1(test_lgf);
thoneyvazul@1020:   checkWithIntMap(input1);
thoneyvazul@1020: 
thoneyvazul@1020:   std::istringstream input2(test_lgf);
thoneyvazul@1020:   checkWithConst1Map(input2);
thoneyvazul@1020: }