euler.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  *
00003  * This file is a part of LEMON, a generic C++ optimization library
00004  *
00005  * Copyright (C) 2003-2006
00006  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00007  * (Egervary Research Group on Combinatorial Optimization, EGRES).
00008  *
00009  * Permission to use, modify and distribute this software is granted
00010  * provided that this copyright notice appears in all copies. For
00011  * precise terms see the accompanying LICENSE file.
00012  *
00013  * This software is provided "AS IS" with no warranty of any kind,
00014  * express or implied, and with no claim as to its suitability for any
00015  * purpose.
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       //This produces a warning.Strange.
00095       //std::list<Edge>::iterator next=euler.begin();
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 }

Generated on Fri Feb 3 18:36:50 2006 for LEMON by  doxygen 1.4.6