r642:16d7255a6849
Sat, 18 Apr 2009 09:51:54
[Not Reviewed]
0 comments (0 inline)
0
2
0
111
88
143
73
| ... | ... |
@@ -23,224 +23,247 @@ |
| 23 | 23 |
#include<lemon/adaptors.h> |
| 24 | 24 |
#include<lemon/connectivity.h> |
| 25 | 25 |
#include <list> |
| 26 | 26 |
|
| 27 | 27 |
/// \ingroup graph_properties |
| 28 | 28 |
/// \file |
| 29 |
/// \brief Euler tour |
|
| 29 |
/// \brief Euler tour iterators and a function for checking the \e Eulerian |
|
| 30 |
/// property. |
|
| 30 | 31 |
/// |
| 31 |
///This file provides an Euler tour iterator and ways to check |
|
| 32 |
///if a digraph is euler. |
|
| 33 |
|
|
| 32 |
///This file provides Euler tour iterators and a function to check |
|
| 33 |
///if a (di)graph is \e Eulerian. |
|
| 34 | 34 |
|
| 35 | 35 |
namespace lemon {
|
| 36 | 36 |
|
| 37 |
///Euler iterator for digraphs. |
|
| 37 |
///Euler tour iterator for digraphs. |
|
| 38 | 38 |
|
| 39 |
/// \ingroup graph_properties |
|
| 40 |
///This iterator converts to the \c Arc type of the digraph and using |
|
| 41 |
///operator ++, it provides an Euler tour of a \e directed |
|
| 42 |
///graph (if there exists). |
|
| 39 |
/// \ingroup graph_prop |
|
| 40 |
///This iterator provides an Euler tour (Eulerian circuit) of a \e directed |
|
| 41 |
///graph (if there exists) and it converts to the \c Arc type of the digraph. |
|
| 43 | 42 |
/// |
| 44 |
///For example |
|
| 45 |
///if the given digraph is Euler (i.e it has only one nontrivial component |
|
| 46 |
///and the in-degree is equal to the out-degree for all nodes), |
|
| 47 |
///the following code will put the arcs of \c g |
|
| 48 |
///to the vector \c et according to an |
|
| 49 |
///Euler tour of \c g. |
|
| 43 |
///For example, if the given digraph has an Euler tour (i.e it has only one |
|
| 44 |
///non-trivial component and the in-degree is equal to the out-degree |
|
| 45 |
///for all nodes), then the following code will put the arcs of \c g |
|
| 46 |
///to the vector \c et according to an Euler tour of \c g. |
|
| 50 | 47 |
///\code |
| 51 | 48 |
/// std::vector<ListDigraph::Arc> et; |
| 52 |
/// for(DiEulerIt<ListDigraph> e(g) |
|
| 49 |
/// for(DiEulerIt<ListDigraph> e(g); e!=INVALID; ++e) |
|
| 53 | 50 |
/// et.push_back(e); |
| 54 | 51 |
///\endcode |
| 55 |
///If \c g |
|
| 52 |
///If \c g has no Euler tour, then the resulted walk will not be closed |
|
| 53 |
///or not contain all arcs. |
|
| 56 | 54 |
///\sa EulerIt |
| 57 | 55 |
template<typename GR> |
| 58 | 56 |
class DiEulerIt |
| 59 | 57 |
{
|
| 60 | 58 |
typedef typename GR::Node Node; |
| 61 | 59 |
typedef typename GR::NodeIt NodeIt; |
| 62 | 60 |
typedef typename GR::Arc Arc; |
| 63 | 61 |
typedef typename GR::ArcIt ArcIt; |
| 64 | 62 |
typedef typename GR::OutArcIt OutArcIt; |
| 65 | 63 |
typedef typename GR::InArcIt InArcIt; |
| 66 | 64 |
|
| 67 | 65 |
const GR &g; |
| 68 |
typename GR::template NodeMap<OutArcIt> |
|
| 66 |
typename GR::template NodeMap<OutArcIt> narc; |
|
| 69 | 67 |
std::list<Arc> euler; |
| 70 | 68 |
|
| 71 | 69 |
public: |
| 72 | 70 |
|
| 73 | 71 |
///Constructor |
| 74 | 72 |
|
| 73 |
///Constructor. |
|
| 75 | 74 |
///\param gr A digraph. |
| 76 |
///\param start The starting point of the tour. If it is not given |
|
| 77 |
/// the tour will start from the first node. |
|
| 75 |
///\param start The starting point of the tour. If it is not given, |
|
| 76 |
///the tour will start from the first node that has an outgoing arc. |
|
| 78 | 77 |
DiEulerIt(const GR &gr, typename GR::Node start = INVALID) |
| 79 |
: g(gr), |
|
| 78 |
: g(gr), narc(g) |
|
| 80 | 79 |
{
|
| 81 |
if(start==INVALID) start=NodeIt(g); |
|
| 82 |
for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n); |
|
| 83 |
while(nedge[start]!=INVALID) {
|
|
| 84 |
euler.push_back(nedge[start]); |
|
| 85 |
Node next=g.target(nedge[start]); |
|
| 86 |
++nedge[start]; |
|
| 87 |
|
|
| 80 |
if (start==INVALID) {
|
|
| 81 |
NodeIt n(g); |
|
| 82 |
while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n; |
|
| 83 |
start=n; |
|
| 84 |
} |
|
| 85 |
if (start!=INVALID) {
|
|
| 86 |
for (NodeIt n(g); n!=INVALID; ++n) narc[n]=OutArcIt(g,n); |
|
| 87 |
while (narc[start]!=INVALID) {
|
|
| 88 |
euler.push_back(narc[start]); |
|
| 89 |
Node next=g.target(narc[start]); |
|
| 90 |
++narc[start]; |
|
| 91 |
start=next; |
|
| 92 |
} |
|
| 88 | 93 |
} |
| 89 | 94 |
} |
| 90 | 95 |
|
| 91 |
///Arc |
|
| 96 |
///Arc conversion |
|
| 92 | 97 |
operator Arc() { return euler.empty()?INVALID:euler.front(); }
|
| 98 |
///Compare with \c INVALID |
|
| 93 | 99 |
bool operator==(Invalid) { return euler.empty(); }
|
| 100 |
///Compare with \c INVALID |
|
| 94 | 101 |
bool operator!=(Invalid) { return !euler.empty(); }
|
| 95 | 102 |
|
| 96 | 103 |
///Next arc of the tour |
| 104 |
|
|
| 105 |
///Next arc of the tour |
|
| 106 |
/// |
|
| 97 | 107 |
DiEulerIt &operator++() {
|
| 98 | 108 |
Node s=g.target(euler.front()); |
| 99 | 109 |
euler.pop_front(); |
| 100 |
//This produces a warning.Strange. |
|
| 101 |
//std::list<Arc>::iterator next=euler.begin(); |
|
| 102 | 110 |
typename std::list<Arc>::iterator next=euler.begin(); |
| 103 |
while(nedge[s]!=INVALID) {
|
|
| 104 |
euler.insert(next,nedge[s]); |
|
| 105 |
Node n=g.target(nedge[s]); |
|
| 106 |
++nedge[s]; |
|
| 111 |
while(narc[s]!=INVALID) {
|
|
| 112 |
euler.insert(next,narc[s]); |
|
| 113 |
Node n=g.target(narc[s]); |
|
| 114 |
++narc[s]; |
|
| 107 | 115 |
s=n; |
| 108 | 116 |
} |
| 109 | 117 |
return *this; |
| 110 | 118 |
} |
| 111 | 119 |
///Postfix incrementation |
| 112 | 120 |
|
| 121 |
/// Postfix incrementation. |
|
| 122 |
/// |
|
| 113 | 123 |
///\warning This incrementation |
| 114 |
///returns an \c Arc, not |
|
| 124 |
///returns an \c Arc, not a \ref DiEulerIt, as one may |
|
| 115 | 125 |
///expect. |
| 116 | 126 |
Arc operator++(int) |
| 117 | 127 |
{
|
| 118 | 128 |
Arc e=*this; |
| 119 | 129 |
++(*this); |
| 120 | 130 |
return e; |
| 121 | 131 |
} |
| 122 | 132 |
}; |
| 123 | 133 |
|
| 124 |
///Euler iterator for graphs. |
|
| 134 |
///Euler tour iterator for graphs. |
|
| 125 | 135 |
|
| 126 | 136 |
/// \ingroup graph_properties |
| 127 |
///This iterator converts to the \c Arc (or \c Edge) |
|
| 128 |
///type of the digraph and using |
|
| 129 |
///operator ++, it provides an Euler tour of an undirected |
|
| 130 |
///digraph (if there exists). |
|
| 137 |
///This iterator provides an Euler tour (Eulerian circuit) of an |
|
| 138 |
///\e undirected graph (if there exists) and it converts to the \c Arc |
|
| 139 |
///and \c Edge types of the graph. |
|
| 131 | 140 |
/// |
| 132 |
///For example |
|
| 133 |
///if the given digraph if Euler (i.e it has only one nontrivial component |
|
| 134 |
/// |
|
| 141 |
///For example, if the given graph has an Euler tour (i.e it has only one |
|
| 142 |
///non-trivial component and the degree of each node is even), |
|
| 135 | 143 |
///the following code will print the arc IDs according to an |
| 136 | 144 |
///Euler tour of \c g. |
| 137 | 145 |
///\code |
| 138 |
/// for(EulerIt<ListGraph> e(g) |
|
| 146 |
/// for(EulerIt<ListGraph> e(g); e!=INVALID; ++e) {
|
|
| 139 | 147 |
/// std::cout << g.id(Edge(e)) << std::eol; |
| 140 | 148 |
/// } |
| 141 | 149 |
///\endcode |
| 142 |
///Although the iterator provides an Euler tour of an graph, |
|
| 143 |
///it still returns Arcs in order to indicate the direction of the tour. |
|
| 144 |
/// |
|
| 150 |
///Although this iterator is for undirected graphs, it still returns |
|
| 151 |
///arcs in order to indicate the direction of the tour. |
|
| 152 |
///(But arcs convert to edges, of course.) |
|
| 145 | 153 |
/// |
| 146 |
///If \c g is not Euler then the resulted tour will not be full or closed. |
|
| 147 |
///\sa EulerIt |
|
| 154 |
///If \c g has no Euler tour, then the resulted walk will not be closed |
|
| 155 |
///or not contain all edges. |
|
| 148 | 156 |
template<typename GR> |
| 149 | 157 |
class EulerIt |
| 150 | 158 |
{
|
| 151 | 159 |
typedef typename GR::Node Node; |
| 152 | 160 |
typedef typename GR::NodeIt NodeIt; |
| 153 | 161 |
typedef typename GR::Arc Arc; |
| 154 | 162 |
typedef typename GR::Edge Edge; |
| 155 | 163 |
typedef typename GR::ArcIt ArcIt; |
| 156 | 164 |
typedef typename GR::OutArcIt OutArcIt; |
| 157 | 165 |
typedef typename GR::InArcIt InArcIt; |
| 158 | 166 |
|
| 159 | 167 |
const GR &g; |
| 160 |
typename GR::template NodeMap<OutArcIt> |
|
| 168 |
typename GR::template NodeMap<OutArcIt> narc; |
|
| 161 | 169 |
typename GR::template EdgeMap<bool> visited; |
| 162 | 170 |
std::list<Arc> euler; |
| 163 | 171 |
|
| 164 | 172 |
public: |
| 165 | 173 |
|
| 166 | 174 |
///Constructor |
| 167 | 175 |
|
| 168 |
///\param gr An graph. |
|
| 169 |
///\param start The starting point of the tour. If it is not given |
|
| 170 |
/// |
|
| 176 |
///Constructor. |
|
| 177 |
///\param gr A graph. |
|
| 178 |
///\param start The starting point of the tour. If it is not given, |
|
| 179 |
///the tour will start from the first node that has an incident edge. |
|
| 171 | 180 |
EulerIt(const GR &gr, typename GR::Node start = INVALID) |
| 172 |
: g(gr), |
|
| 181 |
: g(gr), narc(g), visited(g, false) |
|
| 173 | 182 |
{
|
| 174 |
if(start==INVALID) start=NodeIt(g); |
|
| 175 |
for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n); |
|
| 176 |
while(nedge[start]!=INVALID) {
|
|
| 177 |
euler.push_back(nedge[start]); |
|
| 178 |
visited[nedge[start]]=true; |
|
| 179 |
Node next=g.target(nedge[start]); |
|
| 180 |
++nedge[start]; |
|
| 181 |
start=next; |
|
| 182 |
|
|
| 183 |
if (start==INVALID) {
|
|
| 184 |
NodeIt n(g); |
|
| 185 |
while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n; |
|
| 186 |
start=n; |
|
| 187 |
} |
|
| 188 |
if (start!=INVALID) {
|
|
| 189 |
for (NodeIt n(g); n!=INVALID; ++n) narc[n]=OutArcIt(g,n); |
|
| 190 |
while(narc[start]!=INVALID) {
|
|
| 191 |
euler.push_back(narc[start]); |
|
| 192 |
visited[narc[start]]=true; |
|
| 193 |
Node next=g.target(narc[start]); |
|
| 194 |
++narc[start]; |
|
| 195 |
start=next; |
|
| 196 |
while(narc[start]!=INVALID && visited[narc[start]]) ++narc[start]; |
|
| 197 |
} |
|
| 183 | 198 |
} |
| 184 | 199 |
} |
| 185 | 200 |
|
| 186 |
///Arc |
|
| 201 |
///Arc conversion |
|
| 187 | 202 |
operator Arc() const { return euler.empty()?INVALID:euler.front(); }
|
| 188 |
/// |
|
| 203 |
///Edge conversion |
|
| 189 | 204 |
operator Edge() const { return euler.empty()?INVALID:euler.front(); }
|
| 190 |
///\ |
|
| 205 |
///Compare with \c INVALID |
|
| 191 | 206 |
bool operator==(Invalid) const { return euler.empty(); }
|
| 192 |
///\ |
|
| 207 |
///Compare with \c INVALID |
|
| 193 | 208 |
bool operator!=(Invalid) const { return !euler.empty(); }
|
| 194 | 209 |
|
| 195 | 210 |
///Next arc of the tour |
| 211 |
|
|
| 212 |
///Next arc of the tour |
|
| 213 |
/// |
|
| 196 | 214 |
EulerIt &operator++() {
|
| 197 | 215 |
Node s=g.target(euler.front()); |
| 198 | 216 |
euler.pop_front(); |
| 199 | 217 |
typename std::list<Arc>::iterator next=euler.begin(); |
| 200 |
|
|
| 201 |
while(nedge[s]!=INVALID) {
|
|
| 202 |
while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s]; |
|
| 203 |
if(nedge[s]==INVALID) break; |
|
| 218 |
while(narc[s]!=INVALID) {
|
|
| 219 |
while(narc[s]!=INVALID && visited[narc[s]]) ++narc[s]; |
|
| 220 |
if(narc[s]==INVALID) break; |
|
| 204 | 221 |
else {
|
| 205 |
euler.insert(next,nedge[s]); |
|
| 206 |
visited[nedge[s]]=true; |
|
| 207 |
Node n=g.target(nedge[s]); |
|
| 208 |
++nedge[s]; |
|
| 222 |
euler.insert(next,narc[s]); |
|
| 223 |
visited[narc[s]]=true; |
|
| 224 |
Node n=g.target(narc[s]); |
|
| 225 |
++narc[s]; |
|
| 209 | 226 |
s=n; |
| 210 | 227 |
} |
| 211 | 228 |
} |
| 212 | 229 |
return *this; |
| 213 | 230 |
} |
| 214 | 231 |
|
| 215 | 232 |
///Postfix incrementation |
| 216 | 233 |
|
| 217 |
///\warning This incrementation |
|
| 218 |
///returns an \c Arc, not an \ref EulerIt, as one may |
|
| 219 |
/// |
|
| 234 |
/// Postfix incrementation. |
|
| 235 |
/// |
|
| 236 |
///\warning This incrementation returns an \c Arc (which converts to |
|
| 237 |
///an \c Edge), not an \ref EulerIt, as one may expect. |
|
| 220 | 238 |
Arc operator++(int) |
| 221 | 239 |
{
|
| 222 | 240 |
Arc e=*this; |
| 223 | 241 |
++(*this); |
| 224 | 242 |
return e; |
| 225 | 243 |
} |
| 226 | 244 |
}; |
| 227 | 245 |
|
| 228 | 246 |
|
| 229 |
/// |
|
| 247 |
///Check if the given graph is \e Eulerian |
|
| 230 | 248 |
|
| 231 | 249 |
/// \ingroup graph_properties |
| 232 |
///Checks if the graph is Eulerian. It works for both directed and undirected |
|
| 233 |
///graphs. |
|
| 234 |
///\note By definition, a digraph is called \e Eulerian if |
|
| 235 |
///and only if it is connected and the number of its incoming and outgoing |
|
| 250 |
///This function checks if the given graph is \e Eulerian. |
|
| 251 |
///It works for both directed and undirected graphs. |
|
| 252 |
/// |
|
| 253 |
///By definition, a digraph is called \e Eulerian if |
|
| 254 |
///and only if it is connected and the number of incoming and outgoing |
|
| 236 | 255 |
///arcs are the same for each node. |
| 237 | 256 |
///Similarly, an undirected graph is called \e Eulerian if |
| 238 |
///and only if it is connected and the number of incident arcs is even |
|
| 239 |
///for each node. <em>Therefore, there are digraphs which are not Eulerian, |
|
| 240 |
/// |
|
| 257 |
///and only if it is connected and the number of incident edges is even |
|
| 258 |
///for each node. |
|
| 259 |
/// |
|
| 260 |
///\note There are (di)graphs that are not Eulerian, but still have an |
|
| 261 |
/// Euler tour, since they may contain isolated nodes. |
|
| 262 |
/// |
|
| 263 |
///\sa DiEulerIt, EulerIt |
|
| 241 | 264 |
template<typename GR> |
| 242 | 265 |
#ifdef DOXYGEN |
| 243 | 266 |
bool |
| 244 | 267 |
#else |
| 245 | 268 |
typename enable_if<UndirectedTagIndicator<GR>,bool>::type |
| 246 | 269 |
eulerian(const GR &g) |
| ... | ... |
@@ -253,12 +276,12 @@ |
| 253 | 276 |
typename disable_if<UndirectedTagIndicator<GR>,bool>::type |
| 254 | 277 |
#endif |
| 255 | 278 |
eulerian(const GR &g) |
| 256 | 279 |
{
|
| 257 | 280 |
for(typename GR::NodeIt n(g);n!=INVALID;++n) |
| 258 | 281 |
if(countInArcs(g,n)!=countOutArcs(g,n)) return false; |
| 259 |
return connected( |
|
| 282 |
return connected(undirector(g)); |
|
| 260 | 283 |
} |
| 261 | 284 |
|
| 262 | 285 |
} |
| 263 | 286 |
|
| 264 | 287 |
#endif |
| ... | ... |
@@ -15,139 +15,209 @@ |
| 15 | 15 |
* purpose. |
| 16 | 16 |
* |
| 17 | 17 |
*/ |
| 18 | 18 |
|
| 19 | 19 |
#include <lemon/euler.h> |
| 20 | 20 |
#include <lemon/list_graph.h> |
| 21 |
#include < |
|
| 21 |
#include <lemon/adaptors.h> |
|
| 22 |
#include "test_tools.h" |
|
| 22 | 23 |
|
| 23 | 24 |
using namespace lemon; |
| 24 | 25 |
|
| 25 | 26 |
template <typename Digraph> |
| 26 |
void checkDiEulerIt(const Digraph& g |
|
| 27 |
void checkDiEulerIt(const Digraph& g, |
|
| 28 |
const typename Digraph::Node& start = INVALID) |
|
| 27 | 29 |
{
|
| 28 | 30 |
typename Digraph::template ArcMap<int> visitationNumber(g, 0); |
| 29 | 31 |
|
| 30 |
DiEulerIt<Digraph> e(g); |
|
| 32 |
DiEulerIt<Digraph> e(g, start); |
|
| 33 |
if (e == INVALID) return; |
|
| 31 | 34 |
typename Digraph::Node firstNode = g.source(e); |
| 32 | 35 |
typename Digraph::Node lastNode = g.target(e); |
| 36 |
if (start != INVALID) {
|
|
| 37 |
check(firstNode == start, "checkDiEulerIt: Wrong first node"); |
|
| 38 |
} |
|
| 33 | 39 |
|
| 34 |
for (; e != INVALID; ++e) |
|
| 35 |
{
|
|
| 36 |
if (e != INVALID) |
|
| 37 |
{
|
|
| 38 |
lastNode = g.target(e); |
|
| 39 |
} |
|
| 40 |
for (; e != INVALID; ++e) {
|
|
| 41 |
if (e != INVALID) lastNode = g.target(e); |
|
| 40 | 42 |
++visitationNumber[e]; |
| 41 | 43 |
} |
| 42 | 44 |
|
| 43 | 45 |
check(firstNode == lastNode, |
| 44 |
"checkDiEulerIt: |
|
| 46 |
"checkDiEulerIt: First and last nodes are not the same"); |
|
| 45 | 47 |
|
| 46 | 48 |
for (typename Digraph::ArcIt a(g); a != INVALID; ++a) |
| 47 | 49 |
{
|
| 48 | 50 |
check(visitationNumber[a] == 1, |
| 49 |
"checkDiEulerIt: |
|
| 51 |
"checkDiEulerIt: Not visited or multiple times visited arc found"); |
|
| 50 | 52 |
} |
| 51 | 53 |
} |
| 52 | 54 |
|
| 53 | 55 |
template <typename Graph> |
| 54 |
void checkEulerIt(const Graph& g |
|
| 56 |
void checkEulerIt(const Graph& g, |
|
| 57 |
const typename Graph::Node& start = INVALID) |
|
| 55 | 58 |
{
|
| 56 | 59 |
typename Graph::template EdgeMap<int> visitationNumber(g, 0); |
| 57 | 60 |
|
| 58 |
EulerIt<Graph> e(g); |
|
| 59 |
typename Graph::Node firstNode = g.u(e); |
|
| 60 |
|
|
| 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 |
} |
|
| 61 | 68 |
|
| 62 |
for (; e != INVALID; ++e) |
|
| 63 |
{
|
|
| 64 |
if (e != INVALID) |
|
| 65 |
{
|
|
| 66 |
lastNode = g.v(e); |
|
| 67 |
} |
|
| 69 |
for (; e != INVALID; ++e) {
|
|
| 70 |
if (e != INVALID) lastNode = g.target(typename Graph::Arc(e)); |
|
| 68 | 71 |
++visitationNumber[e]; |
| 69 | 72 |
} |
| 70 | 73 |
|
| 71 | 74 |
check(firstNode == lastNode, |
| 72 |
"checkEulerIt: |
|
| 75 |
"checkEulerIt: First and last nodes are not the same"); |
|
| 73 | 76 |
|
| 74 | 77 |
for (typename Graph::EdgeIt e(g); e != INVALID; ++e) |
| 75 | 78 |
{
|
| 76 | 79 |
check(visitationNumber[e] == 1, |
| 77 |
"checkEulerIt: |
|
| 80 |
"checkEulerIt: Not visited or multiple times visited edge found"); |
|
| 78 | 81 |
} |
| 79 | 82 |
} |
| 80 | 83 |
|
| 81 | 84 |
int main() |
| 82 | 85 |
{
|
| 83 | 86 |
typedef ListDigraph Digraph; |
| 84 |
typedef |
|
| 87 |
typedef Undirector<Digraph> Graph; |
|
| 88 |
|
|
| 89 |
{
|
|
| 90 |
Digraph d; |
|
| 91 |
Graph g(d); |
|
| 92 |
|
|
| 93 |
checkDiEulerIt(d); |
|
| 94 |
checkDiEulerIt(g); |
|
| 95 |
checkEulerIt(g); |
|
| 85 | 96 |
|
| 86 |
|
|
| 97 |
check(eulerian(d), "This graph is Eulerian"); |
|
| 98 |
check(eulerian(g), "This graph is Eulerian"); |
|
| 99 |
} |
|
| 87 | 100 |
{
|
| 88 |
Digraph |
|
| 101 |
Digraph d; |
|
| 102 |
Graph g(d); |
|
| 103 |
Digraph::Node n = d.addNode(); |
|
| 89 | 104 |
|
| 90 |
Digraph::Node n0 = g.addNode(); |
|
| 91 |
Digraph::Node n1 = g.addNode(); |
|
| 92 |
|
|
| 105 |
checkDiEulerIt(d); |
|
| 106 |
checkDiEulerIt(g); |
|
| 107 |
checkEulerIt(g); |
|
| 93 | 108 |
|
| 94 |
g.addArc(n0, n1); |
|
| 95 |
g.addArc(n1, n0); |
|
| 96 |
g.addArc(n1, n2); |
|
| 97 |
g.addArc(n2, n1); |
|
| 109 |
check(eulerian(d), "This graph is Eulerian"); |
|
| 110 |
check(eulerian(g), "This graph is Eulerian"); |
|
| 98 | 111 |
} |
| 112 |
{
|
|
| 113 |
Digraph d; |
|
| 114 |
Graph g(d); |
|
| 115 |
Digraph::Node n = d.addNode(); |
|
| 116 |
d.addArc(n, n); |
|
| 99 | 117 |
|
| 100 |
|
|
| 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 |
} |
|
| 101 | 125 |
{
|
| 102 |
Digraph |
|
| 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); |
|
| 103 | 136 |
|
| 104 |
Digraph::Node n0 = g.addNode(); |
|
| 105 |
Digraph::Node n1 = g.addNode(); |
|
| 106 |
|
|
| 137 |
checkDiEulerIt(d); |
|
| 138 |
checkDiEulerIt(d, n2); |
|
| 139 |
checkDiEulerIt(g); |
|
| 140 |
checkDiEulerIt(g, n2); |
|
| 141 |
checkEulerIt(g); |
|
| 142 |
checkEulerIt(g, n2); |
|
| 107 | 143 |
|
| 108 |
g.addArc(n0, n1); |
|
| 109 |
g.addArc(n1, n0); |
|
| 110 |
|
|
| 144 |
check(eulerian(d), "This graph is Eulerian"); |
|
| 145 |
check(eulerian(g), "This graph is Eulerian"); |
|
| 111 | 146 |
} |
| 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); |
|
| 112 | 168 |
|
| 113 |
|
|
| 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 |
} |
|
| 114 | 183 |
{
|
| 115 |
|
|
| 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); |
|
| 116 | 196 |
|
| 117 |
Graph::Node n0 = g.addNode(); |
|
| 118 |
Graph::Node n1 = g.addNode(); |
|
| 119 |
|
|
| 197 |
checkDiEulerIt(d); |
|
| 198 |
checkDiEulerIt(d, n2); |
|
| 120 | 199 |
|
| 121 |
g.addEdge(n0, n1); |
|
| 122 |
g.addEdge(n1, n2); |
|
| 123 |
|
|
| 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"); |
|
| 124 | 207 |
} |
| 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); |
|
| 125 | 217 |
|
| 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); |
|
| 218 |
check(!eulerian(d), "This graph is not Eulerian"); |
|
| 219 |
check(!eulerian(g), "This graph is not Eulerian"); |
|
| 136 | 220 |
} |
| 137 | 221 |
|
| 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 | 222 |
return 0; |
| 153 | 223 |
} |
0 comments (0 inline)