COIN-OR::LEMON - Graph Library

source: lemon/test/euler_test.cc @ 1109:fe5718b39fda

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

Unify sources

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