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 alpar@504: /// \brief Euler tour alpar@504: /// alpar@504: ///This file provides an Euler tour iterator and ways to check alpar@504: ///if a digraph is euler. alpar@504: alpar@504: alpar@504: namespace lemon { alpar@504: alpar@504: ///Euler iterator for digraphs. alpar@504: kpeter@578: /// \ingroup graph_properties alpar@504: ///This iterator converts to the \c Arc type of the digraph and using alpar@504: ///operator ++, it provides an Euler tour of a \e directed alpar@504: ///graph (if there exists). alpar@504: /// alpar@504: ///For example alpar@504: ///if the given digraph is Euler (i.e it has only one nontrivial component alpar@504: ///and the in-degree is equal to the out-degree for all nodes), alpar@504: ///the following code will put the arcs of \c g alpar@504: ///to the vector \c et according to an alpar@504: ///Euler tour of \c g. alpar@504: ///\code alpar@504: /// std::vector et; alpar@504: /// for(DiEulerIt e(g),e!=INVALID;++e) alpar@504: /// et.push_back(e); alpar@504: ///\endcode alpar@504: ///If \c g is not Euler then the resulted tour will not be full or closed. 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@550: typename GR::template NodeMap nedge; alpar@504: std::list euler; alpar@504: alpar@504: public: alpar@504: alpar@504: ///Constructor alpar@504: kpeter@550: ///\param gr A digraph. alpar@504: ///\param start The starting point of the tour. If it is not given alpar@504: /// the tour will start from the first node. kpeter@550: DiEulerIt(const GR &gr, typename GR::Node start = INVALID) kpeter@550: : g(gr), nedge(g) alpar@504: { alpar@504: if(start==INVALID) start=NodeIt(g); alpar@504: for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n); alpar@504: while(nedge[start]!=INVALID) { alpar@504: euler.push_back(nedge[start]); alpar@504: Node next=g.target(nedge[start]); alpar@504: ++nedge[start]; alpar@504: start=next; alpar@504: } alpar@504: } alpar@504: alpar@504: ///Arc Conversion alpar@504: operator Arc() { return euler.empty()?INVALID:euler.front(); } alpar@504: bool operator==(Invalid) { return euler.empty(); } alpar@504: bool operator!=(Invalid) { return !euler.empty(); } alpar@504: alpar@504: ///Next arc of the tour alpar@504: DiEulerIt &operator++() { alpar@504: Node s=g.target(euler.front()); alpar@504: euler.pop_front(); alpar@504: //This produces a warning.Strange. alpar@504: //std::list::iterator next=euler.begin(); alpar@504: typename std::list::iterator next=euler.begin(); alpar@504: while(nedge[s]!=INVALID) { alpar@504: euler.insert(next,nedge[s]); alpar@504: Node n=g.target(nedge[s]); alpar@504: ++nedge[s]; alpar@504: s=n; alpar@504: } alpar@504: return *this; alpar@504: } alpar@504: ///Postfix incrementation alpar@504: alpar@504: ///\warning This incrementation alpar@504: ///returns an \c Arc, not an \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: alpar@504: ///Euler iterator for graphs. alpar@504: kpeter@578: /// \ingroup graph_properties alpar@504: ///This iterator converts to the \c Arc (or \c Edge) alpar@504: ///type of the digraph and using alpar@504: ///operator ++, it provides an Euler tour of an undirected alpar@504: ///digraph (if there exists). alpar@504: /// alpar@504: ///For example alpar@504: ///if the given digraph if Euler (i.e it has only one nontrivial component alpar@504: ///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 alpar@504: /// for(EulerIt e(g),e!=INVALID;++e) { alpar@504: /// std::cout << g.id(Edge(e)) << std::eol; alpar@504: /// } alpar@504: ///\endcode alpar@504: ///Although the iterator provides an Euler tour of an graph, alpar@504: ///it still returns Arcs in order to indicate the direction of the tour. alpar@504: ///(But Arc will convert to Edges, of course). alpar@504: /// alpar@504: ///If \c g is not Euler then the resulted tour will not be full or closed. alpar@504: ///\sa EulerIt 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@550: typename GR::template NodeMap nedge; 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@550: ///\param gr An graph. alpar@504: ///\param start The starting point of the tour. If it is not given alpar@504: /// the tour will start from the first node. kpeter@550: EulerIt(const GR &gr, typename GR::Node start = INVALID) kpeter@550: : g(gr), nedge(g), visited(g, false) alpar@504: { alpar@504: if(start==INVALID) start=NodeIt(g); alpar@504: for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n); alpar@504: while(nedge[start]!=INVALID) { alpar@504: euler.push_back(nedge[start]); alpar@504: visited[nedge[start]]=true; alpar@504: Node next=g.target(nedge[start]); alpar@504: ++nedge[start]; alpar@504: start=next; alpar@504: while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start]; alpar@504: } alpar@504: } alpar@504: alpar@504: ///Arc Conversion alpar@504: operator Arc() const { return euler.empty()?INVALID:euler.front(); } alpar@504: ///Arc Conversion alpar@504: operator Edge() const { return euler.empty()?INVALID:euler.front(); } alpar@504: ///\e alpar@504: bool operator==(Invalid) const { return euler.empty(); } alpar@504: ///\e alpar@504: bool operator!=(Invalid) const { return !euler.empty(); } alpar@504: alpar@504: ///Next arc of the tour 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(); alpar@504: alpar@504: while(nedge[s]!=INVALID) { alpar@504: while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s]; alpar@504: if(nedge[s]==INVALID) break; alpar@504: else { alpar@504: euler.insert(next,nedge[s]); alpar@504: visited[nedge[s]]=true; alpar@504: Node n=g.target(nedge[s]); alpar@504: ++nedge[s]; alpar@504: s=n; alpar@504: } alpar@504: } alpar@504: return *this; alpar@504: } alpar@504: alpar@504: ///Postfix incrementation alpar@504: alpar@504: ///\warning This incrementation alpar@504: ///returns an \c Arc, not an \ref EulerIt, 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: alpar@504: alpar@505: ///Checks if the graph is Eulerian alpar@504: kpeter@578: /// \ingroup graph_properties alpar@505: ///Checks if the graph is Eulerian. It works for both directed and undirected alpar@504: ///graphs. alpar@505: ///\note By definition, a digraph is called \e Eulerian if alpar@504: ///and only if it is connected and the number of its incoming and outgoing alpar@504: ///arcs are the same for each node. alpar@505: ///Similarly, an undirected graph is called \e Eulerian if alpar@504: ///and only if it is connected and the number of incident arcs is even alpar@505: ///for each node. Therefore, there are digraphs which are not Eulerian, alpar@505: ///but still have an Euler tour. 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@550: return connected(Undirector(g)); alpar@504: } alpar@504: alpar@504: } alpar@504: alpar@504: #endif