Changeset 1818:8f9905c4e1c1 in lemon-0.x
- Timestamp:
- 11/21/05 10:08:16 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2367
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/euler.h
r1803 r1818 1 1 /* -*- C++ -*- 2 * lemon/ topology.h - Part of LEMON, a generic C++ optimization library2 * lemon/euler.h - Part of LEMON, a generic C++ optimization library 3 3 * 4 4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport … … 15 15 */ 16 16 #include<lemon/invalid.h> 17 #include<lemon/topology.h> 17 18 #include <list> 18 19 … … 27 28 namespace lemon { 28 29 29 ///Euler iterator indirected graphs.30 ///Euler iterator for directed graphs. 30 31 31 32 /// \ingroup topology … … 112 113 }; 113 114 115 ///Euler iterator for undirected graphs. 116 117 /// \ingroup topology 118 ///This iterator converts to the \c Edge type of the graph and using 119 ///operator ++ it provides an Euler tour of the graph (if there exists). 120 /// 121 ///For example 122 ///if the given graph if Euler (i.e it has only one nontrivial component 123 ///and the degree of each node is even), 124 ///the following code will print the edge IDs according to an 125 ///Euler tour of \c g. 126 ///\code 127 /// for(UndirEulerIt<UndirListGraph> e(g),e!=INVALID;++e) { 128 /// std::cout << g.id(UndirEdge(e)) << std::eol; 129 /// } 130 ///\endcode 131 ///Although the iterator provides an Euler tour of an undirected graph, 132 ///in order to indicate the direction of the tour, UndirEulerIt 133 ///returns directed edges (that convert to the undirected ones, of course). 134 /// 135 ///If \c g is not Euler then the resulted tour will not be full or closed. 136 ///\todo Test required 137 template<class Graph> 138 class UndirEulerIt 139 { 140 typedef typename Graph::Node Node; 141 typedef typename Graph::NodeIt NodeIt; 142 typedef typename Graph::Edge Edge; 143 typedef typename Graph::EdgeIt EdgeIt; 144 typedef typename Graph::OutEdgeIt OutEdgeIt; 145 typedef typename Graph::InEdgeIt InEdgeIt; 146 147 const Graph &g; 148 typename Graph::NodeMap<OutEdgeIt> nedge; 149 typename Graph::UndirEdgeMap<bool> visited; 150 std::list<Edge> euler; 151 152 public: 153 154 ///Constructor 155 156 ///\param _g An undirected graph. 157 ///\param start The starting point of the tour. If it is not given 158 /// the tour will start from the first node. 159 UndirEulerIt(const Graph &_g,typename Graph::Node start=INVALID) 160 : g(_g), nedge(g), visited(g,false) 161 { 162 if(start==INVALID) start=NodeIt(g); 163 for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutEdgeIt(g,n); 164 while(nedge[start]!=INVALID) { 165 euler.push_back(nedge[start]); 166 Node next=g.target(nedge[start]); 167 ++nedge[start]; 168 start=next; while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start]; 169 } 170 } 171 172 ///Edge Conversion 173 operator Edge() { return euler.empty()?INVALID:euler.front(); } 174 bool operator==(Invalid) { return euler.empty(); } 175 bool operator!=(Invalid) { return !euler.empty(); } 176 177 ///Next edge of the tour 178 UndirEulerIt &operator++() { 179 Node s=g.target(euler.front()); 180 euler.pop_front(); 181 typename std::list<Edge>::iterator next=euler.begin(); 182 183 while(nedge[s]!=INVALID) { 184 while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s]; 185 if(nedge[s]==INVALID) break; 186 else { 187 euler.insert(next,nedge[s]); 188 Node n=g.target(nedge[s]); 189 ++nedge[s]; 190 s=n; 191 } 192 } 193 return *this; 194 } 195 196 ///Postfix incrementation 197 198 ///\warning This incrementation 199 ///returns an \c Edge, not an \ref UndirEulerIt, as one may 200 ///expect. 201 Edge operator++(int) 202 { 203 Edge e=*this; 204 ++(*this); 205 return e; 206 } 207 }; 208 209 114 210 ///Checks if the graph is Euler 115 211 116 /// \ingroup gutils212 /// \ingroup topology 117 213 ///Checks if the graph is Euler. It works for both directed and 118 214 ///undirected graphs. 215 ///\note By definition, a directed graph is called \e Euler if 216 ///and only if connected and the number of it is incoming and outgoing edges 217 ///are the same for each node. 218 ///Similarly, an undirected graph is called \e Euler if 219 ///and only if it is connected and the number of incident edges is even 220 ///for each node. <em>Therefore, there are graphs which are not Euler, but 221 ///still have an Euler tour</em>. 119 222 ///\todo Test required 120 223 template<class Graph> … … 123 226 #else 124 227 typename enable_if<typename Graph::UndirTag,bool>::type 228 euler(const Graph &g) 229 { 230 for(typename Graph::NodeIt n(g);n!=INVALID;++n) 231 if(countIncEdges(g,n)%2) return false; 232 return connected(g); 233 } 234 template<class Graph> 235 typename disable_if<typename Graph::UndirTag,bool>::type 125 236 #endif 126 237 euler(const Graph &g) 127 238 { 128 239 for(typename Graph::NodeIt n(g);n!=INVALID;++n) 129 if(countIncEdges(g,n)%2) return false;130 return true;131 }132 template<class Graph>133 typename disable_if<typename Graph::UndirTag,bool>::type134 euler(const Graph &g)135 {136 for(typename Graph::NodeIt n(g);n!=INVALID;++n)137 240 if(countInEdges(g,n)!=countOutEdges(g,n)) return false; 138 return true;241 return connected(g); 139 242 } 140 243
Note: See TracChangeset
for help on using the changeset viewer.