COIN-OR::LEMON - Graph Library

source: lemon-1.2/test/dfs_test.cc @ 681:532697c9fa53

Last change on this file since 681:532697c9fa53 was 585:65fbcf2f978a, checked in by Peter Kovacs <kpeter@…>, 11 years ago

Improve test files for some algorithms (#263)

File size: 5.3 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-2009
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 <lemon/concepts/digraph.h>
20#include <lemon/smart_graph.h>
21#include <lemon/list_graph.h>
22#include <lemon/lgf_reader.h>
23#include <lemon/dfs.h>
24#include <lemon/path.h>
25
26#include "graph_test.h"
27#include "test_tools.h"
28
29using namespace lemon;
30
31char test_lgf[] =
32  "@nodes\n"
33  "label\n"
34  "0\n"
35  "1\n"
36  "2\n"
37  "3\n"
38  "4\n"
39  "5\n"
40  "6\n"
41  "@arcs\n"
42  "     label\n"
43  "0 1  0\n"
44  "1 2  1\n"
45  "2 3  2\n"
46  "1 4  3\n"
47  "4 2  4\n"
48  "4 5  5\n"
49  "5 0  6\n"
50  "6 3  7\n"
51  "@attributes\n"
52  "source 0\n"
53  "target 5\n";
54
55void checkDfsCompile()
56{
57  typedef concepts::Digraph Digraph;
58  typedef Dfs<Digraph> DType;
59  typedef Digraph::Node Node;
60  typedef Digraph::Arc Arc;
61
62  Digraph G;
63  Node s, t;
64  Arc e;
65  int l, i;
66  bool b;
67  DType::DistMap d(G);
68  DType::PredMap p(G);
69  Path<Digraph> pp;
70  concepts::ReadMap<Arc,bool> am;
71
72  {
73    DType dfs_test(G);
74    const DType& const_dfs_test = dfs_test;
75
76    dfs_test.run(s);
77    dfs_test.run(s,t);
78    dfs_test.run();
79
80    dfs_test.init();
81    dfs_test.addSource(s);
82    e = dfs_test.processNextArc();
83    e = const_dfs_test.nextArc();
84    b = const_dfs_test.emptyQueue();
85    i = const_dfs_test.queueSize();
86   
87    dfs_test.start();
88    dfs_test.start(t);
89    dfs_test.start(am);
90
91    l  = const_dfs_test.dist(t);
92    e  = const_dfs_test.predArc(t);
93    s  = const_dfs_test.predNode(t);
94    b  = const_dfs_test.reached(t);
95    d  = const_dfs_test.distMap();
96    p  = const_dfs_test.predMap();
97    pp = const_dfs_test.path(t);
98  }
99  {
100    DType
101      ::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
102      ::SetDistMap<concepts::ReadWriteMap<Node,int> >
103      ::SetReachedMap<concepts::ReadWriteMap<Node,bool> >
104      ::SetStandardProcessedMap
105      ::SetProcessedMap<concepts::WriteMap<Node,bool> >
106      ::Create dfs_test(G);
107
108    concepts::ReadWriteMap<Node,Arc> pred_map;
109    concepts::ReadWriteMap<Node,int> dist_map;
110    concepts::ReadWriteMap<Node,bool> reached_map;
111    concepts::WriteMap<Node,bool> processed_map;
112   
113    dfs_test
114      .predMap(pred_map)
115      .distMap(dist_map)
116      .reachedMap(reached_map)
117      .processedMap(processed_map);
118
119    dfs_test.run(s);
120    dfs_test.run(s,t);
121    dfs_test.run();
122    dfs_test.init();
123
124    dfs_test.addSource(s);
125    e = dfs_test.processNextArc();
126    e = dfs_test.nextArc();
127    b = dfs_test.emptyQueue();
128    i = dfs_test.queueSize();
129   
130    dfs_test.start();
131    dfs_test.start(t);
132    dfs_test.start(am);
133
134    l  = dfs_test.dist(t);
135    e  = dfs_test.predArc(t);
136    s  = dfs_test.predNode(t);
137    b  = dfs_test.reached(t);
138    pp = dfs_test.path(t);
139  }
140}
141
142void checkDfsFunctionCompile()
143{
144  typedef int VType;
145  typedef concepts::Digraph Digraph;
146  typedef Digraph::Arc Arc;
147  typedef Digraph::Node Node;
148
149  Digraph g;
150  bool b;
151  dfs(g).run(Node());
152  b=dfs(g).run(Node(),Node());
153  dfs(g).run();
154  dfs(g)
155    .predMap(concepts::ReadWriteMap<Node,Arc>())
156    .distMap(concepts::ReadWriteMap<Node,VType>())
157    .reachedMap(concepts::ReadWriteMap<Node,bool>())
158    .processedMap(concepts::WriteMap<Node,bool>())
159    .run(Node());
160  b=dfs(g)
161    .predMap(concepts::ReadWriteMap<Node,Arc>())
162    .distMap(concepts::ReadWriteMap<Node,VType>())
163    .reachedMap(concepts::ReadWriteMap<Node,bool>())
164    .processedMap(concepts::WriteMap<Node,bool>())
165    .path(concepts::Path<Digraph>())
166    .dist(VType())
167    .run(Node(),Node());
168  dfs(g)
169    .predMap(concepts::ReadWriteMap<Node,Arc>())
170    .distMap(concepts::ReadWriteMap<Node,VType>())
171    .reachedMap(concepts::ReadWriteMap<Node,bool>())
172    .processedMap(concepts::WriteMap<Node,bool>())
173    .run();
174}
175
176template <class Digraph>
177void checkDfs() {
178  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
179
180  Digraph G;
181  Node s, t;
182
183  std::istringstream input(test_lgf);
184  digraphReader(G, input).
185    node("source", s).
186    node("target", t).
187    run();
188
189  Dfs<Digraph> dfs_test(G);
190  dfs_test.run(s);
191
192  Path<Digraph> p = dfs_test.path(t);
193  check(p.length() == dfs_test.dist(t),"path() found a wrong path.");
194  check(checkPath(G, p),"path() found a wrong path.");
195  check(pathSource(G, p) == s,"path() found a wrong path.");
196  check(pathTarget(G, p) == t,"path() found a wrong path.");
197
198  for(NodeIt v(G); v!=INVALID; ++v) {
199    if (dfs_test.reached(v)) {
200      check(v==s || dfs_test.predArc(v)!=INVALID, "Wrong tree.");
201      if (dfs_test.predArc(v)!=INVALID ) {
202        Arc e=dfs_test.predArc(v);
203        Node u=G.source(e);
204        check(u==dfs_test.predNode(v),"Wrong tree.");
205        check(dfs_test.dist(v) - dfs_test.dist(u) == 1,
206              "Wrong distance. (" << dfs_test.dist(u) << "->"
207              << dfs_test.dist(v) << ")");
208      }
209    }
210  }
211
212  {
213    NullMap<Node,Arc> myPredMap;
214    dfs(G).predMap(myPredMap).run(s);
215  }
216}
217
218int main()
219{
220  checkDfs<ListDigraph>();
221  checkDfs<SmartDigraph>();
222  return 0;
223}
Note: See TracBrowser for help on using the repository browser.