COIN-OR::LEMON - Graph Library

source: lemon/test/dfs_test.cc @ 930:5df6a8f29d5e

Last change on this file since 930:5df6a8f29d5e was 632:65fbcf2f978a, checked in by Peter Kovacs <kpeter@…>, 11 years ago

Improve test files for some algorithms (#263)

File size: 5.3 KB
RevLine 
[209]1/* -*- mode: C++; indent-tabs-mode: nil; -*-
[100]2 *
[209]3 * This file is a part of LEMON, a generic C++ optimization library.
[100]4 *
[463]5 * Copyright (C) 2003-2009
[100]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
[171]19#include <lemon/concepts/digraph.h>
20#include <lemon/smart_graph.h>
[100]21#include <lemon/list_graph.h>
[228]22#include <lemon/lgf_reader.h>
[100]23#include <lemon/dfs.h>
24#include <lemon/path.h>
[171]25
26#include "graph_test.h"
27#include "test_tools.h"
[100]28
29using namespace lemon;
30
[228]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
[209]55void checkDfsCompile()
[100]56{
57  typedef concepts::Digraph Digraph;
58  typedef Dfs<Digraph> DType;
[286]59  typedef Digraph::Node Node;
60  typedef Digraph::Arc Arc;
[209]61
[100]62  Digraph G;
[286]63  Node s, t;
64  Arc e;
[632]65  int l, i;
[100]66  bool b;
67  DType::DistMap d(G);
68  DType::PredMap p(G);
[286]69  Path<Digraph> pp;
[632]70  concepts::ReadMap<Arc,bool> am;
[209]71
[286]72  {
73    DType dfs_test(G);
[632]74    const DType& const_dfs_test = dfs_test;
[209]75
[286]76    dfs_test.run(s);
77    dfs_test.run(s,t);
78    dfs_test.run();
[209]79
[632]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);
[286]98  }
99  {
100    DType
101      ::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
102      ::SetDistMap<concepts::ReadWriteMap<Node,int> >
103      ::SetReachedMap<concepts::ReadWriteMap<Node,bool> >
[632]104      ::SetStandardProcessedMap
[286]105      ::SetProcessedMap<concepts::WriteMap<Node,bool> >
106      ::Create dfs_test(G);
[100]107
[632]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
[286]119    dfs_test.run(s);
120    dfs_test.run(s,t);
121    dfs_test.run();
[632]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);
[286]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  }
[100]140}
141
[209]142void checkDfsFunctionCompile()
[100]143{
144  typedef int VType;
145  typedef concepts::Digraph Digraph;
146  typedef Digraph::Arc Arc;
147  typedef Digraph::Node Node;
[209]148
[100]149  Digraph g;
[278]150  bool b;
151  dfs(g).run(Node());
152  b=dfs(g).run(Node(),Node());
153  dfs(g).run();
[100]154  dfs(g)
[278]155    .predMap(concepts::ReadWriteMap<Node,Arc>())
156    .distMap(concepts::ReadWriteMap<Node,VType>())
[100]157    .reachedMap(concepts::ReadWriteMap<Node,bool>())
158    .processedMap(concepts::WriteMap<Node,bool>())
[209]159    .run(Node());
[278]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();
[100]174}
175
[171]176template <class Digraph>
177void checkDfs() {
178  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
[100]179
180  Digraph G;
181  Node s, t;
[209]182
[228]183  std::istringstream input(test_lgf);
[293]184  digraphReader(G, input).
[228]185    node("source", s).
186    node("target", t).
187    run();
[209]188
[100]189  Dfs<Digraph> dfs_test(G);
[209]190  dfs_test.run(s);
191
[100]192  Path<Digraph> p = dfs_test.path(t);
[171]193  check(p.length() == dfs_test.dist(t),"path() found a wrong path.");
[100]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.");
[209]197
[100]198  for(NodeIt v(G); v!=INVALID; ++v) {
[228]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) << "->"
[278]207              << dfs_test.dist(v) << ")");
[228]208      }
[100]209    }
210  }
[278]211
212  {
213    NullMap<Node,Arc> myPredMap;
214    dfs(G).predMap(myPredMap).run(s);
215  }
[100]216}
217
[171]218int main()
219{
220  checkDfs<ListDigraph>();
221  checkDfs<SmartDigraph>();
222  return 0;
223}
Note: See TracBrowser for help on using the repository browser.