r522:22f932bbb305
Mon, 03 Nov 2008 12:59:54
[Not Reviewed]
0 comments (0 inline)
0
4
1
| 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 |
|
|
| 23 |
using namespace lemon; |
|
| 24 |
|
|
| 25 |
template <typename Digraph> |
|
| 26 |
void checkDiEulerIt(const Digraph& g) |
|
| 27 |
{
|
|
| 28 |
typename Digraph::template ArcMap<int> visitationNumber(g); |
|
| 29 |
|
|
| 30 |
DiEulerIt<Digraph> e(g); |
|
| 31 |
typename Digraph::Node firstNode = g.source(e); |
|
| 32 |
typename Digraph::Node lastNode; |
|
| 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 |
|
|
| 53 |
template <typename Graph> |
|
| 54 |
void checkEulerIt(const Graph& g) |
|
| 55 |
{
|
|
| 56 |
typename Graph::template EdgeMap<int> visitationNumber(g); |
|
| 57 |
|
|
| 58 |
EulerIt<Graph> e(g); |
|
| 59 |
typename Graph::Node firstNode = g.u(e); |
|
| 60 |
typename Graph::Node lastNode; |
|
| 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 |
|
|
| 81 |
int 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 |
} |
| ... | ... |
@@ -49,16 +49,17 @@ |
| 49 | 49 |
lemon/arg_parser.h \ |
| 50 | 50 |
lemon/assert.h \ |
| 51 | 51 |
lemon/bfs.h \ |
| 52 | 52 |
lemon/bin_heap.h \ |
| 53 | 53 |
lemon/circulation.h \ |
| 54 | 54 |
lemon/clp.h \ |
| 55 | 55 |
lemon/color.h \ |
| 56 | 56 |
lemon/concept_check.h \ |
| 57 |
lemon/connectivity.h \ |
|
| 57 | 58 |
lemon/counter.h \ |
| 58 | 59 |
lemon/core.h \ |
| 59 | 60 |
lemon/cplex.h \ |
| 60 | 61 |
lemon/dfs.h \ |
| 61 | 62 |
lemon/dijkstra.h \ |
| 62 | 63 |
lemon/dim2.h \ |
| 63 | 64 |
lemon/dimacs.h \ |
| 64 | 65 |
lemon/edge_set.h \ |
| ... | ... |
@@ -49,17 +49,16 @@ |
| 49 | 49 |
///Euler tour of \c g. |
| 50 | 50 |
///\code |
| 51 | 51 |
/// std::vector<ListDigraph::Arc> et; |
| 52 | 52 |
/// for(DiEulerIt<ListDigraph> e(g),e!=INVALID;++e) |
| 53 | 53 |
/// et.push_back(e); |
| 54 | 54 |
///\endcode |
| 55 | 55 |
///If \c g is not Euler then the resulted tour will not be full or closed. |
| 56 | 56 |
///\sa EulerIt |
| 57 |
///\todo Test required |
|
| 58 | 57 |
template<class Digraph> |
| 59 | 58 |
class DiEulerIt |
| 60 | 59 |
{
|
| 61 | 60 |
typedef typename Digraph::Node Node; |
| 62 | 61 |
typedef typename Digraph::NodeIt NodeIt; |
| 63 | 62 |
typedef typename Digraph::Arc Arc; |
| 64 | 63 |
typedef typename Digraph::ArcIt ArcIt; |
| 65 | 64 |
typedef typename Digraph::OutArcIt OutArcIt; |
| ... | ... |
@@ -141,17 +140,16 @@ |
| 141 | 140 |
/// } |
| 142 | 141 |
///\endcode |
| 143 | 142 |
///Although the iterator provides an Euler tour of an graph, |
| 144 | 143 |
///it still returns Arcs in order to indicate the direction of the tour. |
| 145 | 144 |
///(But Arc will convert to Edges, of course). |
| 146 | 145 |
/// |
| 147 | 146 |
///If \c g is not Euler then the resulted tour will not be full or closed. |
| 148 | 147 |
///\sa EulerIt |
| 149 |
///\todo Test required |
|
| 150 | 148 |
template<class Digraph> |
| 151 | 149 |
class EulerIt |
| 152 | 150 |
{
|
| 153 | 151 |
typedef typename Digraph::Node Node; |
| 154 | 152 |
typedef typename Digraph::NodeIt NodeIt; |
| 155 | 153 |
typedef typename Digraph::Arc Arc; |
| 156 | 154 |
typedef typename Digraph::Edge Edge; |
| 157 | 155 |
typedef typename Digraph::ArcIt ArcIt; |
| ... | ... |
@@ -235,17 +233,16 @@ |
| 235 | 233 |
///graphs. |
| 236 | 234 |
///\note By definition, a digraph is called \e Eulerian if |
| 237 | 235 |
///and only if it is connected and the number of its incoming and outgoing |
| 238 | 236 |
///arcs are the same for each node. |
| 239 | 237 |
///Similarly, an undirected graph is called \e Eulerian if |
| 240 | 238 |
///and only if it is connected and the number of incident arcs is even |
| 241 | 239 |
///for each node. <em>Therefore, there are digraphs which are not Eulerian, |
| 242 | 240 |
///but still have an Euler tour</em>. |
| 243 |
///\todo Test required |
|
| 244 | 241 |
template<class Digraph> |
| 245 | 242 |
#ifdef DOXYGEN |
| 246 | 243 |
bool |
| 247 | 244 |
#else |
| 248 | 245 |
typename enable_if<UndirectedTagIndicator<Digraph>,bool>::type |
| 249 | 246 |
eulerian(const Digraph &g) |
| 250 | 247 |
{
|
| 251 | 248 |
for(typename Digraph::NodeIt n(g);n!=INVALID;++n) |
| ... | ... |
@@ -15,16 +15,17 @@ |
| 15 | 15 |
circulation_test |
| 16 | 16 |
counter_test |
| 17 | 17 |
dfs_test |
| 18 | 18 |
digraph_test |
| 19 | 19 |
dijkstra_test |
| 20 | 20 |
dim_test |
| 21 | 21 |
edge_set_test |
| 22 | 22 |
error_test |
| 23 |
euler_test |
|
| 23 | 24 |
graph_copy_test |
| 24 | 25 |
graph_test |
| 25 | 26 |
graph_utils_test |
| 26 | 27 |
hao_orlin_test |
| 27 | 28 |
heap_test |
| 28 | 29 |
kruskal_test |
| 29 | 30 |
maps_test |
| 30 | 31 |
max_matching_test |
| ... | ... |
@@ -11,16 +11,17 @@ |
| 11 | 11 |
test/circulation_test \ |
| 12 | 12 |
test/counter_test \ |
| 13 | 13 |
test/dfs_test \ |
| 14 | 14 |
test/digraph_test \ |
| 15 | 15 |
test/dijkstra_test \ |
| 16 | 16 |
test/dim_test \ |
| 17 | 17 |
test/edge_set_test \ |
| 18 | 18 |
test/error_test \ |
| 19 |
test/euler_test \ |
|
| 19 | 20 |
test/graph_copy_test \ |
| 20 | 21 |
test/graph_test \ |
| 21 | 22 |
test/graph_utils_test \ |
| 22 | 23 |
test/hao_orlin_test \ |
| 23 | 24 |
test/heap_test \ |
| 24 | 25 |
test/kruskal_test \ |
| 25 | 26 |
test/maps_test \ |
| 26 | 27 |
test/max_matching_test \ |
| ... | ... |
@@ -49,16 +50,17 @@ |
| 49 | 50 |
test_circulation_test_SOURCES = test/circulation_test.cc |
| 50 | 51 |
test_counter_test_SOURCES = test/counter_test.cc |
| 51 | 52 |
test_dfs_test_SOURCES = test/dfs_test.cc |
| 52 | 53 |
test_digraph_test_SOURCES = test/digraph_test.cc |
| 53 | 54 |
test_dijkstra_test_SOURCES = test/dijkstra_test.cc |
| 54 | 55 |
test_dim_test_SOURCES = test/dim_test.cc |
| 55 | 56 |
test_edge_set_test_SOURCES = test/edge_set_test.cc |
| 56 | 57 |
test_error_test_SOURCES = test/error_test.cc |
| 58 |
test_euler_test_SOURCES = test/euler_test.cc |
|
| 57 | 59 |
test_graph_copy_test_SOURCES = test/graph_copy_test.cc |
| 58 | 60 |
test_graph_test_SOURCES = test/graph_test.cc |
| 59 | 61 |
test_graph_utils_test_SOURCES = test/graph_utils_test.cc |
| 60 | 62 |
test_heap_test_SOURCES = test/heap_test.cc |
| 61 | 63 |
test_kruskal_test_SOURCES = test/kruskal_test.cc |
| 62 | 64 |
test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc |
| 63 | 65 |
test_lp_test_SOURCES = test/lp_test.cc |
| 64 | 66 |
test_maps_test_SOURCES = test/maps_test.cc |
0 comments (0 inline)