/* -*- C++ -*- * lemon/topology.h - Part of LEMON, a generic C++ optimization library * * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * * Permission to use, modify and distribute this software is granted * provided that this copyright notice appears in all copies. For * precise terms see the accompanying LICENSE file. * * This software is provided "AS IS" with no warranty of any kind, * express or implied, and with no claim as to its suitability for any * purpose. * */ #include #include /// \ingroup gutils /// \file /// \brief Euler tour /// ///This file provides an Euler tour iterator and ways to check ///if a graph is euler. namespace lemon { ///Euler iterator in directed graphs. /// \ingroup gutils ///This iterator converts to the \c Edge type of the graph and using ///the ++ 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 in-degree is equal to the out-degree for all nodes), ///the the following code will print the edge IDs according to an ///Euler tour of \c g. ///\code /// for(EulerIt e(g),e!=INVALID;++e) { /// std::cout << g.id(e) << std::eol; /// } ///\endcode ///If \c g is not Euler then the resulted tour will not be full or closed. ///\todo Test required template class EulerIt { 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; std::list euler; public: ///Constructor ///\param _g A directed graph. ///\param start The starting point of the tour. If it is not given /// tho tour will start from the first node. EulerIt(const Graph &_g,typename Graph::Node start=INVALID) : g(_g), nedge(g) { 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; } } ///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 EulerIt &operator++() { Node s=g.target(euler.front()); euler.pop_front(); //This produces a warning.Strange. //std::list::iterator next=euler.begin(); typename std::list::iterator next=euler.begin(); while(nedge[s]!=INVALID) { euler.insert(next,nedge[s]); Node n=g.target(nedge[s]); ++nedge[s]; s=n; } return *this; } ///Postfix incrementation ///\warning This gives back an Edge, not an EulerIt! Edge operator++(int) { Edge e=*this; ++(*this); return e; } }; ///Checks if the graph is Euler /// \ingroup gutils ///Checks if the graph is Euler. It works for both directed and ///undirected graphs. ///\todo What to do with the isolated points? ///\todo Test required template #ifdef DOXYGEN bool #else typename enable_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; } }