Changeset 606:c5fd2d996909 in lemon for lemon/euler.h
 Timestamp:
 03/29/09 23:08:20 (10 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/euler.h
r569 r606 55 55 ///If \c g is not Euler then the resulted tour will not be full or closed. 56 56 ///\sa EulerIt 57 template< class Digraph>57 template<typename GR> 58 58 class DiEulerIt 59 59 { 60 typedef typename Digraph::Node Node;61 typedef typename Digraph::NodeIt NodeIt;62 typedef typename Digraph::Arc Arc;63 typedef typename Digraph::ArcIt ArcIt;64 typedef typename Digraph::OutArcIt OutArcIt;65 typedef typename Digraph::InArcIt InArcIt;66 67 const Digraph&g;68 typename Digraph::template NodeMap<OutArcIt> nedge;60 typedef typename GR::Node Node; 61 typedef typename GR::NodeIt NodeIt; 62 typedef typename GR::Arc Arc; 63 typedef typename GR::ArcIt ArcIt; 64 typedef typename GR::OutArcIt OutArcIt; 65 typedef typename GR::InArcIt InArcIt; 66 67 const GR &g; 68 typename GR::template NodeMap<OutArcIt> nedge; 69 69 std::list<Arc> euler; 70 70 … … 73 73 ///Constructor 74 74 75 ///\param _gA digraph.75 ///\param gr A digraph. 76 76 ///\param start The starting point of the tour. If it is not given 77 77 /// the tour will start from the first node. 78 DiEulerIt(const Digraph &_g,typename Digraph::Node start=INVALID)79 : g( _g), nedge(g)78 DiEulerIt(const GR &gr, typename GR::Node start = INVALID) 79 : g(gr), nedge(g) 80 80 { 81 81 if(start==INVALID) start=NodeIt(g); … … 146 146 ///If \c g is not Euler then the resulted tour will not be full or closed. 147 147 ///\sa EulerIt 148 template< class Digraph>148 template<typename GR> 149 149 class EulerIt 150 150 { 151 typedef typename Digraph::Node Node;152 typedef typename Digraph::NodeIt NodeIt;153 typedef typename Digraph::Arc Arc;154 typedef typename Digraph::Edge Edge;155 typedef typename Digraph::ArcIt ArcIt;156 typedef typename Digraph::OutArcIt OutArcIt;157 typedef typename Digraph::InArcIt InArcIt;158 159 const Digraph&g;160 typename Digraph::template NodeMap<OutArcIt> nedge;161 typename Digraph::template EdgeMap<bool> visited;151 typedef typename GR::Node Node; 152 typedef typename GR::NodeIt NodeIt; 153 typedef typename GR::Arc Arc; 154 typedef typename GR::Edge Edge; 155 typedef typename GR::ArcIt ArcIt; 156 typedef typename GR::OutArcIt OutArcIt; 157 typedef typename GR::InArcIt InArcIt; 158 159 const GR &g; 160 typename GR::template NodeMap<OutArcIt> nedge; 161 typename GR::template EdgeMap<bool> visited; 162 162 std::list<Arc> euler; 163 163 … … 166 166 ///Constructor 167 167 168 ///\param _gAn graph.168 ///\param gr An graph. 169 169 ///\param start The starting point of the tour. If it is not given 170 170 /// the tour will start from the first node. 171 EulerIt(const Digraph &_g,typename Digraph::Node start=INVALID)172 : g( _g), nedge(g), visited(g,false)171 EulerIt(const GR &gr, typename GR::Node start = INVALID) 172 : g(gr), nedge(g), visited(g, false) 173 173 { 174 174 if(start==INVALID) start=NodeIt(g); … … 239 239 ///for each node. <em>Therefore, there are digraphs which are not Eulerian, 240 240 ///but still have an Euler tour</em>. 241 template< class Digraph>241 template<typename GR> 242 242 #ifdef DOXYGEN 243 243 bool 244 244 #else 245 typename enable_if<UndirectedTagIndicator< Digraph>,bool>::type246 eulerian(const Digraph&g)247 { 248 for(typename Digraph::NodeIt n(g);n!=INVALID;++n)245 typename enable_if<UndirectedTagIndicator<GR>,bool>::type 246 eulerian(const GR &g) 247 { 248 for(typename GR::NodeIt n(g);n!=INVALID;++n) 249 249 if(countIncEdges(g,n)%2) return false; 250 250 return connected(g); 251 251 } 252 template<class Digraph>253 typename disable_if<UndirectedTagIndicator< Digraph>,bool>::type252 template<class GR> 253 typename disable_if<UndirectedTagIndicator<GR>,bool>::type 254 254 #endif 255 eulerian(const Digraph&g)256 { 257 for(typename Digraph::NodeIt n(g);n!=INVALID;++n)255 eulerian(const GR &g) 256 { 257 for(typename GR::NodeIt n(g);n!=INVALID;++n) 258 258 if(countInArcs(g,n)!=countOutArcs(g,n)) return false; 259 return connected(Undirector<const Digraph>(g));259 return connected(Undirector<const GR>(g)); 260 260 } 261 261
Note: See TracChangeset
for help on using the changeset viewer.