1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/euler.h Mon Feb 23 11:30:15 2009 +0000
1.3 @@ -0,0 +1,267 @@
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_prop
1.31 +/// \file
1.32 +/// \brief Euler tour
1.33 +///
1.34 +///This file provides an Euler tour iterator and ways to check
1.35 +///if a digraph is euler.
1.36 +
1.37 +
1.38 +namespace lemon {
1.39 +
1.40 + ///Euler iterator for digraphs.
1.41 +
1.42 + /// \ingroup graph_prop
1.43 + ///This iterator converts to the \c Arc type of the digraph and using
1.44 + ///operator ++, it provides an Euler tour of a \e directed
1.45 + ///graph (if there exists).
1.46 + ///
1.47 + ///For example
1.48 + ///if the given digraph is Euler (i.e it has only one nontrivial component
1.49 + ///and the in-degree is equal to the out-degree for all nodes),
1.50 + ///the following code will put the arcs of \c g
1.51 + ///to the vector \c et according to an
1.52 + ///Euler tour of \c g.
1.53 + ///\code
1.54 + /// std::vector<ListDigraph::Arc> et;
1.55 + /// for(DiEulerIt<ListDigraph> e(g),e!=INVALID;++e)
1.56 + /// et.push_back(e);
1.57 + ///\endcode
1.58 + ///If \c g is not Euler then the resulted tour will not be full or closed.
1.59 + ///\sa EulerIt
1.60 + ///\todo Test required
1.61 + template<class Digraph>
1.62 + class DiEulerIt
1.63 + {
1.64 + typedef typename Digraph::Node Node;
1.65 + typedef typename Digraph::NodeIt NodeIt;
1.66 + typedef typename Digraph::Arc Arc;
1.67 + typedef typename Digraph::ArcIt ArcIt;
1.68 + typedef typename Digraph::OutArcIt OutArcIt;
1.69 + typedef typename Digraph::InArcIt InArcIt;
1.70 +
1.71 + const Digraph &g;
1.72 + typename Digraph::template NodeMap<OutArcIt> nedge;
1.73 + std::list<Arc> euler;
1.74 +
1.75 + public:
1.76 +
1.77 + ///Constructor
1.78 +
1.79 + ///\param _g A digraph.
1.80 + ///\param start The starting point of the tour. If it is not given
1.81 + /// the tour will start from the first node.
1.82 + DiEulerIt(const Digraph &_g,typename Digraph::Node start=INVALID)
1.83 + : g(_g), nedge(g)
1.84 + {
1.85 + if(start==INVALID) start=NodeIt(g);
1.86 + for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n);
1.87 + while(nedge[start]!=INVALID) {
1.88 + euler.push_back(nedge[start]);
1.89 + Node next=g.target(nedge[start]);
1.90 + ++nedge[start];
1.91 + start=next;
1.92 + }
1.93 + }
1.94 +
1.95 + ///Arc Conversion
1.96 + operator Arc() { return euler.empty()?INVALID:euler.front(); }
1.97 + bool operator==(Invalid) { return euler.empty(); }
1.98 + bool operator!=(Invalid) { return !euler.empty(); }
1.99 +
1.100 + ///Next arc of the tour
1.101 + DiEulerIt &operator++() {
1.102 + Node s=g.target(euler.front());
1.103 + euler.pop_front();
1.104 + //This produces a warning.Strange.
1.105 + //std::list<Arc>::iterator next=euler.begin();
1.106 + typename std::list<Arc>::iterator next=euler.begin();
1.107 + while(nedge[s]!=INVALID) {
1.108 + euler.insert(next,nedge[s]);
1.109 + Node n=g.target(nedge[s]);
1.110 + ++nedge[s];
1.111 + s=n;
1.112 + }
1.113 + return *this;
1.114 + }
1.115 + ///Postfix incrementation
1.116 +
1.117 + ///\warning This incrementation
1.118 + ///returns an \c Arc, not an \ref DiEulerIt, as one may
1.119 + ///expect.
1.120 + Arc operator++(int)
1.121 + {
1.122 + Arc e=*this;
1.123 + ++(*this);
1.124 + return e;
1.125 + }
1.126 + };
1.127 +
1.128 + ///Euler iterator for graphs.
1.129 +
1.130 + /// \ingroup graph_prop
1.131 + ///This iterator converts to the \c Arc (or \c Edge)
1.132 + ///type of the digraph and using
1.133 + ///operator ++, it provides an Euler tour of an undirected
1.134 + ///digraph (if there exists).
1.135 + ///
1.136 + ///For example
1.137 + ///if the given digraph if Euler (i.e it has only one nontrivial component
1.138 + ///and the degree of each node is even),
1.139 + ///the following code will print the arc IDs according to an
1.140 + ///Euler tour of \c g.
1.141 + ///\code
1.142 + /// for(EulerIt<ListGraph> e(g),e!=INVALID;++e) {
1.143 + /// std::cout << g.id(Edge(e)) << std::eol;
1.144 + /// }
1.145 + ///\endcode
1.146 + ///Although the iterator provides an Euler tour of an graph,
1.147 + ///it still returns Arcs in order to indicate the direction of the tour.
1.148 + ///(But Arc will convert to Edges, of course).
1.149 + ///
1.150 + ///If \c g is not Euler then the resulted tour will not be full or closed.
1.151 + ///\sa EulerIt
1.152 + ///\todo Test required
1.153 + template<class Digraph>
1.154 + class EulerIt
1.155 + {
1.156 + typedef typename Digraph::Node Node;
1.157 + typedef typename Digraph::NodeIt NodeIt;
1.158 + typedef typename Digraph::Arc Arc;
1.159 + typedef typename Digraph::Edge Edge;
1.160 + typedef typename Digraph::ArcIt ArcIt;
1.161 + typedef typename Digraph::OutArcIt OutArcIt;
1.162 + typedef typename Digraph::InArcIt InArcIt;
1.163 +
1.164 + const Digraph &g;
1.165 + typename Digraph::template NodeMap<OutArcIt> nedge;
1.166 + typename Digraph::template EdgeMap<bool> visited;
1.167 + std::list<Arc> euler;
1.168 +
1.169 + public:
1.170 +
1.171 + ///Constructor
1.172 +
1.173 + ///\param _g An graph.
1.174 + ///\param start The starting point of the tour. If it is not given
1.175 + /// the tour will start from the first node.
1.176 + EulerIt(const Digraph &_g,typename Digraph::Node start=INVALID)
1.177 + : g(_g), nedge(g), visited(g,false)
1.178 + {
1.179 + if(start==INVALID) start=NodeIt(g);
1.180 + for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n);
1.181 + while(nedge[start]!=INVALID) {
1.182 + euler.push_back(nedge[start]);
1.183 + visited[nedge[start]]=true;
1.184 + Node next=g.target(nedge[start]);
1.185 + ++nedge[start];
1.186 + start=next;
1.187 + while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start];
1.188 + }
1.189 + }
1.190 +
1.191 + ///Arc Conversion
1.192 + operator Arc() const { return euler.empty()?INVALID:euler.front(); }
1.193 + ///Arc Conversion
1.194 + operator Edge() const { return euler.empty()?INVALID:euler.front(); }
1.195 + ///\e
1.196 + bool operator==(Invalid) const { return euler.empty(); }
1.197 + ///\e
1.198 + bool operator!=(Invalid) const { return !euler.empty(); }
1.199 +
1.200 + ///Next arc of the tour
1.201 + EulerIt &operator++() {
1.202 + Node s=g.target(euler.front());
1.203 + euler.pop_front();
1.204 + typename std::list<Arc>::iterator next=euler.begin();
1.205 +
1.206 + while(nedge[s]!=INVALID) {
1.207 + while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s];
1.208 + if(nedge[s]==INVALID) break;
1.209 + else {
1.210 + euler.insert(next,nedge[s]);
1.211 + visited[nedge[s]]=true;
1.212 + Node n=g.target(nedge[s]);
1.213 + ++nedge[s];
1.214 + s=n;
1.215 + }
1.216 + }
1.217 + return *this;
1.218 + }
1.219 +
1.220 + ///Postfix incrementation
1.221 +
1.222 + ///\warning This incrementation
1.223 + ///returns an \c Arc, not an \ref EulerIt, as one may
1.224 + ///expect.
1.225 + Arc operator++(int)
1.226 + {
1.227 + Arc e=*this;
1.228 + ++(*this);
1.229 + return e;
1.230 + }
1.231 + };
1.232 +
1.233 +
1.234 + ///Checks if the graph is Euler
1.235 +
1.236 + /// \ingroup graph_prop
1.237 + ///Checks if the graph is Euler. It works for both directed and undirected
1.238 + ///graphs.
1.239 + ///\note By definition, a digraph is called \e Euler if
1.240 + ///and only if it is connected and the number of its incoming and outgoing
1.241 + ///arcs are the same for each node.
1.242 + ///Similarly, an undirected graph is called \e Euler if
1.243 + ///and only if it is connected and the number of incident arcs is even
1.244 + ///for each node. <em>Therefore, there are digraphs which are not Euler, but
1.245 + ///still have an Euler tour</em>.
1.246 + ///\todo Test required
1.247 + template<class Digraph>
1.248 +#ifdef DOXYGEN
1.249 + bool
1.250 +#else
1.251 + typename enable_if<UndirectedTagIndicator<Digraph>,bool>::type
1.252 + euler(const Digraph &g)
1.253 + {
1.254 + for(typename Digraph::NodeIt n(g);n!=INVALID;++n)
1.255 + if(countIncEdges(g,n)%2) return false;
1.256 + return connected(g);
1.257 + }
1.258 + template<class Digraph>
1.259 + typename disable_if<UndirectedTagIndicator<Digraph>,bool>::type
1.260 +#endif
1.261 + euler(const Digraph &g)
1.262 + {
1.263 + for(typename Digraph::NodeIt n(g);n!=INVALID;++n)
1.264 + if(countInArcs(g,n)!=countOutArcs(g,n)) return false;
1.265 + return connected(Undirector<const Digraph>(g));
1.266 + }
1.267 +
1.268 +}
1.269 +
1.270 +#endif