1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/euler.h Thu Nov 05 15:50:01 2009 +0100
1.3 @@ -0,0 +1,287 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library.
1.7 + *
1.8 + * Copyright (C) 2003-2009
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#ifndef LEMON_EULER_H
1.23 +#define LEMON_EULER_H
1.24 +
1.25 +#include<lemon/core.h>
1.26 +#include<lemon/adaptors.h>
1.27 +#include<lemon/connectivity.h>
1.28 +#include <list>
1.29 +
1.30 +/// \ingroup graph_properties
1.31 +/// \file
1.32 +/// \brief Euler tour iterators and a function for checking the \e Eulerian
1.33 +/// property.
1.34 +///
1.35 +///This file provides Euler tour iterators and a function to check
1.36 +///if a (di)graph is \e Eulerian.
1.37 +
1.38 +namespace lemon {
1.39 +
1.40 + ///Euler tour iterator for digraphs.
1.41 +
1.42 + /// \ingroup graph_prop
1.43 + ///This iterator provides an Euler tour (Eulerian circuit) of a \e directed
1.44 + ///graph (if there exists) and it converts to the \c Arc type of the digraph.
1.45 + ///
1.46 + ///For example, if the given digraph has an Euler tour (i.e it has only one
1.47 + ///non-trivial component and the in-degree is equal to the out-degree
1.48 + ///for all nodes), then the following code will put the arcs of \c g
1.49 + ///to the vector \c et according to an Euler tour of \c g.
1.50 + ///\code
1.51 + /// std::vector<ListDigraph::Arc> et;
1.52 + /// for(DiEulerIt<ListDigraph> e(g); e!=INVALID; ++e)
1.53 + /// et.push_back(e);
1.54 + ///\endcode
1.55 + ///If \c g has no Euler tour, then the resulted walk will not be closed
1.56 + ///or not contain all arcs.
1.57 + ///\sa EulerIt
1.58 + template<typename GR>
1.59 + class DiEulerIt
1.60 + {
1.61 + typedef typename GR::Node Node;
1.62 + typedef typename GR::NodeIt NodeIt;
1.63 + typedef typename GR::Arc Arc;
1.64 + typedef typename GR::ArcIt ArcIt;
1.65 + typedef typename GR::OutArcIt OutArcIt;
1.66 + typedef typename GR::InArcIt InArcIt;
1.67 +
1.68 + const GR &g;
1.69 + typename GR::template NodeMap<OutArcIt> narc;
1.70 + std::list<Arc> euler;
1.71 +
1.72 + public:
1.73 +
1.74 + ///Constructor
1.75 +
1.76 + ///Constructor.
1.77 + ///\param gr A digraph.
1.78 + ///\param start The starting point of the tour. If it is not given,
1.79 + ///the tour will start from the first node that has an outgoing arc.
1.80 + DiEulerIt(const GR &gr, typename GR::Node start = INVALID)
1.81 + : g(gr), narc(g)
1.82 + {
1.83 + if (start==INVALID) {
1.84 + NodeIt n(g);
1.85 + while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n;
1.86 + start=n;
1.87 + }
1.88 + if (start!=INVALID) {
1.89 + for (NodeIt n(g); n!=INVALID; ++n) narc[n]=OutArcIt(g,n);
1.90 + while (narc[start]!=INVALID) {
1.91 + euler.push_back(narc[start]);
1.92 + Node next=g.target(narc[start]);
1.93 + ++narc[start];
1.94 + start=next;
1.95 + }
1.96 + }
1.97 + }
1.98 +
1.99 + ///Arc conversion
1.100 + operator Arc() { return euler.empty()?INVALID:euler.front(); }
1.101 + ///Compare with \c INVALID
1.102 + bool operator==(Invalid) { return euler.empty(); }
1.103 + ///Compare with \c INVALID
1.104 + bool operator!=(Invalid) { return !euler.empty(); }
1.105 +
1.106 + ///Next arc of the tour
1.107 +
1.108 + ///Next arc of the tour
1.109 + ///
1.110 + DiEulerIt &operator++() {
1.111 + Node s=g.target(euler.front());
1.112 + euler.pop_front();
1.113 + typename std::list<Arc>::iterator next=euler.begin();
1.114 + while(narc[s]!=INVALID) {
1.115 + euler.insert(next,narc[s]);
1.116 + Node n=g.target(narc[s]);
1.117 + ++narc[s];
1.118 + s=n;
1.119 + }
1.120 + return *this;
1.121 + }
1.122 + ///Postfix incrementation
1.123 +
1.124 + /// Postfix incrementation.
1.125 + ///
1.126 + ///\warning This incrementation
1.127 + ///returns an \c Arc, not a \ref DiEulerIt, as one may
1.128 + ///expect.
1.129 + Arc operator++(int)
1.130 + {
1.131 + Arc e=*this;
1.132 + ++(*this);
1.133 + return e;
1.134 + }
1.135 + };
1.136 +
1.137 + ///Euler tour iterator for graphs.
1.138 +
1.139 + /// \ingroup graph_properties
1.140 + ///This iterator provides an Euler tour (Eulerian circuit) of an
1.141 + ///\e undirected graph (if there exists) and it converts to the \c Arc
1.142 + ///and \c Edge types of the graph.
1.143 + ///
1.144 + ///For example, if the given graph has an Euler tour (i.e it has only one
1.145 + ///non-trivial component and the degree of each node is even),
1.146 + ///the following code will print the arc IDs according to an
1.147 + ///Euler tour of \c g.
1.148 + ///\code
1.149 + /// for(EulerIt<ListGraph> e(g); e!=INVALID; ++e) {
1.150 + /// std::cout << g.id(Edge(e)) << std::eol;
1.151 + /// }
1.152 + ///\endcode
1.153 + ///Although this iterator is for undirected graphs, it still returns
1.154 + ///arcs in order to indicate the direction of the tour.
1.155 + ///(But arcs convert to edges, of course.)
1.156 + ///
1.157 + ///If \c g has no Euler tour, then the resulted walk will not be closed
1.158 + ///or not contain all edges.
1.159 + template<typename GR>
1.160 + class EulerIt
1.161 + {
1.162 + typedef typename GR::Node Node;
1.163 + typedef typename GR::NodeIt NodeIt;
1.164 + typedef typename GR::Arc Arc;
1.165 + typedef typename GR::Edge Edge;
1.166 + typedef typename GR::ArcIt ArcIt;
1.167 + typedef typename GR::OutArcIt OutArcIt;
1.168 + typedef typename GR::InArcIt InArcIt;
1.169 +
1.170 + const GR &g;
1.171 + typename GR::template NodeMap<OutArcIt> narc;
1.172 + typename GR::template EdgeMap<bool> visited;
1.173 + std::list<Arc> euler;
1.174 +
1.175 + public:
1.176 +
1.177 + ///Constructor
1.178 +
1.179 + ///Constructor.
1.180 + ///\param gr A graph.
1.181 + ///\param start The starting point of the tour. If it is not given,
1.182 + ///the tour will start from the first node that has an incident edge.
1.183 + EulerIt(const GR &gr, typename GR::Node start = INVALID)
1.184 + : g(gr), narc(g), visited(g, false)
1.185 + {
1.186 + if (start==INVALID) {
1.187 + NodeIt n(g);
1.188 + while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n;
1.189 + start=n;
1.190 + }
1.191 + if (start!=INVALID) {
1.192 + for (NodeIt n(g); n!=INVALID; ++n) narc[n]=OutArcIt(g,n);
1.193 + while(narc[start]!=INVALID) {
1.194 + euler.push_back(narc[start]);
1.195 + visited[narc[start]]=true;
1.196 + Node next=g.target(narc[start]);
1.197 + ++narc[start];
1.198 + start=next;
1.199 + while(narc[start]!=INVALID && visited[narc[start]]) ++narc[start];
1.200 + }
1.201 + }
1.202 + }
1.203 +
1.204 + ///Arc conversion
1.205 + operator Arc() const { return euler.empty()?INVALID:euler.front(); }
1.206 + ///Edge conversion
1.207 + operator Edge() const { return euler.empty()?INVALID:euler.front(); }
1.208 + ///Compare with \c INVALID
1.209 + bool operator==(Invalid) const { return euler.empty(); }
1.210 + ///Compare with \c INVALID
1.211 + bool operator!=(Invalid) const { return !euler.empty(); }
1.212 +
1.213 + ///Next arc of the tour
1.214 +
1.215 + ///Next arc of the tour
1.216 + ///
1.217 + EulerIt &operator++() {
1.218 + Node s=g.target(euler.front());
1.219 + euler.pop_front();
1.220 + typename std::list<Arc>::iterator next=euler.begin();
1.221 + while(narc[s]!=INVALID) {
1.222 + while(narc[s]!=INVALID && visited[narc[s]]) ++narc[s];
1.223 + if(narc[s]==INVALID) break;
1.224 + else {
1.225 + euler.insert(next,narc[s]);
1.226 + visited[narc[s]]=true;
1.227 + Node n=g.target(narc[s]);
1.228 + ++narc[s];
1.229 + s=n;
1.230 + }
1.231 + }
1.232 + return *this;
1.233 + }
1.234 +
1.235 + ///Postfix incrementation
1.236 +
1.237 + /// Postfix incrementation.
1.238 + ///
1.239 + ///\warning This incrementation returns an \c Arc (which converts to
1.240 + ///an \c Edge), not an \ref EulerIt, as one may expect.
1.241 + Arc operator++(int)
1.242 + {
1.243 + Arc e=*this;
1.244 + ++(*this);
1.245 + return e;
1.246 + }
1.247 + };
1.248 +
1.249 +
1.250 + ///Check if the given graph is Eulerian
1.251 +
1.252 + /// \ingroup graph_properties
1.253 + ///This function checks if the given graph is Eulerian.
1.254 + ///It works for both directed and undirected graphs.
1.255 + ///
1.256 + ///By definition, a digraph is called \e Eulerian if
1.257 + ///and only if it is connected and the number of incoming and outgoing
1.258 + ///arcs are the same for each node.
1.259 + ///Similarly, an undirected graph is called \e Eulerian if
1.260 + ///and only if it is connected and the number of incident edges is even
1.261 + ///for each node.
1.262 + ///
1.263 + ///\note There are (di)graphs that are not Eulerian, but still have an
1.264 + /// Euler tour, since they may contain isolated nodes.
1.265 + ///
1.266 + ///\sa DiEulerIt, EulerIt
1.267 + template<typename GR>
1.268 +#ifdef DOXYGEN
1.269 + bool
1.270 +#else
1.271 + typename enable_if<UndirectedTagIndicator<GR>,bool>::type
1.272 + eulerian(const GR &g)
1.273 + {
1.274 + for(typename GR::NodeIt n(g);n!=INVALID;++n)
1.275 + if(countIncEdges(g,n)%2) return false;
1.276 + return connected(g);
1.277 + }
1.278 + template<class GR>
1.279 + typename disable_if<UndirectedTagIndicator<GR>,bool>::type
1.280 +#endif
1.281 + eulerian(const GR &g)
1.282 + {
1.283 + for(typename GR::NodeIt n(g);n!=INVALID;++n)
1.284 + if(countInArcs(g,n)!=countOutArcs(g,n)) return false;
1.285 + return connected(undirector(g));
1.286 + }
1.287 +
1.288 +}
1.289 +
1.290 +#endif