COIN-OR::LEMON - Graph Library

source: lemon/test/euler_test.cc @ 1229:473c71baff72

Last change on this file since 1229:473c71baff72 was 1159:7fdaa05a69a1, checked in by Alpar Juttner <alpar@…>, 12 years ago

Merge #449 to branches >=1.2

File size: 5.4 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-2010
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/euler.h>
20#include <lemon/list_graph.h>
21#include <lemon/adaptors.h>
22#include "test_tools.h"
23
24using namespace lemon;
25
26template <typename Digraph>
27void checkDiEulerIt(const Digraph& g,
28                    const typename Digraph::Node& start = INVALID)
29{
30  typename Digraph::template ArcMap<int> visitationNumber(g, 0);
31
32  DiEulerIt<Digraph> e(g, start);
33  if (e == INVALID) return;
34  typename Digraph::Node firstNode = g.source(e);
35  typename Digraph::Node lastNode = g.target(e);
36  if (start != INVALID) {
37    check(firstNode == start, "checkDiEulerIt: Wrong first node");
38  }
39
40  for (; e != INVALID; ++e) {
41    if (e != INVALID) lastNode = g.target(e);
42    ++visitationNumber[e];
43  }
44
45  check(firstNode == lastNode,
46      "checkDiEulerIt: First and last nodes are not the same");
47
48  for (typename Digraph::ArcIt a(g); a != INVALID; ++a)
49  {
50    check(visitationNumber[a] == 1,
51        "checkDiEulerIt: Not visited or multiple times visited arc found");
52  }
53}
54
55template <typename Graph>
56void checkEulerIt(const Graph& g,
57                  const typename Graph::Node& start = INVALID)
58{
59  typename Graph::template EdgeMap<int> visitationNumber(g, 0);
60
61  EulerIt<Graph> e(g, start);
62  if (e == INVALID) return;
63  typename Graph::Node firstNode = g.source(typename Graph::Arc(e));
64  typename Graph::Node lastNode = g.target(typename Graph::Arc(e));
65  if (start != INVALID) {
66    check(firstNode == start, "checkEulerIt: Wrong first node");
67  }
68
69  for (; e != INVALID; ++e) {
70    if (e != INVALID) lastNode = g.target(typename Graph::Arc(e));
71    ++visitationNumber[e];
72  }
73
74  check(firstNode == lastNode,
75      "checkEulerIt: First and last nodes are not the same");
76
77  for (typename Graph::EdgeIt e(g); e != INVALID; ++e)
78  {
79    check(visitationNumber[e] == 1,
80        "checkEulerIt: Not visited or multiple times visited edge found");
81  }
82}
83
84int main()
85{
86  typedef ListDigraph Digraph;
87  typedef Undirector<Digraph> Graph;
88
89  {
90    Digraph d;
91    Graph g(d);
92
93    checkDiEulerIt(d);
94    checkDiEulerIt(g);
95    checkEulerIt(g);
96
97    check(eulerian(d), "This graph is Eulerian");
98    check(eulerian(g), "This graph is Eulerian");
99  }
100  {
101    Digraph d;
102    Graph g(d);
103    Digraph::Node n = d.addNode();
104    ignore_unused_variable_warning(n);
105 
106    checkDiEulerIt(d);
107    checkDiEulerIt(g);
108    checkEulerIt(g);
109
110    check(eulerian(d), "This graph is Eulerian");
111    check(eulerian(g), "This graph is Eulerian");
112  }
113  {
114    Digraph d;
115    Graph g(d);
116    Digraph::Node n = d.addNode();
117    d.addArc(n, n);
118
119    checkDiEulerIt(d);
120    checkDiEulerIt(g);
121    checkEulerIt(g);
122
123    check(eulerian(d), "This graph is Eulerian");
124    check(eulerian(g), "This graph is Eulerian");
125  }
126  {
127    Digraph d;
128    Graph g(d);
129    Digraph::Node n1 = d.addNode();
130    Digraph::Node n2 = d.addNode();
131    Digraph::Node n3 = d.addNode();
132
133    d.addArc(n1, n2);
134    d.addArc(n2, n1);
135    d.addArc(n2, n3);
136    d.addArc(n3, n2);
137
138    checkDiEulerIt(d);
139    checkDiEulerIt(d, n2);
140    checkDiEulerIt(g);
141    checkDiEulerIt(g, n2);
142    checkEulerIt(g);
143    checkEulerIt(g, n2);
144
145    check(eulerian(d), "This graph is Eulerian");
146    check(eulerian(g), "This graph is Eulerian");
147  }
148  {
149    Digraph d;
150    Graph g(d);
151    Digraph::Node n1 = d.addNode();
152    Digraph::Node n2 = d.addNode();
153    Digraph::Node n3 = d.addNode();
154    Digraph::Node n4 = d.addNode();
155    Digraph::Node n5 = d.addNode();
156    Digraph::Node n6 = d.addNode();
157
158    d.addArc(n1, n2);
159    d.addArc(n2, n4);
160    d.addArc(n1, n3);
161    d.addArc(n3, n4);
162    d.addArc(n4, n1);
163    d.addArc(n3, n5);
164    d.addArc(n5, n2);
165    d.addArc(n4, n6);
166    d.addArc(n2, n6);
167    d.addArc(n6, n1);
168    d.addArc(n6, n3);
169
170    checkDiEulerIt(d);
171    checkDiEulerIt(d, n1);
172    checkDiEulerIt(d, n5);
173
174    checkDiEulerIt(g);
175    checkDiEulerIt(g, n1);
176    checkDiEulerIt(g, n5);
177    checkEulerIt(g);
178    checkEulerIt(g, n1);
179    checkEulerIt(g, n5);
180
181    check(eulerian(d), "This graph is Eulerian");
182    check(eulerian(g), "This graph is Eulerian");
183  }
184  {
185    Digraph d;
186    Graph g(d);
187    Digraph::Node n0 = d.addNode();
188    Digraph::Node n1 = d.addNode();
189    Digraph::Node n2 = d.addNode();
190    Digraph::Node n3 = d.addNode();
191    Digraph::Node n4 = d.addNode();
192    Digraph::Node n5 = d.addNode();
193    ignore_unused_variable_warning(n0,n4,n5);
194
195    d.addArc(n1, n2);
196    d.addArc(n2, n3);
197    d.addArc(n3, n1);
198
199    checkDiEulerIt(d);
200    checkDiEulerIt(d, n2);
201
202    checkDiEulerIt(g);
203    checkDiEulerIt(g, n2);
204    checkEulerIt(g);
205    checkEulerIt(g, n2);
206
207    check(!eulerian(d), "This graph is not Eulerian");
208    check(!eulerian(g), "This graph is not Eulerian");
209  }
210  {
211    Digraph d;
212    Graph g(d);
213    Digraph::Node n1 = d.addNode();
214    Digraph::Node n2 = d.addNode();
215    Digraph::Node n3 = d.addNode();
216
217    d.addArc(n1, n2);
218    d.addArc(n2, n3);
219
220    check(!eulerian(d), "This graph is not Eulerian");
221    check(!eulerian(g), "This graph is not Eulerian");
222  }
223
224  return 0;
225}
Note: See TracBrowser for help on using the repository browser.