1.1 --- a/lemon/euler.h Fri Nov 18 11:17:08 2005 +0000
1.2 +++ b/lemon/euler.h Mon Nov 21 09:08:16 2005 +0000
1.3 @@ -1,5 +1,5 @@
1.4 /* -*- C++ -*-
1.5 - * lemon/topology.h - Part of LEMON, a generic C++ optimization library
1.6 + * lemon/euler.h - Part of LEMON, a generic C++ optimization library
1.7 *
1.8 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.9 * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.10 @@ -14,6 +14,7 @@
1.11 *
1.12 */
1.13 #include<lemon/invalid.h>
1.14 +#include<lemon/topology.h>
1.15 #include <list>
1.16
1.17 /// \ingroup topology
1.18 @@ -26,7 +27,7 @@
1.19
1.20 namespace lemon {
1.21
1.22 - ///Euler iterator in directed graphs.
1.23 + ///Euler iterator for directed graphs.
1.24
1.25 /// \ingroup topology
1.26 ///This iterator converts to the \c Edge type of the graph and using
1.27 @@ -111,31 +112,133 @@
1.28 }
1.29 };
1.30
1.31 + ///Euler iterator for undirected graphs.
1.32 +
1.33 + /// \ingroup topology
1.34 + ///This iterator converts to the \c Edge type of the graph and using
1.35 + ///operator ++ it provides an Euler tour of the graph (if there exists).
1.36 + ///
1.37 + ///For example
1.38 + ///if the given graph if Euler (i.e it has only one nontrivial component
1.39 + ///and the degree of each node is even),
1.40 + ///the following code will print the edge IDs according to an
1.41 + ///Euler tour of \c g.
1.42 + ///\code
1.43 + /// for(UndirEulerIt<UndirListGraph> e(g),e!=INVALID;++e) {
1.44 + /// std::cout << g.id(UndirEdge(e)) << std::eol;
1.45 + /// }
1.46 + ///\endcode
1.47 + ///Although the iterator provides an Euler tour of an undirected graph,
1.48 + ///in order to indicate the direction of the tour, UndirEulerIt
1.49 + ///returns directed edges (that convert to the undirected ones, of course).
1.50 + ///
1.51 + ///If \c g is not Euler then the resulted tour will not be full or closed.
1.52 + ///\todo Test required
1.53 + template<class Graph>
1.54 + class UndirEulerIt
1.55 + {
1.56 + typedef typename Graph::Node Node;
1.57 + typedef typename Graph::NodeIt NodeIt;
1.58 + typedef typename Graph::Edge Edge;
1.59 + typedef typename Graph::EdgeIt EdgeIt;
1.60 + typedef typename Graph::OutEdgeIt OutEdgeIt;
1.61 + typedef typename Graph::InEdgeIt InEdgeIt;
1.62 +
1.63 + const Graph &g;
1.64 + typename Graph::NodeMap<OutEdgeIt> nedge;
1.65 + typename Graph::UndirEdgeMap<bool> visited;
1.66 + std::list<Edge> euler;
1.67 +
1.68 + public:
1.69 +
1.70 + ///Constructor
1.71 +
1.72 + ///\param _g An undirected graph.
1.73 + ///\param start The starting point of the tour. If it is not given
1.74 + /// the tour will start from the first node.
1.75 + UndirEulerIt(const Graph &_g,typename Graph::Node start=INVALID)
1.76 + : g(_g), nedge(g), visited(g,false)
1.77 + {
1.78 + if(start==INVALID) start=NodeIt(g);
1.79 + for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutEdgeIt(g,n);
1.80 + while(nedge[start]!=INVALID) {
1.81 + euler.push_back(nedge[start]);
1.82 + Node next=g.target(nedge[start]);
1.83 + ++nedge[start];
1.84 + start=next; while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start];
1.85 + }
1.86 + }
1.87 +
1.88 + ///Edge Conversion
1.89 + operator Edge() { return euler.empty()?INVALID:euler.front(); }
1.90 + bool operator==(Invalid) { return euler.empty(); }
1.91 + bool operator!=(Invalid) { return !euler.empty(); }
1.92 +
1.93 + ///Next edge of the tour
1.94 + UndirEulerIt &operator++() {
1.95 + Node s=g.target(euler.front());
1.96 + euler.pop_front();
1.97 + typename std::list<Edge>::iterator next=euler.begin();
1.98 +
1.99 + while(nedge[s]!=INVALID) {
1.100 + while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s];
1.101 + if(nedge[s]==INVALID) break;
1.102 + else {
1.103 + euler.insert(next,nedge[s]);
1.104 + Node n=g.target(nedge[s]);
1.105 + ++nedge[s];
1.106 + s=n;
1.107 + }
1.108 + }
1.109 + return *this;
1.110 + }
1.111 +
1.112 + ///Postfix incrementation
1.113 +
1.114 + ///\warning This incrementation
1.115 + ///returns an \c Edge, not an \ref UndirEulerIt, as one may
1.116 + ///expect.
1.117 + Edge operator++(int)
1.118 + {
1.119 + Edge e=*this;
1.120 + ++(*this);
1.121 + return e;
1.122 + }
1.123 + };
1.124 +
1.125 +
1.126 ///Checks if the graph is Euler
1.127
1.128 - /// \ingroup gutils
1.129 + /// \ingroup topology
1.130 ///Checks if the graph is Euler. It works for both directed and
1.131 ///undirected graphs.
1.132 + ///\note By definition, a directed graph is called \e Euler if
1.133 + ///and only if connected and the number of it is incoming and outgoing edges
1.134 + ///are the same for each node.
1.135 + ///Similarly, an undirected graph is called \e Euler if
1.136 + ///and only if it is connected and the number of incident edges is even
1.137 + ///for each node. <em>Therefore, there are graphs which are not Euler, but
1.138 + ///still have an Euler tour</em>.
1.139 ///\todo Test required
1.140 template<class Graph>
1.141 #ifdef DOXYGEN
1.142 bool
1.143 #else
1.144 typename enable_if<typename Graph::UndirTag,bool>::type
1.145 + euler(const Graph &g)
1.146 + {
1.147 + for(typename Graph::NodeIt n(g);n!=INVALID;++n)
1.148 + if(countIncEdges(g,n)%2) return false;
1.149 + return connected(g);
1.150 + }
1.151 + template<class Graph>
1.152 + typename disable_if<typename Graph::UndirTag,bool>::type
1.153 #endif
1.154 euler(const Graph &g)
1.155 {
1.156 for(typename Graph::NodeIt n(g);n!=INVALID;++n)
1.157 - if(countIncEdges(g,n)%2) return false;
1.158 - return true;
1.159 - }
1.160 - template<class Graph>
1.161 - typename disable_if<typename Graph::UndirTag,bool>::type
1.162 - euler(const Graph &g)
1.163 - {
1.164 - for(typename Graph::NodeIt n(g);n!=INVALID;++n)
1.165 if(countInEdges(g,n)!=countOutEdges(g,n)) return false;
1.166 - return true;
1.167 + return connected(g);
1.168 }
1.169
1.170 }