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