COIN-OR::LEMON - Graph Library

source: lemon/test/euler_test.cc @ 1126:a30455cd0107

1.1 r1.1.4
Last change on this file since 1126:a30455cd0107 was 1081:f1398882a928, checked in by Alpar Juttner <alpar@…>, 13 years ago

Unify sources

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-2011
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
105    checkDiEulerIt(d);
106    checkDiEulerIt(g);
107    checkEulerIt(g);
108
109    check(eulerian(d), "This graph is Eulerian");
110    check(eulerian(g), "This graph is Eulerian");
111  }
112  {
113    Digraph d;
114    Graph g(d);
115    Digraph::Node n = d.addNode();
116    d.addArc(n, n);
117
118    checkDiEulerIt(d);
119    checkDiEulerIt(g);
120    checkEulerIt(g);
121
122    check(eulerian(d), "This graph is Eulerian");
123    check(eulerian(g), "This graph is Eulerian");
124  }
125  {
126    Digraph d;
127    Graph g(d);
128    Digraph::Node n1 = d.addNode();
129    Digraph::Node n2 = d.addNode();
130    Digraph::Node n3 = d.addNode();
131
132    d.addArc(n1, n2);
133    d.addArc(n2, n1);
134    d.addArc(n2, n3);
135    d.addArc(n3, n2);
136
137    checkDiEulerIt(d);
138    checkDiEulerIt(d, n2);
139    checkDiEulerIt(g);
140    checkDiEulerIt(g, n2);
141    checkEulerIt(g);
142    checkEulerIt(g, n2);
143
144    check(eulerian(d), "This graph is Eulerian");
145    check(eulerian(g), "This graph is Eulerian");
146  }
147  {
148    Digraph d;
149    Graph g(d);
150    Digraph::Node n1 = d.addNode();
151    Digraph::Node n2 = d.addNode();
152    Digraph::Node n3 = d.addNode();
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  }
221
222  return 0;
223}
Note: See TracBrowser for help on using the repository browser.