00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #include<lemon/invalid.h>
00020 #include<lemon/topology.h>
00021 #include <list>
00022
00029
00030
00031 namespace lemon {
00032
00034
00051 template<class Graph>
00052 class EulerIt
00053 {
00054 typedef typename Graph::Node Node;
00055 typedef typename Graph::NodeIt NodeIt;
00056 typedef typename Graph::Edge Edge;
00057 typedef typename Graph::EdgeIt EdgeIt;
00058 typedef typename Graph::OutEdgeIt OutEdgeIt;
00059 typedef typename Graph::InEdgeIt InEdgeIt;
00060
00061 const Graph &g;
00062 typename Graph::NodeMap<OutEdgeIt> nedge;
00063 std::list<Edge> euler;
00064
00065 public:
00066
00068
00072 EulerIt(const Graph &_g,typename Graph::Node start=INVALID)
00073 : g(_g), nedge(g)
00074 {
00075 if(start==INVALID) start=NodeIt(g);
00076 for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutEdgeIt(g,n);
00077 while(nedge[start]!=INVALID) {
00078 euler.push_back(nedge[start]);
00079 Node next=g.target(nedge[start]);
00080 ++nedge[start];
00081 start=next;
00082 }
00083 }
00084
00086 operator Edge() { return euler.empty()?INVALID:euler.front(); }
00087 bool operator==(Invalid) { return euler.empty(); }
00088 bool operator!=(Invalid) { return !euler.empty(); }
00089
00091 EulerIt &operator++() {
00092 Node s=g.target(euler.front());
00093 euler.pop_front();
00094
00095
00096 typename std::list<Edge>::iterator next=euler.begin();
00097 while(nedge[s]!=INVALID) {
00098 euler.insert(next,nedge[s]);
00099 Node n=g.target(nedge[s]);
00100 ++nedge[s];
00101 s=n;
00102 }
00103 return *this;
00104 }
00106
00110 Edge operator++(int)
00111 {
00112 Edge e=*this;
00113 ++(*this);
00114 return e;
00115 }
00116 };
00117
00119
00140 template<class Graph>
00141 class UEulerIt
00142 {
00143 typedef typename Graph::Node Node;
00144 typedef typename Graph::NodeIt NodeIt;
00145 typedef typename Graph::Edge Edge;
00146 typedef typename Graph::EdgeIt EdgeIt;
00147 typedef typename Graph::OutEdgeIt OutEdgeIt;
00148 typedef typename Graph::InEdgeIt InEdgeIt;
00149
00150 const Graph &g;
00151 typename Graph::NodeMap<OutEdgeIt> nedge;
00152 typename Graph::UEdgeMap<bool> visited;
00153 std::list<Edge> euler;
00154
00155 public:
00156
00158
00162 UEulerIt(const Graph &_g,typename Graph::Node start=INVALID)
00163 : g(_g), nedge(g), visited(g,false)
00164 {
00165 if(start==INVALID) start=NodeIt(g);
00166 for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutEdgeIt(g,n);
00167 while(nedge[start]!=INVALID) {
00168 euler.push_back(nedge[start]);
00169 Node next=g.target(nedge[start]);
00170 ++nedge[start];
00171 start=next; while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start];
00172 }
00173 }
00174
00176 operator Edge() { return euler.empty()?INVALID:euler.front(); }
00177 bool operator==(Invalid) { return euler.empty(); }
00178 bool operator!=(Invalid) { return !euler.empty(); }
00179
00181 UEulerIt &operator++() {
00182 Node s=g.target(euler.front());
00183 euler.pop_front();
00184 typename std::list<Edge>::iterator next=euler.begin();
00185
00186 while(nedge[s]!=INVALID) {
00187 while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s];
00188 if(nedge[s]==INVALID) break;
00189 else {
00190 euler.insert(next,nedge[s]);
00191 Node n=g.target(nedge[s]);
00192 ++nedge[s];
00193 s=n;
00194 }
00195 }
00196 return *this;
00197 }
00198
00200
00204 Edge operator++(int)
00205 {
00206 Edge e=*this;
00207 ++(*this);
00208 return e;
00209 }
00210 };
00211
00212
00214
00226 template<class Graph>
00227 #ifdef DOXYGEN
00228 bool
00229 #else
00230 typename enable_if<typename Graph::UTag,bool>::type
00231 euler(const Graph &g)
00232 {
00233 for(typename Graph::NodeIt n(g);n!=INVALID;++n)
00234 if(countIncEdges(g,n)%2) return false;
00235 return connected(g);
00236 }
00237 template<class Graph>
00238 typename disable_if<typename Graph::UTag,bool>::type
00239 #endif
00240 euler(const Graph &g)
00241 {
00242 for(typename Graph::NodeIt n(g);n!=INVALID;++n)
00243 if(countInEdges(g,n)!=countOutEdges(g,n)) return false;
00244 return connected(g);
00245 }
00246
00247 }