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