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 |
} |
| ... | ... |
@@ -45,24 +45,25 @@ |
| 45 | 45 |
endif |
| 46 | 46 |
|
| 47 | 47 |
lemon_HEADERS += \ |
| 48 | 48 |
lemon/adaptors.h \ |
| 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 \ |
| 65 | 66 |
lemon/elevator.h \ |
| 66 | 67 |
lemon/error.h \ |
| 67 | 68 |
lemon/euler.h \ |
| 68 | 69 |
lemon/full_graph.h \ |
| ... | ... |
@@ -45,25 +45,24 @@ |
| 45 | 45 |
///if the given digraph is Euler (i.e it has only one nontrivial component |
| 46 | 46 |
///and the in-degree is equal to the out-degree for all nodes), |
| 47 | 47 |
///the following code will put the arcs of \c g |
| 48 | 48 |
///to the vector \c et according to an |
| 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; |
| 66 | 65 |
typedef typename Digraph::InArcIt InArcIt; |
| 67 | 66 |
|
| 68 | 67 |
const Digraph &g; |
| 69 | 68 |
typename Digraph::template NodeMap<OutArcIt> nedge; |
| ... | ... |
@@ -137,25 +136,24 @@ |
| 137 | 136 |
///Euler tour of \c g. |
| 138 | 137 |
///\code |
| 139 | 138 |
/// for(EulerIt<ListGraph> e(g),e!=INVALID;++e) {
|
| 140 | 139 |
/// std::cout << g.id(Edge(e)) << std::eol; |
| 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; |
| 158 | 156 |
typedef typename Digraph::OutArcIt OutArcIt; |
| 159 | 157 |
typedef typename Digraph::InArcIt InArcIt; |
| 160 | 158 |
|
| 161 | 159 |
const Digraph &g; |
| ... | ... |
@@ -231,25 +229,24 @@ |
| 231 | 229 |
///Checks if the graph is Eulerian |
| 232 | 230 |
|
| 233 | 231 |
/// \ingroup graph_prop |
| 234 | 232 |
///Checks if the graph is Eulerian. It works for both directed and undirected |
| 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) |
| 252 | 249 |
if(countIncEdges(g,n)%2) return false; |
| 253 | 250 |
return connected(g); |
| 254 | 251 |
} |
| 255 | 252 |
template<class Digraph> |
| ... | ... |
@@ -11,24 +11,25 @@ |
| 11 | 11 |
|
| 12 | 12 |
SET(TESTS |
| 13 | 13 |
adaptors_test |
| 14 | 14 |
bfs_test |
| 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 |
| 31 | 32 |
path_test |
| 32 | 33 |
preflow_test |
| 33 | 34 |
radix_sort_test |
| 34 | 35 |
random_test |
| ... | ... |
@@ -7,24 +7,25 @@ |
| 7 | 7 |
|
| 8 | 8 |
check_PROGRAMS += \ |
| 9 | 9 |
test/adaptors_test \ |
| 10 | 10 |
test/bfs_test \ |
| 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 \ |
| 27 | 28 |
test/path_test \ |
| 28 | 29 |
test/preflow_test \ |
| 29 | 30 |
test/radix_sort_test \ |
| 30 | 31 |
test/random_test \ |
| ... | ... |
@@ -45,24 +46,25 @@ |
| 45 | 46 |
XFAIL_TESTS += test/test_tools_fail$(EXEEXT) |
| 46 | 47 |
|
| 47 | 48 |
test_adaptors_test_SOURCES = test/adaptors_test.cc |
| 48 | 49 |
test_bfs_test_SOURCES = test/bfs_test.cc |
| 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 |
| 65 | 67 |
test_mip_test_SOURCES = test/mip_test.cc |
| 66 | 68 |
test_max_matching_test_SOURCES = test/max_matching_test.cc |
| 67 | 69 |
test_path_test_SOURCES = test/path_test.cc |
| 68 | 70 |
test_preflow_test_SOURCES = test/preflow_test.cc |
0 comments (0 inline)