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: kpeter@586: /// \ingroup graph_properties alpar@520: /// \file kpeter@592: /// \brief Euler tour iterators and a function for checking the \e Eulerian kpeter@592: /// property. alpar@520: /// kpeter@592: ///This file provides Euler tour iterators and a function to check kpeter@592: ///if a (di)graph is \e Eulerian. alpar@520: alpar@520: namespace lemon { alpar@520: kpeter@592: ///Euler tour iterator for digraphs. alpar@520: kpeter@592: /// \ingroup graph_prop kpeter@592: ///This iterator provides an Euler tour (Eulerian circuit) of a \e directed kpeter@592: ///graph (if there exists) and it converts to the \c Arc type of the digraph. alpar@520: /// kpeter@592: ///For example, if the given digraph has an Euler tour (i.e it has only one kpeter@592: ///non-trivial component and the in-degree is equal to the out-degree kpeter@592: ///for all nodes), then the following code will put the arcs of \c g kpeter@592: ///to the vector \c et according to an Euler tour of \c g. alpar@520: ///\code alpar@520: /// std::vector et; kpeter@592: /// for(DiEulerIt e(g); e!=INVALID; ++e) alpar@520: /// et.push_back(e); alpar@520: ///\endcode kpeter@592: ///If \c g has no Euler tour, then the resulted walk will not be closed kpeter@592: ///or not contain all arcs. 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@592: typename GR::template NodeMap narc; alpar@520: std::list euler; alpar@520: alpar@520: public: alpar@520: alpar@520: ///Constructor alpar@520: kpeter@592: ///Constructor. kpeter@559: ///\param gr A digraph. kpeter@592: ///\param start The starting point of the tour. If it is not given, kpeter@592: ///the tour will start from the first node that has an outgoing arc. kpeter@559: DiEulerIt(const GR &gr, typename GR::Node start = INVALID) kpeter@592: : g(gr), narc(g) alpar@520: { kpeter@591: if (start==INVALID) { kpeter@591: NodeIt n(g); kpeter@591: while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n; kpeter@591: start=n; kpeter@591: } kpeter@591: if (start!=INVALID) { kpeter@592: for (NodeIt n(g); n!=INVALID; ++n) narc[n]=OutArcIt(g,n); kpeter@592: while (narc[start]!=INVALID) { kpeter@592: euler.push_back(narc[start]); kpeter@592: Node next=g.target(narc[start]); kpeter@592: ++narc[start]; kpeter@591: start=next; kpeter@591: } alpar@520: } alpar@520: } alpar@520: kpeter@592: ///Arc conversion alpar@520: operator Arc() { return euler.empty()?INVALID:euler.front(); } kpeter@592: ///Compare with \c INVALID alpar@520: bool operator==(Invalid) { return euler.empty(); } kpeter@592: ///Compare with \c INVALID alpar@520: bool operator!=(Invalid) { return !euler.empty(); } alpar@520: alpar@520: ///Next arc of the tour kpeter@592: kpeter@592: ///Next arc of the tour kpeter@592: /// alpar@520: DiEulerIt &operator++() { alpar@520: Node s=g.target(euler.front()); alpar@520: euler.pop_front(); alpar@520: typename std::list::iterator next=euler.begin(); kpeter@592: while(narc[s]!=INVALID) { kpeter@592: euler.insert(next,narc[s]); kpeter@592: Node n=g.target(narc[s]); kpeter@592: ++narc[s]; alpar@520: s=n; alpar@520: } alpar@520: return *this; alpar@520: } alpar@520: ///Postfix incrementation alpar@520: kpeter@592: /// Postfix incrementation. kpeter@592: /// alpar@520: ///\warning This incrementation kpeter@592: ///returns an \c Arc, not a \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: kpeter@592: ///Euler tour iterator for graphs. alpar@520: kpeter@586: /// \ingroup graph_properties kpeter@592: ///This iterator provides an Euler tour (Eulerian circuit) of an kpeter@592: ///\e undirected graph (if there exists) and it converts to the \c Arc kpeter@592: ///and \c Edge types of the graph. alpar@520: /// kpeter@592: ///For example, if the given graph has an Euler tour (i.e it has only one kpeter@592: ///non-trivial component 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 kpeter@592: /// for(EulerIt e(g); e!=INVALID; ++e) { alpar@520: /// std::cout << g.id(Edge(e)) << std::eol; alpar@520: /// } alpar@520: ///\endcode kpeter@592: ///Although this iterator is for undirected graphs, it still returns kpeter@592: ///arcs in order to indicate the direction of the tour. kpeter@592: ///(But arcs convert to edges, of course.) alpar@520: /// kpeter@592: ///If \c g has no Euler tour, then the resulted walk will not be closed kpeter@592: ///or not contain all edges. 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@592: typename GR::template NodeMap narc; 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@592: ///Constructor. kpeter@592: ///\param gr A graph. kpeter@592: ///\param start The starting point of the tour. If it is not given, kpeter@592: ///the tour will start from the first node that has an incident edge. kpeter@559: EulerIt(const GR &gr, typename GR::Node start = INVALID) kpeter@592: : g(gr), narc(g), visited(g, false) alpar@520: { kpeter@591: if (start==INVALID) { kpeter@591: NodeIt n(g); kpeter@591: while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n; kpeter@591: start=n; kpeter@591: } kpeter@591: if (start!=INVALID) { kpeter@592: for (NodeIt n(g); n!=INVALID; ++n) narc[n]=OutArcIt(g,n); kpeter@592: while(narc[start]!=INVALID) { kpeter@592: euler.push_back(narc[start]); kpeter@592: visited[narc[start]]=true; kpeter@592: Node next=g.target(narc[start]); kpeter@592: ++narc[start]; kpeter@591: start=next; kpeter@592: while(narc[start]!=INVALID && visited[narc[start]]) ++narc[start]; kpeter@591: } alpar@520: } alpar@520: } alpar@520: kpeter@592: ///Arc conversion alpar@520: operator Arc() const { return euler.empty()?INVALID:euler.front(); } kpeter@592: ///Edge conversion alpar@520: operator Edge() const { return euler.empty()?INVALID:euler.front(); } kpeter@592: ///Compare with \c INVALID alpar@520: bool operator==(Invalid) const { return euler.empty(); } kpeter@592: ///Compare with \c INVALID alpar@520: bool operator!=(Invalid) const { return !euler.empty(); } alpar@520: alpar@520: ///Next arc of the tour kpeter@592: kpeter@592: ///Next arc of the tour kpeter@592: /// 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(); kpeter@592: while(narc[s]!=INVALID) { kpeter@592: while(narc[s]!=INVALID && visited[narc[s]]) ++narc[s]; kpeter@592: if(narc[s]==INVALID) break; alpar@520: else { kpeter@592: euler.insert(next,narc[s]); kpeter@592: visited[narc[s]]=true; kpeter@592: Node n=g.target(narc[s]); kpeter@592: ++narc[s]; alpar@520: s=n; alpar@520: } alpar@520: } alpar@520: return *this; alpar@520: } alpar@520: alpar@520: ///Postfix incrementation alpar@520: kpeter@592: /// Postfix incrementation. kpeter@592: /// kpeter@592: ///\warning This incrementation returns an \c Arc (which converts to kpeter@592: ///an \c Edge), not an \ref EulerIt, as one may 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: kpeter@648: ///Check if the given graph is Eulerian alpar@520: kpeter@586: /// \ingroup graph_properties kpeter@648: ///This function checks if the given graph is Eulerian. kpeter@592: ///It works for both directed and undirected graphs. kpeter@592: /// kpeter@592: ///By definition, a digraph is called \e Eulerian if kpeter@592: ///and only if it is connected and the number of incoming and outgoing alpar@520: ///arcs are the same for each node. alpar@521: ///Similarly, an undirected graph is called \e Eulerian if kpeter@592: ///and only if it is connected and the number of incident edges is even kpeter@592: ///for each node. kpeter@592: /// kpeter@592: ///\note There are (di)graphs that are not Eulerian, but still have an kpeter@592: /// Euler tour, since they may contain isolated nodes. kpeter@592: /// kpeter@592: ///\sa DiEulerIt, EulerIt 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@592: return connected(undirector(g)); alpar@520: } alpar@520: alpar@520: } alpar@520: alpar@520: #endif