COIN-OR::LEMON - Graph Library

source: lemon-main/test/max_cardinality_search_test.cc @ 1163:db1d342a1087

Last change on this file since 1163:db1d342a1087 was 1092:dceba191c00d, checked in by Alpar Juttner <alpar@…>, 11 years ago

Apply unify-sources.sh to the source tree

File size: 3.8 KB
Line 
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-2013
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
29using namespace lemon;
30using namespace std;
31
32char 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
53void 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) && !maxcard.processed(x) &&
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 && 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
155int main() {
156
157  std::istringstream input1(test_lgf);
158  checkWithIntMap(input1);
159
160  std::istringstream input2(test_lgf);
161  checkWithConst1Map(input2);
162}
Note: See TracBrowser for help on using the repository browser.