alpar@1738: /* -*- C++ -*- alpar@1738: * alpar@1956: * This file is a part of LEMON, a generic C++ optimization library alpar@1956: * alpar@2553: * Copyright (C) 2003-2008 alpar@1956: * 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@1956: deba@1993: #include alpar@1818: #include alpar@1738: #include alpar@1738: deba@2429: /// \ingroup graph_prop 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@1818: ///Euler iterator for directed graphs. alpar@1738: deba@2429: /// \ingroup graph_prop alpar@1738: ///This iterator converts to the \c Edge type of the graph and using alpar@1970: ///operator ++ it provides an Euler tour of a \e directed alpar@1970: ///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@1970: ///the following code will put the edges of \c g alpar@1970: ///to the vector \c et according to an alpar@1738: ///Euler tour of \c g. alpar@1738: ///\code alpar@1970: /// std::vector et; alpar@1970: /// for(EulerIt e(g),e!=INVALID;++e) alpar@1970: /// et.push_back(e); alpar@1738: ///\endcode alpar@1738: ///If \c g is not Euler then the resulted tour will not be full or closed. alpar@1970: ///\sa UEulerIt 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; deba@2405: typename Graph::template 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@1803: /// the 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@1803: ///\warning This incrementation alpar@1803: ///returns an \c Edge, not an \ref EulerIt, as one may alpar@1803: ///expect. 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@1818: ///Euler iterator for undirected graphs. alpar@1818: deba@2429: /// \ingroup graph_prop alpar@2350: ///This iterator converts to the \c Edge (or \c UEdge) alpar@1970: ///type of the graph and using alpar@2350: ///operator ++ it provides an Euler tour of an undirected alpar@1970: ///graph (if there exists). alpar@1818: /// alpar@1818: ///For example alpar@1818: ///if the given graph if Euler (i.e it has only one nontrivial component alpar@1818: ///and the degree of each node is even), alpar@1818: ///the following code will print the edge IDs according to an alpar@1818: ///Euler tour of \c g. alpar@1818: ///\code klao@1909: /// for(UEulerIt e(g),e!=INVALID;++e) { klao@1909: /// std::cout << g.id(UEdge(e)) << std::eol; alpar@1818: /// } alpar@1818: ///\endcode alpar@1818: ///Although the iterator provides an Euler tour of an undirected graph, klao@1909: ///in order to indicate the direction of the tour, UEulerIt alpar@1818: ///returns directed edges (that convert to the undirected ones, of course). alpar@1818: /// alpar@1818: ///If \c g is not Euler then the resulted tour will not be full or closed. alpar@1970: ///\sa EulerIt alpar@1818: ///\todo Test required alpar@1818: template klao@1909: class UEulerIt alpar@1818: { alpar@1818: typedef typename Graph::Node Node; alpar@1818: typedef typename Graph::NodeIt NodeIt; alpar@1818: typedef typename Graph::Edge Edge; alpar@2445: typedef typename Graph::UEdge UEdge; alpar@1818: typedef typename Graph::EdgeIt EdgeIt; alpar@1818: typedef typename Graph::OutEdgeIt OutEdgeIt; alpar@1818: typedef typename Graph::InEdgeIt InEdgeIt; alpar@1818: alpar@1818: const Graph &g; deba@2405: typename Graph::template NodeMap nedge; deba@2405: typename Graph::template UEdgeMap visited; alpar@1818: std::list euler; alpar@1818: alpar@1818: public: alpar@1818: alpar@1818: ///Constructor alpar@1818: alpar@1818: ///\param _g An undirected graph. alpar@1818: ///\param start The starting point of the tour. If it is not given alpar@1818: /// the tour will start from the first node. klao@1909: UEulerIt(const Graph &_g,typename Graph::Node start=INVALID) alpar@1818: : g(_g), nedge(g), visited(g,false) alpar@1818: { alpar@1818: if(start==INVALID) start=NodeIt(g); alpar@1818: for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutEdgeIt(g,n); alpar@1818: while(nedge[start]!=INVALID) { alpar@1818: euler.push_back(nedge[start]); alpar@2445: visited[nedge[start]]=true; alpar@1818: Node next=g.target(nedge[start]); alpar@1818: ++nedge[start]; alpar@2445: start=next; alpar@2445: while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start]; alpar@1818: } alpar@1818: } alpar@1818: alpar@1818: ///Edge Conversion alpar@2445: operator Edge() const { return euler.empty()?INVALID:euler.front(); } alpar@2445: ///Edge Conversion alpar@2445: operator UEdge() const { return euler.empty()?INVALID:euler.front(); } alpar@2445: ///\e alpar@2445: bool operator==(Invalid) const { return euler.empty(); } alpar@2445: ///\e alpar@2445: bool operator!=(Invalid) const { return !euler.empty(); } alpar@1818: alpar@1818: ///Next edge of the tour klao@1909: UEulerIt &operator++() { alpar@1818: Node s=g.target(euler.front()); alpar@1818: euler.pop_front(); alpar@1818: typename std::list::iterator next=euler.begin(); alpar@1818: alpar@1818: while(nedge[s]!=INVALID) { alpar@1818: while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s]; alpar@1818: if(nedge[s]==INVALID) break; alpar@1818: else { alpar@1818: euler.insert(next,nedge[s]); alpar@2445: visited[nedge[s]]=true; alpar@1818: Node n=g.target(nedge[s]); alpar@1818: ++nedge[s]; alpar@1818: s=n; alpar@1818: } alpar@1818: } alpar@1818: return *this; alpar@1818: } alpar@1818: alpar@1818: ///Postfix incrementation alpar@1818: alpar@1818: ///\warning This incrementation klao@1909: ///returns an \c Edge, not an \ref UEulerIt, as one may alpar@1818: ///expect. alpar@1818: Edge operator++(int) alpar@1818: { alpar@1818: Edge e=*this; alpar@1818: ++(*this); alpar@1818: return e; alpar@1818: } alpar@1818: }; alpar@1818: alpar@1818: alpar@1738: ///Checks if the graph is Euler alpar@1738: deba@2429: /// \ingroup graph_prop alpar@1738: ///Checks if the graph is Euler. It works for both directed and alpar@1738: ///undirected graphs. alpar@1818: ///\note By definition, a directed graph is called \e Euler if alpar@1818: ///and only if connected and the number of it is incoming and outgoing edges alpar@1818: ///are the same for each node. alpar@1818: ///Similarly, an undirected graph is called \e Euler if alpar@1818: ///and only if it is connected and the number of incident edges is even alpar@1818: ///for each node. Therefore, there are graphs which are not Euler, but alpar@1818: ///still have an Euler tour. alpar@1738: ///\todo Test required alpar@1738: template alpar@1738: #ifdef DOXYGEN alpar@1738: bool alpar@1738: #else deba@1979: typename enable_if,bool>::type alpar@1818: euler(const Graph &g) alpar@1818: { alpar@1818: for(typename Graph::NodeIt n(g);n!=INVALID;++n) alpar@1818: if(countIncEdges(g,n)%2) return false; alpar@1818: return connected(g); alpar@1818: } alpar@1818: template deba@1979: typename disable_if,bool>::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(countInEdges(g,n)!=countOutEdges(g,n)) return false; alpar@1818: return connected(g); alpar@1738: } alpar@1738: alpar@1738: }