1.1 --- a/lemon/Makefile.am Mon Feb 23 11:58:39 2009 +0100
1.2 +++ b/lemon/Makefile.am Mon Feb 23 11:30:15 2009 +0000
1.3 @@ -64,6 +64,7 @@
1.4 lemon/edge_set.h \
1.5 lemon/elevator.h \
1.6 lemon/error.h \
1.7 + lemon/euler.h \
1.8 lemon/full_graph.h \
1.9 lemon/glpk.h \
1.10 lemon/graph_to_eps.h \
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/lemon/euler.h Mon Feb 23 11:30:15 2009 +0000
2.3 @@ -0,0 +1,267 @@
2.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
2.5 + *
2.6 + * This file is a part of LEMON, a generic C++ optimization library.
2.7 + *
2.8 + * Copyright (C) 2003-2009
2.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
2.11 + *
2.12 + * Permission to use, modify and distribute this software is granted
2.13 + * provided that this copyright notice appears in all copies. For
2.14 + * precise terms see the accompanying LICENSE file.
2.15 + *
2.16 + * This software is provided "AS IS" with no warranty of any kind,
2.17 + * express or implied, and with no claim as to its suitability for any
2.18 + * purpose.
2.19 + *
2.20 + */
2.21 +
2.22 +#ifndef LEMON_EULER_H
2.23 +#define LEMON_EULER_H
2.24 +
2.25 +#include<lemon/core.h>
2.26 +#include<lemon/adaptors.h>
2.27 +#include<lemon/connectivity.h>
2.28 +#include <list>
2.29 +
2.30 +/// \ingroup graph_prop
2.31 +/// \file
2.32 +/// \brief Euler tour
2.33 +///
2.34 +///This file provides an Euler tour iterator and ways to check
2.35 +///if a digraph is euler.
2.36 +
2.37 +
2.38 +namespace lemon {
2.39 +
2.40 + ///Euler iterator for digraphs.
2.41 +
2.42 + /// \ingroup graph_prop
2.43 + ///This iterator converts to the \c Arc type of the digraph and using
2.44 + ///operator ++, it provides an Euler tour of a \e directed
2.45 + ///graph (if there exists).
2.46 + ///
2.47 + ///For example
2.48 + ///if the given digraph is Euler (i.e it has only one nontrivial component
2.49 + ///and the in-degree is equal to the out-degree for all nodes),
2.50 + ///the following code will put the arcs of \c g
2.51 + ///to the vector \c et according to an
2.52 + ///Euler tour of \c g.
2.53 + ///\code
2.54 + /// std::vector<ListDigraph::Arc> et;
2.55 + /// for(DiEulerIt<ListDigraph> e(g),e!=INVALID;++e)
2.56 + /// et.push_back(e);
2.57 + ///\endcode
2.58 + ///If \c g is not Euler then the resulted tour will not be full or closed.
2.59 + ///\sa EulerIt
2.60 + ///\todo Test required
2.61 + template<class Digraph>
2.62 + class DiEulerIt
2.63 + {
2.64 + typedef typename Digraph::Node Node;
2.65 + typedef typename Digraph::NodeIt NodeIt;
2.66 + typedef typename Digraph::Arc Arc;
2.67 + typedef typename Digraph::ArcIt ArcIt;
2.68 + typedef typename Digraph::OutArcIt OutArcIt;
2.69 + typedef typename Digraph::InArcIt InArcIt;
2.70 +
2.71 + const Digraph &g;
2.72 + typename Digraph::template NodeMap<OutArcIt> nedge;
2.73 + std::list<Arc> euler;
2.74 +
2.75 + public:
2.76 +
2.77 + ///Constructor
2.78 +
2.79 + ///\param _g A digraph.
2.80 + ///\param start The starting point of the tour. If it is not given
2.81 + /// the tour will start from the first node.
2.82 + DiEulerIt(const Digraph &_g,typename Digraph::Node start=INVALID)
2.83 + : g(_g), nedge(g)
2.84 + {
2.85 + if(start==INVALID) start=NodeIt(g);
2.86 + for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n);
2.87 + while(nedge[start]!=INVALID) {
2.88 + euler.push_back(nedge[start]);
2.89 + Node next=g.target(nedge[start]);
2.90 + ++nedge[start];
2.91 + start=next;
2.92 + }
2.93 + }
2.94 +
2.95 + ///Arc Conversion
2.96 + operator Arc() { return euler.empty()?INVALID:euler.front(); }
2.97 + bool operator==(Invalid) { return euler.empty(); }
2.98 + bool operator!=(Invalid) { return !euler.empty(); }
2.99 +
2.100 + ///Next arc of the tour
2.101 + DiEulerIt &operator++() {
2.102 + Node s=g.target(euler.front());
2.103 + euler.pop_front();
2.104 + //This produces a warning.Strange.
2.105 + //std::list<Arc>::iterator next=euler.begin();
2.106 + typename std::list<Arc>::iterator next=euler.begin();
2.107 + while(nedge[s]!=INVALID) {
2.108 + euler.insert(next,nedge[s]);
2.109 + Node n=g.target(nedge[s]);
2.110 + ++nedge[s];
2.111 + s=n;
2.112 + }
2.113 + return *this;
2.114 + }
2.115 + ///Postfix incrementation
2.116 +
2.117 + ///\warning This incrementation
2.118 + ///returns an \c Arc, not an \ref DiEulerIt, as one may
2.119 + ///expect.
2.120 + Arc operator++(int)
2.121 + {
2.122 + Arc e=*this;
2.123 + ++(*this);
2.124 + return e;
2.125 + }
2.126 + };
2.127 +
2.128 + ///Euler iterator for graphs.
2.129 +
2.130 + /// \ingroup graph_prop
2.131 + ///This iterator converts to the \c Arc (or \c Edge)
2.132 + ///type of the digraph and using
2.133 + ///operator ++, it provides an Euler tour of an undirected
2.134 + ///digraph (if there exists).
2.135 + ///
2.136 + ///For example
2.137 + ///if the given digraph if Euler (i.e it has only one nontrivial component
2.138 + ///and the degree of each node is even),
2.139 + ///the following code will print the arc IDs according to an
2.140 + ///Euler tour of \c g.
2.141 + ///\code
2.142 + /// for(EulerIt<ListGraph> e(g),e!=INVALID;++e) {
2.143 + /// std::cout << g.id(Edge(e)) << std::eol;
2.144 + /// }
2.145 + ///\endcode
2.146 + ///Although the iterator provides an Euler tour of an graph,
2.147 + ///it still returns Arcs in order to indicate the direction of the tour.
2.148 + ///(But Arc will convert to Edges, of course).
2.149 + ///
2.150 + ///If \c g is not Euler then the resulted tour will not be full or closed.
2.151 + ///\sa EulerIt
2.152 + ///\todo Test required
2.153 + template<class Digraph>
2.154 + class EulerIt
2.155 + {
2.156 + typedef typename Digraph::Node Node;
2.157 + typedef typename Digraph::NodeIt NodeIt;
2.158 + typedef typename Digraph::Arc Arc;
2.159 + typedef typename Digraph::Edge Edge;
2.160 + typedef typename Digraph::ArcIt ArcIt;
2.161 + typedef typename Digraph::OutArcIt OutArcIt;
2.162 + typedef typename Digraph::InArcIt InArcIt;
2.163 +
2.164 + const Digraph &g;
2.165 + typename Digraph::template NodeMap<OutArcIt> nedge;
2.166 + typename Digraph::template EdgeMap<bool> visited;
2.167 + std::list<Arc> euler;
2.168 +
2.169 + public:
2.170 +
2.171 + ///Constructor
2.172 +
2.173 + ///\param _g An graph.
2.174 + ///\param start The starting point of the tour. If it is not given
2.175 + /// the tour will start from the first node.
2.176 + EulerIt(const Digraph &_g,typename Digraph::Node start=INVALID)
2.177 + : g(_g), nedge(g), visited(g,false)
2.178 + {
2.179 + if(start==INVALID) start=NodeIt(g);
2.180 + for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n);
2.181 + while(nedge[start]!=INVALID) {
2.182 + euler.push_back(nedge[start]);
2.183 + visited[nedge[start]]=true;
2.184 + Node next=g.target(nedge[start]);
2.185 + ++nedge[start];
2.186 + start=next;
2.187 + while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start];
2.188 + }
2.189 + }
2.190 +
2.191 + ///Arc Conversion
2.192 + operator Arc() const { return euler.empty()?INVALID:euler.front(); }
2.193 + ///Arc Conversion
2.194 + operator Edge() const { return euler.empty()?INVALID:euler.front(); }
2.195 + ///\e
2.196 + bool operator==(Invalid) const { return euler.empty(); }
2.197 + ///\e
2.198 + bool operator!=(Invalid) const { return !euler.empty(); }
2.199 +
2.200 + ///Next arc of the tour
2.201 + EulerIt &operator++() {
2.202 + Node s=g.target(euler.front());
2.203 + euler.pop_front();
2.204 + typename std::list<Arc>::iterator next=euler.begin();
2.205 +
2.206 + while(nedge[s]!=INVALID) {
2.207 + while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s];
2.208 + if(nedge[s]==INVALID) break;
2.209 + else {
2.210 + euler.insert(next,nedge[s]);
2.211 + visited[nedge[s]]=true;
2.212 + Node n=g.target(nedge[s]);
2.213 + ++nedge[s];
2.214 + s=n;
2.215 + }
2.216 + }
2.217 + return *this;
2.218 + }
2.219 +
2.220 + ///Postfix incrementation
2.221 +
2.222 + ///\warning This incrementation
2.223 + ///returns an \c Arc, not an \ref EulerIt, as one may
2.224 + ///expect.
2.225 + Arc operator++(int)
2.226 + {
2.227 + Arc e=*this;
2.228 + ++(*this);
2.229 + return e;
2.230 + }
2.231 + };
2.232 +
2.233 +
2.234 + ///Checks if the graph is Euler
2.235 +
2.236 + /// \ingroup graph_prop
2.237 + ///Checks if the graph is Euler. It works for both directed and undirected
2.238 + ///graphs.
2.239 + ///\note By definition, a digraph is called \e Euler if
2.240 + ///and only if it is connected and the number of its incoming and outgoing
2.241 + ///arcs are the same for each node.
2.242 + ///Similarly, an undirected graph is called \e Euler if
2.243 + ///and only if it is connected and the number of incident arcs is even
2.244 + ///for each node. <em>Therefore, there are digraphs which are not Euler, but
2.245 + ///still have an Euler tour</em>.
2.246 + ///\todo Test required
2.247 + template<class Digraph>
2.248 +#ifdef DOXYGEN
2.249 + bool
2.250 +#else
2.251 + typename enable_if<UndirectedTagIndicator<Digraph>,bool>::type
2.252 + euler(const Digraph &g)
2.253 + {
2.254 + for(typename Digraph::NodeIt n(g);n!=INVALID;++n)
2.255 + if(countIncEdges(g,n)%2) return false;
2.256 + return connected(g);
2.257 + }
2.258 + template<class Digraph>
2.259 + typename disable_if<UndirectedTagIndicator<Digraph>,bool>::type
2.260 +#endif
2.261 + euler(const Digraph &g)
2.262 + {
2.263 + for(typename Digraph::NodeIt n(g);n!=INVALID;++n)
2.264 + if(countInArcs(g,n)!=countOutArcs(g,n)) return false;
2.265 + return connected(Undirector<const Digraph>(g));
2.266 + }
2.267 +
2.268 +}
2.269 +
2.270 +#endif