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 <lemon/euler.h>
20 #include <lemon/list_graph.h>
21 #include <lemon/adaptors.h>
22 #include "test_tools.h"
23
24 using namespace lemon;
25
26 template <typename Digraph>
checkDiEulerIt(const Digraph & g,const typename Digraph::Node & start=INVALID)27 void 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
55 template <typename Graph>
checkEulerIt(const Graph & g,const typename Graph::Node & start=INVALID)56 void 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
main()84 int 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 ::lemon::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 ::lemon::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 }
226