COIN-OR::LEMON - Graph Library

source: lemon-1.2/test/euler_test.cc @ 558:f53d641aa967

Last change on this file since 558:f53d641aa967 was 531:ba7bafdc458d, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Avoid warnings in test/euler_test.h (#65)

File size: 3.6 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-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>
21#include <test/test_tools.h>
22
23using namespace lemon;
24
25template <typename Digraph>
26void checkDiEulerIt(const Digraph& g)
27{
28  typename Digraph::template ArcMap<int> visitationNumber(g, 0);
29
30  DiEulerIt<Digraph> e(g);
31  typename Digraph::Node firstNode = g.source(e);
32  typename Digraph::Node lastNode = g.target(e);
33
34  for (; e != INVALID; ++e)
35  {
36    if (e != INVALID)
37    {
38      lastNode = g.target(e);
39    }
40    ++visitationNumber[e];
41  }
42
43  check(firstNode == lastNode,
44      "checkDiEulerIt: first and last node are not the same");
45
46  for (typename Digraph::ArcIt a(g); a != INVALID; ++a)
47  {
48    check(visitationNumber[a] == 1,
49        "checkDiEulerIt: not visited or multiple times visited arc found");
50  }
51}
52
53template <typename Graph>
54void checkEulerIt(const Graph& g)
55{
56  typename Graph::template EdgeMap<int> visitationNumber(g, 0);
57
58  EulerIt<Graph> e(g);
59  typename Graph::Node firstNode = g.u(e);
60  typename Graph::Node lastNode = g.v(e);
61
62  for (; e != INVALID; ++e)
63  {
64    if (e != INVALID)
65    {
66      lastNode = g.v(e);
67    }
68    ++visitationNumber[e];
69  }
70
71  check(firstNode == lastNode,
72      "checkEulerIt: first and last node are not the same");
73
74  for (typename Graph::EdgeIt e(g); e != INVALID; ++e)
75  {
76    check(visitationNumber[e] == 1,
77        "checkEulerIt: not visited or multiple times visited edge found");
78  }
79}
80
81int main()
82{
83  typedef ListDigraph Digraph;
84  typedef ListGraph Graph;
85
86  Digraph digraphWithEulerianCircuit;
87  {
88    Digraph& g = digraphWithEulerianCircuit;
89
90    Digraph::Node n0 = g.addNode();
91    Digraph::Node n1 = g.addNode();
92    Digraph::Node n2 = g.addNode();
93
94    g.addArc(n0, n1);
95    g.addArc(n1, n0);
96    g.addArc(n1, n2);
97    g.addArc(n2, n1);
98  }
99
100  Digraph digraphWithoutEulerianCircuit;
101  {
102    Digraph& g = digraphWithoutEulerianCircuit;
103
104    Digraph::Node n0 = g.addNode();
105    Digraph::Node n1 = g.addNode();
106    Digraph::Node n2 = g.addNode();
107
108    g.addArc(n0, n1);
109    g.addArc(n1, n0);
110    g.addArc(n1, n2);
111  }
112
113  Graph graphWithEulerianCircuit;
114  {
115    Graph& g = graphWithEulerianCircuit;
116
117    Graph::Node n0 = g.addNode();
118    Graph::Node n1 = g.addNode();
119    Graph::Node n2 = g.addNode();
120
121    g.addEdge(n0, n1);
122    g.addEdge(n1, n2);
123    g.addEdge(n2, n0);
124  }
125
126  Graph graphWithoutEulerianCircuit;
127  {
128    Graph& g = graphWithoutEulerianCircuit;
129
130    Graph::Node n0 = g.addNode();
131    Graph::Node n1 = g.addNode();
132    Graph::Node n2 = g.addNode();
133
134    g.addEdge(n0, n1);
135    g.addEdge(n1, n2);
136  }
137
138  checkDiEulerIt(digraphWithEulerianCircuit);
139
140  checkEulerIt(graphWithEulerianCircuit);
141
142  check(eulerian(digraphWithEulerianCircuit),
143      "this graph should have an Eulerian circuit");
144  check(!eulerian(digraphWithoutEulerianCircuit),
145      "this graph should not have an Eulerian circuit");
146
147  check(eulerian(graphWithEulerianCircuit),
148      "this graph should have an Eulerian circuit");
149  check(!eulerian(graphWithoutEulerianCircuit),
150      "this graph should have an Eulerian circuit");
151
152  return 0;
153}
Note: See TracBrowser for help on using the repository browser.