alpar@520: /* -*- mode: C++; indent-tabs-mode: nil; -*- alpar@520: * alpar@520: * This file is a part of LEMON, a generic C++ optimization library. alpar@520: * alpar@520: * Copyright (C) 2003-2009 alpar@520: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@520: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@520: * alpar@520: * Permission to use, modify and distribute this software is granted alpar@520: * provided that this copyright notice appears in all copies. For alpar@520: * precise terms see the accompanying LICENSE file. alpar@520: * alpar@520: * This software is provided "AS IS" with no warranty of any kind, alpar@520: * express or implied, and with no claim as to its suitability for any alpar@520: * purpose. alpar@520: * alpar@520: */ alpar@520: alpar@520: #ifndef LEMON_EULER_H alpar@520: #define LEMON_EULER_H alpar@520: alpar@520: #include alpar@520: #include alpar@520: #include alpar@520: #include alpar@520: alpar@520: /// \ingroup graph_prop alpar@520: /// \file alpar@520: /// \brief Euler tour alpar@520: /// alpar@520: ///This file provides an Euler tour iterator and ways to check alpar@520: ///if a digraph is euler. alpar@520: alpar@520: alpar@520: namespace lemon { alpar@520: alpar@520: ///Euler iterator for digraphs. alpar@520: alpar@520: /// \ingroup graph_prop alpar@520: ///This iterator converts to the \c Arc type of the digraph and using alpar@520: ///operator ++, it provides an Euler tour of a \e directed alpar@520: ///graph (if there exists). alpar@520: /// alpar@520: ///For example alpar@520: ///if the given digraph is Euler (i.e it has only one nontrivial component alpar@520: ///and the in-degree is equal to the out-degree for all nodes), alpar@520: ///the following code will put the arcs of \c g alpar@520: ///to the vector \c et according to an alpar@520: ///Euler tour of \c g. alpar@520: ///\code alpar@520: /// std::vector et; alpar@520: /// for(DiEulerIt e(g),e!=INVALID;++e) alpar@520: /// et.push_back(e); alpar@520: ///\endcode alpar@520: ///If \c g is not Euler then the resulted tour will not be full or closed. alpar@520: ///\sa EulerIt kpeter@559: template alpar@520: class DiEulerIt alpar@520: { kpeter@559: typedef typename GR::Node Node; kpeter@559: typedef typename GR::NodeIt NodeIt; kpeter@559: typedef typename GR::Arc Arc; kpeter@559: typedef typename GR::ArcIt ArcIt; kpeter@559: typedef typename GR::OutArcIt OutArcIt; kpeter@559: typedef typename GR::InArcIt InArcIt; alpar@520: kpeter@559: const GR &g; kpeter@559: typename GR::template NodeMap nedge; alpar@520: std::list euler; alpar@520: alpar@520: public: alpar@520: alpar@520: ///Constructor alpar@520: kpeter@559: ///\param gr A digraph. alpar@520: ///\param start The starting point of the tour. If it is not given alpar@520: /// the tour will start from the first node. kpeter@559: DiEulerIt(const GR &gr, typename GR::Node start = INVALID) kpeter@559: : g(gr), nedge(g) alpar@520: { alpar@520: if(start==INVALID) start=NodeIt(g); alpar@520: for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n); alpar@520: while(nedge[start]!=INVALID) { alpar@520: euler.push_back(nedge[start]); alpar@520: Node next=g.target(nedge[start]); alpar@520: ++nedge[start]; alpar@520: start=next; alpar@520: } alpar@520: } alpar@520: alpar@520: ///Arc Conversion alpar@520: operator Arc() { return euler.empty()?INVALID:euler.front(); } alpar@520: bool operator==(Invalid) { return euler.empty(); } alpar@520: bool operator!=(Invalid) { return !euler.empty(); } alpar@520: alpar@520: ///Next arc of the tour alpar@520: DiEulerIt &operator++() { alpar@520: Node s=g.target(euler.front()); alpar@520: euler.pop_front(); alpar@520: //This produces a warning.Strange. alpar@520: //std::list::iterator next=euler.begin(); alpar@520: typename std::list::iterator next=euler.begin(); alpar@520: while(nedge[s]!=INVALID) { alpar@520: euler.insert(next,nedge[s]); alpar@520: Node n=g.target(nedge[s]); alpar@520: ++nedge[s]; alpar@520: s=n; alpar@520: } alpar@520: return *this; alpar@520: } alpar@520: ///Postfix incrementation alpar@520: alpar@520: ///\warning This incrementation alpar@520: ///returns an \c Arc, not an \ref DiEulerIt, as one may alpar@520: ///expect. alpar@520: Arc operator++(int) alpar@520: { alpar@520: Arc e=*this; alpar@520: ++(*this); alpar@520: return e; alpar@520: } alpar@520: }; alpar@520: alpar@520: ///Euler iterator for graphs. alpar@520: alpar@520: /// \ingroup graph_prop alpar@520: ///This iterator converts to the \c Arc (or \c Edge) alpar@520: ///type of the digraph and using alpar@520: ///operator ++, it provides an Euler tour of an undirected alpar@520: ///digraph (if there exists). alpar@520: /// alpar@520: ///For example alpar@520: ///if the given digraph if Euler (i.e it has only one nontrivial component alpar@520: ///and the degree of each node is even), alpar@520: ///the following code will print the arc IDs according to an alpar@520: ///Euler tour of \c g. alpar@520: ///\code alpar@520: /// for(EulerIt e(g),e!=INVALID;++e) { alpar@520: /// std::cout << g.id(Edge(e)) << std::eol; alpar@520: /// } alpar@520: ///\endcode alpar@520: ///Although the iterator provides an Euler tour of an graph, alpar@520: ///it still returns Arcs in order to indicate the direction of the tour. alpar@520: ///(But Arc will convert to Edges, of course). alpar@520: /// alpar@520: ///If \c g is not Euler then the resulted tour will not be full or closed. alpar@520: ///\sa EulerIt kpeter@559: template alpar@520: class EulerIt alpar@520: { kpeter@559: typedef typename GR::Node Node; kpeter@559: typedef typename GR::NodeIt NodeIt; kpeter@559: typedef typename GR::Arc Arc; kpeter@559: typedef typename GR::Edge Edge; kpeter@559: typedef typename GR::ArcIt ArcIt; kpeter@559: typedef typename GR::OutArcIt OutArcIt; kpeter@559: typedef typename GR::InArcIt InArcIt; alpar@520: kpeter@559: const GR &g; kpeter@559: typename GR::template NodeMap nedge; kpeter@559: typename GR::template EdgeMap visited; alpar@520: std::list euler; alpar@520: alpar@520: public: alpar@520: alpar@520: ///Constructor alpar@520: kpeter@559: ///\param gr An graph. alpar@520: ///\param start The starting point of the tour. If it is not given alpar@520: /// the tour will start from the first node. kpeter@559: EulerIt(const GR &gr, typename GR::Node start = INVALID) kpeter@559: : g(gr), nedge(g), visited(g, false) alpar@520: { alpar@520: if(start==INVALID) start=NodeIt(g); alpar@520: for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n); alpar@520: while(nedge[start]!=INVALID) { alpar@520: euler.push_back(nedge[start]); alpar@520: visited[nedge[start]]=true; alpar@520: Node next=g.target(nedge[start]); alpar@520: ++nedge[start]; alpar@520: start=next; alpar@520: while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start]; alpar@520: } alpar@520: } alpar@520: alpar@520: ///Arc Conversion alpar@520: operator Arc() const { return euler.empty()?INVALID:euler.front(); } alpar@520: ///Arc Conversion alpar@520: operator Edge() const { return euler.empty()?INVALID:euler.front(); } alpar@520: ///\e alpar@520: bool operator==(Invalid) const { return euler.empty(); } alpar@520: ///\e alpar@520: bool operator!=(Invalid) const { return !euler.empty(); } alpar@520: alpar@520: ///Next arc of the tour alpar@520: EulerIt &operator++() { alpar@520: Node s=g.target(euler.front()); alpar@520: euler.pop_front(); alpar@520: typename std::list::iterator next=euler.begin(); alpar@520: alpar@520: while(nedge[s]!=INVALID) { alpar@520: while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s]; alpar@520: if(nedge[s]==INVALID) break; alpar@520: else { alpar@520: euler.insert(next,nedge[s]); alpar@520: visited[nedge[s]]=true; alpar@520: Node n=g.target(nedge[s]); alpar@520: ++nedge[s]; alpar@520: s=n; alpar@520: } alpar@520: } alpar@520: return *this; alpar@520: } alpar@520: alpar@520: ///Postfix incrementation alpar@520: alpar@520: ///\warning This incrementation alpar@520: ///returns an \c Arc, not an \ref EulerIt, as one may alpar@520: ///expect. alpar@520: Arc operator++(int) alpar@520: { alpar@520: Arc e=*this; alpar@520: ++(*this); alpar@520: return e; alpar@520: } alpar@520: }; alpar@520: alpar@520: alpar@521: ///Checks if the graph is Eulerian alpar@520: alpar@520: /// \ingroup graph_prop alpar@521: ///Checks if the graph is Eulerian. It works for both directed and undirected alpar@520: ///graphs. alpar@521: ///\note By definition, a digraph is called \e Eulerian if alpar@520: ///and only if it is connected and the number of its incoming and outgoing alpar@520: ///arcs are the same for each node. alpar@521: ///Similarly, an undirected graph is called \e Eulerian if alpar@520: ///and only if it is connected and the number of incident arcs is even alpar@521: ///for each node. Therefore, there are digraphs which are not Eulerian, alpar@521: ///but still have an Euler tour. kpeter@559: template alpar@520: #ifdef DOXYGEN alpar@520: bool alpar@520: #else kpeter@559: typename enable_if,bool>::type kpeter@559: eulerian(const GR &g) alpar@520: { kpeter@559: for(typename GR::NodeIt n(g);n!=INVALID;++n) alpar@520: if(countIncEdges(g,n)%2) return false; alpar@520: return connected(g); alpar@520: } kpeter@559: template kpeter@559: typename disable_if,bool>::type alpar@520: #endif kpeter@559: eulerian(const GR &g) alpar@520: { kpeter@559: for(typename GR::NodeIt n(g);n!=INVALID;++n) alpar@520: if(countInArcs(g,n)!=countOutArcs(g,n)) return false; kpeter@559: return connected(Undirector(g)); alpar@520: } alpar@520: alpar@520: } alpar@520: alpar@520: #endif