COIN-OR::LEMON - Graph Library

source: lemon-main/test/dfs_test.cc @ 282:dc9e8d2c0df9

Last change on this file since 282:dc9e8d2c0df9 was 278:931190050520, checked in by Peter Kovacs <kpeter@…>, 16 years ago

Improve the function-type interface of bfs, dfs, and dijkstra (ticket #96)

File size: 3.7 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-2008
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
60  Digraph G;
61  Digraph::Node n;
62  Digraph::Arc e;
63  int l;
64  bool b;
65  DType::DistMap d(G);
66  DType::PredMap p(G);
67
68  DType dfs_test(G);
69
70  dfs_test.run(n);
71
72  l  = dfs_test.dist(n);
73  e  = dfs_test.predArc(n);
74  n  = dfs_test.predNode(n);
75  d  = dfs_test.distMap();
76  p  = dfs_test.predMap();
77  b  = dfs_test.reached(n);
78
79  Path<Digraph> pp = dfs_test.path(n);
80}
81
82void checkDfsFunctionCompile()
83{
84  typedef int VType;
85  typedef concepts::Digraph Digraph;
86  typedef Digraph::Arc Arc;
87  typedef Digraph::Node Node;
88
89  Digraph g;
90  bool b;
91  dfs(g).run(Node());
92  b=dfs(g).run(Node(),Node());
93  dfs(g).run();
94  dfs(g)
95    .predMap(concepts::ReadWriteMap<Node,Arc>())
96    .distMap(concepts::ReadWriteMap<Node,VType>())
97    .reachedMap(concepts::ReadWriteMap<Node,bool>())
98    .processedMap(concepts::WriteMap<Node,bool>())
99    .run(Node());
100  b=dfs(g)
101    .predMap(concepts::ReadWriteMap<Node,Arc>())
102    .distMap(concepts::ReadWriteMap<Node,VType>())
103    .reachedMap(concepts::ReadWriteMap<Node,bool>())
104    .processedMap(concepts::WriteMap<Node,bool>())
105    .path(concepts::Path<Digraph>())
106    .dist(VType())
107    .run(Node(),Node());
108  dfs(g)
109    .predMap(concepts::ReadWriteMap<Node,Arc>())
110    .distMap(concepts::ReadWriteMap<Node,VType>())
111    .reachedMap(concepts::ReadWriteMap<Node,bool>())
112    .processedMap(concepts::WriteMap<Node,bool>())
113    .run();
114}
115
116template <class Digraph>
117void checkDfs() {
118  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
119
120  Digraph G;
121  Node s, t;
122
123  std::istringstream input(test_lgf);
124  digraphReader(input, G).
125    node("source", s).
126    node("target", t).
127    run();
128
129  Dfs<Digraph> dfs_test(G);
130  dfs_test.run(s);
131
132  Path<Digraph> p = dfs_test.path(t);
133  check(p.length() == dfs_test.dist(t),"path() found a wrong path.");
134  check(checkPath(G, p),"path() found a wrong path.");
135  check(pathSource(G, p) == s,"path() found a wrong path.");
136  check(pathTarget(G, p) == t,"path() found a wrong path.");
137
138  for(NodeIt v(G); v!=INVALID; ++v) {
139    if (dfs_test.reached(v)) {
140      check(v==s || dfs_test.predArc(v)!=INVALID, "Wrong tree.");
141      if (dfs_test.predArc(v)!=INVALID ) {
142        Arc e=dfs_test.predArc(v);
143        Node u=G.source(e);
144        check(u==dfs_test.predNode(v),"Wrong tree.");
145        check(dfs_test.dist(v) - dfs_test.dist(u) == 1,
146              "Wrong distance. (" << dfs_test.dist(u) << "->"
147              << dfs_test.dist(v) << ")");
148      }
149    }
150  }
151
152  {
153    NullMap<Node,Arc> myPredMap;
154    dfs(G).predMap(myPredMap).run(s);
155  }
156}
157
158int main()
159{
160  checkDfs<ListDigraph>();
161  checkDfs<SmartDigraph>();
162  return 0;
163}
Note: See TracBrowser for help on using the repository browser.