# Changeset 1818:8f9905c4e1c1 in lemon-0.x

Ignore:
Timestamp:
11/21/05 10:08:16 (14 years ago)
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2367
Message:

File:
1 edited

Unmodified
Removed
• ## lemon/euler.h

 r1803 /* -*- C++ -*- * lemon/topology.h - Part of LEMON, a generic C++ optimization library * lemon/euler.h - Part of LEMON, a generic C++ optimization library * * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport */ #include #include #include namespace lemon { ///Euler iterator in directed graphs. ///Euler iterator for directed graphs. /// \ingroup topology }; ///Euler iterator for undirected graphs. /// \ingroup topology ///This iterator converts to the \c Edge type of the graph and using ///operator ++ it provides an Euler tour of the graph (if there exists). /// ///For example ///if the given graph if Euler (i.e it has only one nontrivial component ///and the degree of each node is even), ///the following code will print the edge IDs according to an ///Euler tour of \c g. ///\code ///  for(UndirEulerIt e(g),e!=INVALID;++e) { ///    std::cout << g.id(UndirEdge(e)) << std::eol; ///  } ///\endcode ///Although the iterator provides an Euler tour of an undirected graph, ///in order to indicate the direction of the tour, UndirEulerIt ///returns directed edges (that convert to the undirected ones, of course). /// ///If \c g is not Euler then the resulted tour will not be full or closed. ///\todo Test required template class UndirEulerIt { typedef typename Graph::Node Node; typedef typename Graph::NodeIt NodeIt; typedef typename Graph::Edge Edge; typedef typename Graph::EdgeIt EdgeIt; typedef typename Graph::OutEdgeIt OutEdgeIt; typedef typename Graph::InEdgeIt InEdgeIt; const Graph &g; typename Graph::NodeMap nedge; typename Graph::UndirEdgeMap visited; std::list euler; public: ///Constructor ///\param _g An undirected graph. ///\param start The starting point of the tour. If it is not given ///       the tour will start from the first node. UndirEulerIt(const Graph &_g,typename Graph::Node start=INVALID) : g(_g), nedge(g), visited(g,false) { if(start==INVALID) start=NodeIt(g); for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutEdgeIt(g,n); while(nedge[start]!=INVALID) { euler.push_back(nedge[start]); Node next=g.target(nedge[start]); ++nedge[start]; start=next;     while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start]; } } ///Edge Conversion operator Edge() { return euler.empty()?INVALID:euler.front(); } bool operator==(Invalid) { return euler.empty(); } bool operator!=(Invalid) { return !euler.empty(); } ///Next edge of the tour UndirEulerIt &operator++() { Node s=g.target(euler.front()); euler.pop_front(); typename std::list::iterator next=euler.begin(); while(nedge[s]!=INVALID) { while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s]; if(nedge[s]==INVALID) break; else { euler.insert(next,nedge[s]); Node n=g.target(nedge[s]); ++nedge[s]; s=n; } } return *this; } ///Postfix incrementation ///\warning This incrementation ///returns an \c Edge, not an \ref UndirEulerIt, as one may ///expect. Edge operator++(int) { Edge e=*this; ++(*this); return e; } }; ///Checks if the graph is Euler /// \ingroup gutils /// \ingroup topology ///Checks if the graph is Euler. It works for both directed and ///undirected graphs. ///\note By definition, a directed graph is called \e Euler if ///and only if connected and the number of it is incoming and outgoing edges ///are the same for each node. ///Similarly, an undirected graph is called \e Euler if ///and only if it is connected and the number of incident edges is even ///for each node. Therefore, there are graphs which are not Euler, but ///still have an Euler tour. ///\todo Test required template #else typename enable_if::type euler(const Graph &g) { for(typename Graph::NodeIt n(g);n!=INVALID;++n) if(countIncEdges(g,n)%2) return false; return connected(g); } template typename disable_if::type #endif euler(const Graph &g) { for(typename Graph::NodeIt n(g);n!=INVALID;++n) if(countIncEdges(g,n)%2) return false; return true; } template typename disable_if::type euler(const Graph &g) { for(typename Graph::NodeIt n(g);n!=INVALID;++n) if(countInEdges(g,n)!=countOutEdges(g,n)) return false; return true; return connected(g); }
Note: See TracChangeset for help on using the changeset viewer.