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