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