COIN-OR::LEMON - Graph Library

source: lemon-1.2/test/euler_test.cc @ 619:ec817dfc2cb7

Last change on this file since 619:ec817dfc2cb7 was 592:2ebfdb89ec66, checked in by Peter Kovacs <kpeter@…>, 11 years ago

Improvements for the Euler tools and the test file (#264)

File size: 5.4 KB
RevLine 
[522]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-2009
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>
[592]21#include <lemon/adaptors.h>
22#include "test_tools.h"
[522]23
24using namespace lemon;
25
26template <typename Digraph>
[592]27void checkDiEulerIt(const Digraph& g,
28                    const typename Digraph::Node& start = INVALID)
[522]29{
[531]30  typename Digraph::template ArcMap<int> visitationNumber(g, 0);
[522]31
[592]32  DiEulerIt<Digraph> e(g, start);
33  if (e == INVALID) return;
[522]34  typename Digraph::Node firstNode = g.source(e);
[531]35  typename Digraph::Node lastNode = g.target(e);
[592]36  if (start != INVALID) {
37    check(firstNode == start, "checkDiEulerIt: Wrong first node");
38  }
[522]39
[592]40  for (; e != INVALID; ++e) {
41    if (e != INVALID) lastNode = g.target(e);
[522]42    ++visitationNumber[e];
43  }
44
45  check(firstNode == lastNode,
[592]46      "checkDiEulerIt: First and last nodes are not the same");
[522]47
48  for (typename Digraph::ArcIt a(g); a != INVALID; ++a)
49  {
50    check(visitationNumber[a] == 1,
[592]51        "checkDiEulerIt: Not visited or multiple times visited arc found");
[522]52  }
53}
54
55template <typename Graph>
[592]56void checkEulerIt(const Graph& g,
57                  const typename Graph::Node& start = INVALID)
[522]58{
[531]59  typename Graph::template EdgeMap<int> visitationNumber(g, 0);
[522]60
[592]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  }
[522]68
[592]69  for (; e != INVALID; ++e) {
70    if (e != INVALID) lastNode = g.target(typename Graph::Arc(e));
[522]71    ++visitationNumber[e];
72  }
73
74  check(firstNode == lastNode,
[592]75      "checkEulerIt: First and last nodes are not the same");
[522]76
77  for (typename Graph::EdgeIt e(g); e != INVALID; ++e)
78  {
79    check(visitationNumber[e] == 1,
[592]80        "checkEulerIt: Not visited or multiple times visited edge found");
[522]81  }
82}
83
84int main()
85{
86  typedef ListDigraph Digraph;
[592]87  typedef Undirector<Digraph> Graph;
88 
89  {
90    Digraph d;
91    Graph g(d);
92   
93    checkDiEulerIt(d);
94    checkDiEulerIt(g);
95    checkEulerIt(g);
[522]96
[592]97    check(eulerian(d), "This graph is Eulerian");
98    check(eulerian(g), "This graph is Eulerian");
99  }
[522]100  {
[592]101    Digraph d;
102    Graph g(d);
103    Digraph::Node n = d.addNode();
[522]104
[592]105    checkDiEulerIt(d);
106    checkDiEulerIt(g);
107    checkEulerIt(g);
[522]108
[592]109    check(eulerian(d), "This graph is Eulerian");
110    check(eulerian(g), "This graph is Eulerian");
[522]111  }
[592]112  {
113    Digraph d;
114    Graph g(d);
115    Digraph::Node n = d.addNode();
116    d.addArc(n, n);
[522]117
[592]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  }
[522]125  {
[592]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);
[522]136
[592]137    checkDiEulerIt(d);
138    checkDiEulerIt(d, n2);
139    checkDiEulerIt(g);
140    checkDiEulerIt(g, n2);
141    checkEulerIt(g);
142    checkEulerIt(g, n2);
[522]143
[592]144    check(eulerian(d), "This graph is Eulerian");
145    check(eulerian(g), "This graph is Eulerian");
[522]146  }
[592]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);
[522]168
[592]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  }
[522]183  {
[592]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);
[522]196
[592]197    checkDiEulerIt(d);
198    checkDiEulerIt(d, n2);
[522]199
[592]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");
[522]207  }
[592]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);
[522]217
[592]218    check(!eulerian(d), "This graph is not Eulerian");
219    check(!eulerian(g), "This graph is not Eulerian");
[522]220  }
221
222  return 0;
223}
Note: See TracBrowser for help on using the repository browser.