Changeset 639:2ebfdb89ec66 in lemon for lemon/euler.h
 Timestamp:
 04/15/09 11:47:19 (12 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/euler.h
r638 r639 27 27 /// \ingroup graph_properties 28 28 /// \file 29 /// \brief Euler tour 29 /// \brief Euler tour iterators and a function for checking the \e Eulerian 30 /// property. 30 31 /// 31 ///This file provides an Euler tour iterator and ways to check 32 ///if a digraph is euler. 33 32 ///This file provides Euler tour iterators and a function to check 33 ///if a (di)graph is \e Eulerian. 34 34 35 35 namespace lemon { 36 36 37 ///Euler iterator for digraphs. 38 39 /// \ingroup graph_properties 40 ///This iterator converts to the \c Arc type of the digraph and using 41 ///operator ++, it provides an Euler tour of a \e directed 42 ///graph (if there exists). 43 /// 44 ///For example 45 ///if the given digraph is Euler (i.e it has only one nontrivial component 46 ///and the indegree is equal to the outdegree for all nodes), 47 ///the following code will put the arcs of \c g 48 ///to the vector \c et according to an 49 ///Euler tour of \c g. 37 ///Euler tour iterator for digraphs. 38 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. 42 /// 43 ///For example, if the given digraph has an Euler tour (i.e it has only one 44 ///nontrivial component and the indegree is equal to the outdegree 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. 50 47 ///\code 51 48 /// std::vector<ListDigraph::Arc> et; 52 /// for(DiEulerIt<ListDigraph> e(g) ,e!=INVALID;++e)49 /// for(DiEulerIt<ListDigraph> e(g); e!=INVALID; ++e) 53 50 /// et.push_back(e); 54 51 ///\endcode 55 ///If \c g is not Euler then the resulted tour will not be full or closed. 52 ///If \c g has no Euler tour, then the resulted walk will not be closed 53 ///or not contain all arcs. 56 54 ///\sa EulerIt 57 55 template<typename GR> … … 66 64 67 65 const GR &g; 68 typename GR::template NodeMap<OutArcIt> n edge;66 typename GR::template NodeMap<OutArcIt> narc; 69 67 std::list<Arc> euler; 70 68 … … 73 71 ///Constructor 74 72 73 ///Constructor. 75 74 ///\param gr A digraph. 76 ///\param start The starting point of the tour. If it is not given 77 /// the tour will start from the first node.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. 78 77 DiEulerIt(const GR &gr, typename GR::Node start = INVALID) 79 : g(gr), n edge(g)78 : g(gr), narc(g) 80 79 { 81 80 if (start==INVALID) { … … 85 84 } 86 85 if (start!=INVALID) { 87 for (NodeIt n(g); n!=INVALID; ++n) n edge[n]=OutArcIt(g,n);88 while (n edge[start]!=INVALID) {89 euler.push_back(n edge[start]);90 Node next=g.target(n edge[start]);91 ++n edge[start];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]; 92 91 start=next; 93 92 } … … 95 94 } 96 95 97 ///Arc Conversion96 ///Arc conversion 98 97 operator Arc() { return euler.empty()?INVALID:euler.front(); } 98 ///Compare with \c INVALID 99 99 bool operator==(Invalid) { return euler.empty(); } 100 ///Compare with \c INVALID 100 101 bool operator!=(Invalid) { return !euler.empty(); } 101 102 102 103 ///Next arc of the tour 104 105 ///Next arc of the tour 106 /// 103 107 DiEulerIt &operator++() { 104 108 Node s=g.target(euler.front()); 105 109 euler.pop_front(); 106 //This produces a warning.Strange.107 //std::list<Arc>::iterator next=euler.begin();108 110 typename std::list<Arc>::iterator next=euler.begin(); 109 while(n edge[s]!=INVALID) {110 euler.insert(next,n edge[s]);111 Node n=g.target(n edge[s]);112 ++n edge[s];111 while(narc[s]!=INVALID) { 112 euler.insert(next,narc[s]); 113 Node n=g.target(narc[s]); 114 ++narc[s]; 113 115 s=n; 114 116 } … … 117 119 ///Postfix incrementation 118 120 121 /// Postfix incrementation. 122 /// 119 123 ///\warning This incrementation 120 ///returns an \c Arc, not a n\ref DiEulerIt, as one may124 ///returns an \c Arc, not a \ref DiEulerIt, as one may 121 125 ///expect. 122 126 Arc operator++(int) … … 128 132 }; 129 133 130 ///Euler iterator for graphs.134 ///Euler tour iterator for graphs. 131 135 132 136 /// \ingroup graph_properties 133 ///This iterator converts to the \c Arc (or \c Edge) 134 ///type of the digraph and using 135 ///operator ++, it provides an Euler tour of an undirected 136 ///digraph (if there exists). 137 /// 138 ///For example 139 ///if the given digraph if Euler (i.e it has only one nontrivial component 140 ///and the degree of each node is even), 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. 140 /// 141 ///For example, if the given graph has an Euler tour (i.e it has only one 142 ///nontrivial component and the degree of each node is even), 141 143 ///the following code will print the arc IDs according to an 142 144 ///Euler tour of \c g. 143 145 ///\code 144 /// for(EulerIt<ListGraph> e(g) ,e!=INVALID;++e) {146 /// for(EulerIt<ListGraph> e(g); e!=INVALID; ++e) { 145 147 /// std::cout << g.id(Edge(e)) << std::eol; 146 148 /// } 147 149 ///\endcode 148 ///Although th e iterator provides an Euler tour of an graph,149 /// it still returns Arcs in order to indicate the direction of the tour.150 ///(But Arc will convert to Edges, of course).151 /// 152 ///If \c g is not Euler then the resulted tour will not be full or closed.153 /// \sa EulerIt150 ///Although this iterator is for undirected graphs, it still returns 151 ///arcs in order to indicate the direction of the tour. 152 ///(But arcs convert to edges, of course.) 153 /// 154 ///If \c g has no Euler tour, then the resulted walk will not be closed 155 ///or not contain all edges. 154 156 template<typename GR> 155 157 class EulerIt … … 164 166 165 167 const GR &g; 166 typename GR::template NodeMap<OutArcIt> n edge;168 typename GR::template NodeMap<OutArcIt> narc; 167 169 typename GR::template EdgeMap<bool> visited; 168 170 std::list<Arc> euler; … … 172 174 ///Constructor 173 175 174 ///\param gr An graph. 175 ///\param start The starting point of the tour. If it is not given 176 /// the tour will start from the first node. 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. 177 180 EulerIt(const GR &gr, typename GR::Node start = INVALID) 178 : g(gr), n edge(g), visited(g, false)181 : g(gr), narc(g), visited(g, false) 179 182 { 180 183 if (start==INVALID) { … … 184 187 } 185 188 if (start!=INVALID) { 186 for (NodeIt n(g); n!=INVALID; ++n) n edge[n]=OutArcIt(g,n);187 while(n edge[start]!=INVALID) {188 euler.push_back(n edge[start]);189 visited[n edge[start]]=true;190 Node next=g.target(n edge[start]);191 ++n edge[start];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]; 192 195 start=next; 193 while(n edge[start]!=INVALID && visited[nedge[start]]) ++nedge[start];196 while(narc[start]!=INVALID && visited[narc[start]]) ++narc[start]; 194 197 } 195 198 } 196 199 } 197 200 198 ///Arc Conversion201 ///Arc conversion 199 202 operator Arc() const { return euler.empty()?INVALID:euler.front(); } 200 /// Arc Conversion203 ///Edge conversion 201 204 operator Edge() const { return euler.empty()?INVALID:euler.front(); } 202 /// \e205 ///Compare with \c INVALID 203 206 bool operator==(Invalid) const { return euler.empty(); } 204 /// \e207 ///Compare with \c INVALID 205 208 bool operator!=(Invalid) const { return !euler.empty(); } 206 209 207 210 ///Next arc of the tour 211 212 ///Next arc of the tour 213 /// 208 214 EulerIt &operator++() { 209 215 Node s=g.target(euler.front()); 210 216 euler.pop_front(); 211 217 typename std::list<Arc>::iterator next=euler.begin(); 212 213 while(nedge[s]!=INVALID) { 214 while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s]; 215 if(nedge[s]==INVALID) break; 218 while(narc[s]!=INVALID) { 219 while(narc[s]!=INVALID && visited[narc[s]]) ++narc[s]; 220 if(narc[s]==INVALID) break; 216 221 else { 217 euler.insert(next,n edge[s]);218 visited[n edge[s]]=true;219 Node n=g.target(n edge[s]);220 ++n edge[s];222 euler.insert(next,narc[s]); 223 visited[narc[s]]=true; 224 Node n=g.target(narc[s]); 225 ++narc[s]; 221 226 s=n; 222 227 } … … 227 232 ///Postfix incrementation 228 233 229 ///\warning This incrementation 230 ///returns an \c Arc, not an \ref EulerIt, as one may 231 ///expect. 234 /// Postfix incrementation. 235 /// 236 ///\warning This incrementation returns an \c Arc (which converts to 237 ///an \c Edge), not an \ref EulerIt, as one may expect. 232 238 Arc operator++(int) 233 239 { … … 239 245 240 246 241 ///Check s if the graph isEulerian247 ///Check if the given graph is \e Eulerian 242 248 243 249 /// \ingroup graph_properties 244 ///Checks if the graph is Eulerian. It works for both directed and undirected 245 ///graphs. 246 ///\note By definition, a digraph is called \e Eulerian if 247 ///and only if it is connected and the number of its incoming and outgoing 250 ///This function checks if the given graph is \e Eulerian. 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 248 255 ///arcs are the same for each node. 249 256 ///Similarly, an undirected graph is called \e Eulerian if 250 ///and only if it is connected and the number of incident arcs is even 251 ///for each node. <em>Therefore, there are digraphs which are not Eulerian, 252 ///but still have an Euler tour</em>. 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 253 264 template<typename GR> 254 265 #ifdef DOXYGEN … … 269 280 for(typename GR::NodeIt n(g);n!=INVALID;++n) 270 281 if(countInArcs(g,n)!=countOutArcs(g,n)) return false; 271 return connected( Undirector<const GR>(g));282 return connected(undirector(g)); 272 283 } 273 284
Note: See TracChangeset
for help on using the changeset viewer.