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