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