[567] | 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 |
---|
[567] | 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 | #ifndef LEMON_EULER_H |
---|
| 20 | #define LEMON_EULER_H |
---|
| 21 | |
---|
| 22 | #include<lemon/core.h> |
---|
| 23 | #include<lemon/adaptors.h> |
---|
| 24 | #include<lemon/connectivity.h> |
---|
| 25 | #include <list> |
---|
| 26 | |
---|
[633] | 27 | /// \ingroup graph_properties |
---|
[567] | 28 | /// \file |
---|
[1081] | 29 | /// \brief Euler tour iterators and a function for checking the \e Eulerian |
---|
[639] | 30 | /// property. |
---|
[567] | 31 | /// |
---|
[639] | 32 | ///This file provides Euler tour iterators and a function to check |
---|
| 33 | ///if a (di)graph is \e Eulerian. |
---|
[567] | 34 | |
---|
| 35 | namespace lemon { |
---|
| 36 | |
---|
[639] | 37 | ///Euler tour iterator for digraphs. |
---|
[567] | 38 | |
---|
[639] | 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. |
---|
[567] | 42 | /// |
---|
[639] | 43 | ///For example, if the given digraph has an Euler tour (i.e it has only one |
---|
[1081] | 44 | ///non-trivial component and the in-degree is equal to the out-degree |
---|
[639] | 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. |
---|
[567] | 47 | ///\code |
---|
| 48 | /// std::vector<ListDigraph::Arc> et; |
---|
[639] | 49 | /// for(DiEulerIt<ListDigraph> e(g); e!=INVALID; ++e) |
---|
[567] | 50 | /// et.push_back(e); |
---|
| 51 | ///\endcode |
---|
[639] | 52 | ///If \c g has no Euler tour, then the resulted walk will not be closed |
---|
| 53 | ///or not contain all arcs. |
---|
[567] | 54 | ///\sa EulerIt |
---|
[606] | 55 | template<typename GR> |
---|
[567] | 56 | class DiEulerIt |
---|
| 57 | { |
---|
[606] | 58 | typedef typename GR::Node Node; |
---|
| 59 | typedef typename GR::NodeIt NodeIt; |
---|
| 60 | typedef typename GR::Arc Arc; |
---|
| 61 | typedef typename GR::ArcIt ArcIt; |
---|
| 62 | typedef typename GR::OutArcIt OutArcIt; |
---|
| 63 | typedef typename GR::InArcIt InArcIt; |
---|
[567] | 64 | |
---|
[606] | 65 | const GR &g; |
---|
[639] | 66 | typename GR::template NodeMap<OutArcIt> narc; |
---|
[567] | 67 | std::list<Arc> euler; |
---|
| 68 | |
---|
| 69 | public: |
---|
| 70 | |
---|
| 71 | ///Constructor |
---|
| 72 | |
---|
[639] | 73 | ///Constructor. |
---|
[606] | 74 | ///\param gr A digraph. |
---|
[639] | 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. |
---|
[606] | 77 | DiEulerIt(const GR &gr, typename GR::Node start = INVALID) |
---|
[639] | 78 | : g(gr), narc(g) |
---|
[567] | 79 | { |
---|
[638] | 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) { |
---|
[639] | 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]; |
---|
[638] | 91 | start=next; |
---|
| 92 | } |
---|
[567] | 93 | } |
---|
| 94 | } |
---|
| 95 | |
---|
[639] | 96 | ///Arc conversion |
---|
[567] | 97 | operator Arc() { return euler.empty()?INVALID:euler.front(); } |
---|
[639] | 98 | ///Compare with \c INVALID |
---|
[567] | 99 | bool operator==(Invalid) { return euler.empty(); } |
---|
[639] | 100 | ///Compare with \c INVALID |
---|
[567] | 101 | bool operator!=(Invalid) { return !euler.empty(); } |
---|
| 102 | |
---|
| 103 | ///Next arc of the tour |
---|
[639] | 104 | |
---|
| 105 | ///Next arc of the tour |
---|
| 106 | /// |
---|
[567] | 107 | DiEulerIt &operator++() { |
---|
| 108 | Node s=g.target(euler.front()); |
---|
| 109 | euler.pop_front(); |
---|
| 110 | typename std::list<Arc>::iterator next=euler.begin(); |
---|
[639] | 111 | while(narc[s]!=INVALID) { |
---|
| 112 | euler.insert(next,narc[s]); |
---|
| 113 | Node n=g.target(narc[s]); |
---|
| 114 | ++narc[s]; |
---|
[567] | 115 | s=n; |
---|
| 116 | } |
---|
| 117 | return *this; |
---|
| 118 | } |
---|
| 119 | ///Postfix incrementation |
---|
| 120 | |
---|
[639] | 121 | /// Postfix incrementation. |
---|
| 122 | /// |
---|
[567] | 123 | ///\warning This incrementation |
---|
[639] | 124 | ///returns an \c Arc, not a \ref DiEulerIt, as one may |
---|
[567] | 125 | ///expect. |
---|
| 126 | Arc operator++(int) |
---|
| 127 | { |
---|
| 128 | Arc e=*this; |
---|
| 129 | ++(*this); |
---|
| 130 | return e; |
---|
| 131 | } |
---|
| 132 | }; |
---|
| 133 | |
---|
[639] | 134 | ///Euler tour iterator for graphs. |
---|
[567] | 135 | |
---|
[633] | 136 | /// \ingroup graph_properties |
---|
[639] | 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. |
---|
[567] | 140 | /// |
---|
[1081] | 141 | ///For example, if the given graph has an Euler tour (i.e it has only one |
---|
[639] | 142 | ///non-trivial component and the degree of each node is even), |
---|
[567] | 143 | ///the following code will print the arc IDs according to an |
---|
| 144 | ///Euler tour of \c g. |
---|
| 145 | ///\code |
---|
[639] | 146 | /// for(EulerIt<ListGraph> e(g); e!=INVALID; ++e) { |
---|
[567] | 147 | /// std::cout << g.id(Edge(e)) << std::eol; |
---|
| 148 | /// } |
---|
| 149 | ///\endcode |
---|
[1081] | 150 | ///Although this iterator is for undirected graphs, it still returns |
---|
[639] | 151 | ///arcs in order to indicate the direction of the tour. |
---|
| 152 | ///(But arcs convert to edges, of course.) |
---|
[567] | 153 | /// |
---|
[639] | 154 | ///If \c g has no Euler tour, then the resulted walk will not be closed |
---|
| 155 | ///or not contain all edges. |
---|
[606] | 156 | template<typename GR> |
---|
[567] | 157 | class EulerIt |
---|
| 158 | { |
---|
[606] | 159 | typedef typename GR::Node Node; |
---|
| 160 | typedef typename GR::NodeIt NodeIt; |
---|
| 161 | typedef typename GR::Arc Arc; |
---|
| 162 | typedef typename GR::Edge Edge; |
---|
| 163 | typedef typename GR::ArcIt ArcIt; |
---|
| 164 | typedef typename GR::OutArcIt OutArcIt; |
---|
| 165 | typedef typename GR::InArcIt InArcIt; |
---|
[567] | 166 | |
---|
[606] | 167 | const GR &g; |
---|
[639] | 168 | typename GR::template NodeMap<OutArcIt> narc; |
---|
[606] | 169 | typename GR::template EdgeMap<bool> visited; |
---|
[567] | 170 | std::list<Arc> euler; |
---|
| 171 | |
---|
| 172 | public: |
---|
| 173 | |
---|
| 174 | ///Constructor |
---|
| 175 | |
---|
[639] | 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. |
---|
[606] | 180 | EulerIt(const GR &gr, typename GR::Node start = INVALID) |
---|
[639] | 181 | : g(gr), narc(g), visited(g, false) |
---|
[567] | 182 | { |
---|
[638] | 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) { |
---|
[639] | 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]; |
---|
[638] | 195 | start=next; |
---|
[639] | 196 | while(narc[start]!=INVALID && visited[narc[start]]) ++narc[start]; |
---|
[638] | 197 | } |
---|
[567] | 198 | } |
---|
| 199 | } |
---|
| 200 | |
---|
[639] | 201 | ///Arc conversion |
---|
[567] | 202 | operator Arc() const { return euler.empty()?INVALID:euler.front(); } |
---|
[639] | 203 | ///Edge conversion |
---|
[567] | 204 | operator Edge() const { return euler.empty()?INVALID:euler.front(); } |
---|
[639] | 205 | ///Compare with \c INVALID |
---|
[567] | 206 | bool operator==(Invalid) const { return euler.empty(); } |
---|
[639] | 207 | ///Compare with \c INVALID |
---|
[567] | 208 | bool operator!=(Invalid) const { return !euler.empty(); } |
---|
| 209 | |
---|
| 210 | ///Next arc of the tour |
---|
[639] | 211 | |
---|
| 212 | ///Next arc of the tour |
---|
| 213 | /// |
---|
[567] | 214 | EulerIt &operator++() { |
---|
| 215 | Node s=g.target(euler.front()); |
---|
| 216 | euler.pop_front(); |
---|
| 217 | typename std::list<Arc>::iterator next=euler.begin(); |
---|
[639] | 218 | while(narc[s]!=INVALID) { |
---|
| 219 | while(narc[s]!=INVALID && visited[narc[s]]) ++narc[s]; |
---|
| 220 | if(narc[s]==INVALID) break; |
---|
[567] | 221 | else { |
---|
[639] | 222 | euler.insert(next,narc[s]); |
---|
| 223 | visited[narc[s]]=true; |
---|
| 224 | Node n=g.target(narc[s]); |
---|
| 225 | ++narc[s]; |
---|
[567] | 226 | s=n; |
---|
| 227 | } |
---|
| 228 | } |
---|
| 229 | return *this; |
---|
| 230 | } |
---|
| 231 | |
---|
| 232 | ///Postfix incrementation |
---|
| 233 | |
---|
[639] | 234 | /// Postfix incrementation. |
---|
| 235 | /// |
---|
[1081] | 236 | ///\warning This incrementation returns an \c Arc (which converts to |
---|
[639] | 237 | ///an \c Edge), not an \ref EulerIt, as one may expect. |
---|
[567] | 238 | Arc operator++(int) |
---|
| 239 | { |
---|
| 240 | Arc e=*this; |
---|
| 241 | ++(*this); |
---|
| 242 | return e; |
---|
| 243 | } |
---|
| 244 | }; |
---|
| 245 | |
---|
| 246 | |
---|
[695] | 247 | ///Check if the given graph is Eulerian |
---|
[567] | 248 | |
---|
[633] | 249 | /// \ingroup graph_properties |
---|
[695] | 250 | ///This function checks if the given graph is Eulerian. |
---|
[639] | 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 |
---|
[567] | 255 | ///arcs are the same for each node. |
---|
[568] | 256 | ///Similarly, an undirected graph is called \e Eulerian if |
---|
[639] | 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 |
---|
[606] | 264 | template<typename GR> |
---|
[567] | 265 | #ifdef DOXYGEN |
---|
| 266 | bool |
---|
| 267 | #else |
---|
[606] | 268 | typename enable_if<UndirectedTagIndicator<GR>,bool>::type |
---|
| 269 | eulerian(const GR &g) |
---|
[567] | 270 | { |
---|
[606] | 271 | for(typename GR::NodeIt n(g);n!=INVALID;++n) |
---|
[567] | 272 | if(countIncEdges(g,n)%2) return false; |
---|
| 273 | return connected(g); |
---|
| 274 | } |
---|
[606] | 275 | template<class GR> |
---|
| 276 | typename disable_if<UndirectedTagIndicator<GR>,bool>::type |
---|
[567] | 277 | #endif |
---|
[606] | 278 | eulerian(const GR &g) |
---|
[567] | 279 | { |
---|
[606] | 280 | for(typename GR::NodeIt n(g);n!=INVALID;++n) |
---|
[567] | 281 | if(countInArcs(g,n)!=countOutArcs(g,n)) return false; |
---|
[639] | 282 | return connected(undirector(g)); |
---|
[567] | 283 | } |
---|
| 284 | |
---|
| 285 | } |
---|
| 286 | |
---|
| 287 | #endif |
---|