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