alpar@1738: /* -*- C++ -*-
alpar@1738:  *
alpar@1956:  * This file is a part of LEMON, a generic C++ optimization library
alpar@1956:  *
alpar@2553:  * Copyright (C) 2003-2008
alpar@1956:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1738:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@1738:  *
alpar@1738:  * Permission to use, modify and distribute this software is granted
alpar@1738:  * provided that this copyright notice appears in all copies. For
alpar@1738:  * precise terms see the accompanying LICENSE file.
alpar@1738:  *
alpar@1738:  * This software is provided "AS IS" with no warranty of any kind,
alpar@1738:  * express or implied, and with no claim as to its suitability for any
alpar@1738:  * purpose.
alpar@1738:  *
alpar@1738:  */
alpar@1956: 
deba@1993: #include<lemon/bits/invalid.h>
alpar@1818: #include<lemon/topology.h>
alpar@1738: #include <list>
alpar@1738: 
deba@2429: /// \ingroup graph_prop
alpar@1738: /// \file
alpar@1738: /// \brief Euler tour
alpar@1738: ///
alpar@1738: ///This file provides an Euler tour iterator and ways to check
alpar@1738: ///if a graph is euler.
alpar@1738: 
alpar@1738: 
alpar@1738: namespace lemon {
alpar@1738: 
alpar@1818:   ///Euler iterator for directed graphs.
alpar@1738: 
deba@2429:   /// \ingroup graph_prop
alpar@1738:   ///This iterator converts to the \c Edge type of the graph and using
alpar@1970:   ///operator ++ it provides an Euler tour of a \e directed
alpar@1970:   ///graph (if there exists).
alpar@1738:   ///
alpar@1738:   ///For example
alpar@1738:   ///if the given graph if Euler (i.e it has only one nontrivial component
alpar@1738:   ///and the in-degree is equal to the out-degree for all nodes),
alpar@1970:   ///the following code will put the edges of \c g
alpar@1970:   ///to the vector \c et according to an
alpar@1738:   ///Euler tour of \c g.
alpar@1738:   ///\code
alpar@1970:   ///  std::vector<ListGraph::Edge> et;
alpar@1970:   ///  for(EulerIt<ListGraph> e(g),e!=INVALID;++e)
alpar@1970:   ///    et.push_back(e);
alpar@1738:   ///\endcode
alpar@1738:   ///If \c g is not Euler then the resulted tour will not be full or closed.
alpar@1970:   ///\sa UEulerIt
alpar@1738:   ///\todo Test required
alpar@1738:   template<class Graph>
alpar@1738:   class EulerIt 
alpar@1738:   {
alpar@1738:     typedef typename Graph::Node Node;
alpar@1738:     typedef typename Graph::NodeIt NodeIt;
alpar@1738:     typedef typename Graph::Edge Edge;
alpar@1738:     typedef typename Graph::EdgeIt EdgeIt;
alpar@1738:     typedef typename Graph::OutEdgeIt OutEdgeIt;
alpar@1738:     typedef typename Graph::InEdgeIt InEdgeIt;
alpar@1738:     
alpar@1738:     const Graph &g;
deba@2405:     typename Graph::template NodeMap<OutEdgeIt> nedge;
alpar@1738:     std::list<Edge> euler;
alpar@1738: 
alpar@1738:   public:
alpar@1738:     
alpar@1738:     ///Constructor
alpar@1738: 
alpar@1738:     ///\param _g A directed graph.
alpar@1738:     ///\param start The starting point of the tour. If it is not given
alpar@1803:     ///       the tour will start from the first node.
alpar@1738:     EulerIt(const Graph &_g,typename Graph::Node start=INVALID)
alpar@1738:       : g(_g), nedge(g)
alpar@1738:     {
alpar@1738:       if(start==INVALID) start=NodeIt(g);
alpar@1738:       for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutEdgeIt(g,n);
alpar@1738:       while(nedge[start]!=INVALID) {
alpar@1738: 	euler.push_back(nedge[start]);
alpar@1738: 	Node next=g.target(nedge[start]);
alpar@1738: 	++nedge[start];
alpar@1738: 	start=next;
alpar@1738:       }
alpar@1738:     }
alpar@1738:     
alpar@1738:     ///Edge Conversion
alpar@1738:     operator Edge() { return euler.empty()?INVALID:euler.front(); }
alpar@1738:     bool operator==(Invalid) { return euler.empty(); }
alpar@1738:     bool operator!=(Invalid) { return !euler.empty(); }
alpar@1738:     
alpar@1738:     ///Next edge of the tour
alpar@1738:     EulerIt &operator++() {
alpar@1738:       Node s=g.target(euler.front());
alpar@1738:       euler.pop_front();
alpar@1738:       //This produces a warning.Strange.
alpar@1738:       //std::list<Edge>::iterator next=euler.begin();
alpar@1738:       typename std::list<Edge>::iterator next=euler.begin();
alpar@1738:       while(nedge[s]!=INVALID) {
alpar@1738: 	euler.insert(next,nedge[s]);
alpar@1738: 	Node n=g.target(nedge[s]);
alpar@1738: 	++nedge[s];
alpar@1738: 	s=n;
alpar@1738:       }
alpar@1738:       return *this;
alpar@1738:     }
alpar@1738:     ///Postfix incrementation
alpar@1738:     
alpar@1803:     ///\warning This incrementation
alpar@1803:     ///returns an \c Edge, not an \ref EulerIt, as one may
alpar@1803:     ///expect.
alpar@1738:     Edge operator++(int) 
alpar@1738:     {
alpar@1738:       Edge e=*this;
alpar@1738:       ++(*this);
alpar@1738:       return e;
alpar@1738:     }
alpar@1738:   };
alpar@1738: 
alpar@1818:   ///Euler iterator for undirected graphs.
alpar@1818: 
deba@2429:   /// \ingroup graph_prop
alpar@2350:   ///This iterator converts to the \c Edge (or \c UEdge)
alpar@1970:   ///type of the graph and using
alpar@2350:   ///operator ++ it provides an Euler tour of an undirected
alpar@1970:   ///graph (if there exists).
alpar@1818:   ///
alpar@1818:   ///For example
alpar@1818:   ///if the given graph if Euler (i.e it has only one nontrivial component
alpar@1818:   ///and the degree of each node is even),
alpar@1818:   ///the following code will print the edge IDs according to an
alpar@1818:   ///Euler tour of \c g.
alpar@1818:   ///\code
klao@1909:   ///  for(UEulerIt<ListUGraph> e(g),e!=INVALID;++e) {
klao@1909:   ///    std::cout << g.id(UEdge(e)) << std::eol;
alpar@1818:   ///  }
alpar@1818:   ///\endcode
alpar@1818:   ///Although the iterator provides an Euler tour of an undirected graph,
klao@1909:   ///in order to indicate the direction of the tour, UEulerIt
alpar@1818:   ///returns directed edges (that convert to the undirected ones, of course).
alpar@1818:   ///
alpar@1818:   ///If \c g is not Euler then the resulted tour will not be full or closed.
alpar@1970:   ///\sa EulerIt
alpar@1818:   ///\todo Test required
alpar@1818:   template<class Graph>
klao@1909:   class UEulerIt
alpar@1818:   {
alpar@1818:     typedef typename Graph::Node Node;
alpar@1818:     typedef typename Graph::NodeIt NodeIt;
alpar@1818:     typedef typename Graph::Edge Edge;
alpar@2445:     typedef typename Graph::UEdge UEdge;
alpar@1818:     typedef typename Graph::EdgeIt EdgeIt;
alpar@1818:     typedef typename Graph::OutEdgeIt OutEdgeIt;
alpar@1818:     typedef typename Graph::InEdgeIt InEdgeIt;
alpar@1818:     
alpar@1818:     const Graph &g;
deba@2405:     typename Graph::template NodeMap<OutEdgeIt> nedge;
deba@2405:     typename Graph::template UEdgeMap<bool> visited;
alpar@1818:     std::list<Edge> euler;
alpar@1818: 
alpar@1818:   public:
alpar@1818:     
alpar@1818:     ///Constructor
alpar@1818: 
alpar@1818:     ///\param _g An undirected graph.
alpar@1818:     ///\param start The starting point of the tour. If it is not given
alpar@1818:     ///       the tour will start from the first node.
klao@1909:     UEulerIt(const Graph &_g,typename Graph::Node start=INVALID)
alpar@1818:       : g(_g), nedge(g), visited(g,false)
alpar@1818:     {
alpar@1818:       if(start==INVALID) start=NodeIt(g);
alpar@1818:       for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutEdgeIt(g,n);
alpar@1818:       while(nedge[start]!=INVALID) {
alpar@1818: 	euler.push_back(nedge[start]);
alpar@2445: 	visited[nedge[start]]=true;
alpar@1818: 	Node next=g.target(nedge[start]);
alpar@1818: 	++nedge[start];
alpar@2445: 	start=next;
alpar@2445: 	while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start];
alpar@1818:       }
alpar@1818:     }
alpar@1818:     
alpar@1818:     ///Edge Conversion
alpar@2445:     operator Edge() const { return euler.empty()?INVALID:euler.front(); }
alpar@2445:     ///Edge Conversion
alpar@2445:     operator UEdge() const { return euler.empty()?INVALID:euler.front(); }
alpar@2445:     ///\e
alpar@2445:     bool operator==(Invalid) const { return euler.empty(); }
alpar@2445:     ///\e
alpar@2445:     bool operator!=(Invalid) const { return !euler.empty(); }
alpar@1818:     
alpar@1818:     ///Next edge of the tour
klao@1909:     UEulerIt &operator++() {
alpar@1818:       Node s=g.target(euler.front());
alpar@1818:       euler.pop_front();
alpar@1818:       typename std::list<Edge>::iterator next=euler.begin();
alpar@1818: 
alpar@1818:       while(nedge[s]!=INVALID) {
alpar@1818: 	while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s];
alpar@1818: 	if(nedge[s]==INVALID) break;
alpar@1818: 	else {
alpar@1818: 	  euler.insert(next,nedge[s]);
alpar@2445: 	  visited[nedge[s]]=true;
alpar@1818: 	  Node n=g.target(nedge[s]);
alpar@1818: 	  ++nedge[s];
alpar@1818: 	  s=n;
alpar@1818: 	}
alpar@1818:       }
alpar@1818:       return *this;
alpar@1818:     }
alpar@1818:     
alpar@1818:     ///Postfix incrementation
alpar@1818:     
alpar@1818:     ///\warning This incrementation
klao@1909:     ///returns an \c Edge, not an \ref UEulerIt, as one may
alpar@1818:     ///expect.
alpar@1818:     Edge operator++(int) 
alpar@1818:     {
alpar@1818:       Edge e=*this;
alpar@1818:       ++(*this);
alpar@1818:       return e;
alpar@1818:     }
alpar@1818:   };
alpar@1818: 
alpar@1818: 
alpar@1738:   ///Checks if the graph is Euler
alpar@1738: 
deba@2429:   /// \ingroup graph_prop
alpar@1738:   ///Checks if the graph is Euler. It works for both directed and
alpar@1738:   ///undirected graphs.
alpar@1818:   ///\note By definition, a directed graph is called \e Euler if
alpar@1818:   ///and only if connected and the number of it is incoming and outgoing edges
alpar@1818:   ///are the same for each node.
alpar@1818:   ///Similarly, an undirected graph is called \e Euler if
alpar@1818:   ///and only if it is connected and the number of incident edges is even
alpar@1818:   ///for each node. <em>Therefore, there are graphs which are not Euler, but
alpar@1818:   ///still have an Euler tour</em>.
alpar@1738:   ///\todo Test required
alpar@1738:   template<class Graph>
alpar@1738: #ifdef DOXYGEN
alpar@1738:   bool
alpar@1738: #else
deba@1979:   typename enable_if<UndirectedTagIndicator<Graph>,bool>::type
alpar@1818:   euler(const Graph &g) 
alpar@1818:   {
alpar@1818:     for(typename Graph::NodeIt n(g);n!=INVALID;++n)
alpar@1818:       if(countIncEdges(g,n)%2) return false;
alpar@1818:     return connected(g);
alpar@1818:   }
alpar@1818:   template<class Graph>
deba@1979:   typename disable_if<UndirectedTagIndicator<Graph>,bool>::type
alpar@1738: #endif
alpar@1738:   euler(const Graph &g) 
alpar@1738:   {
alpar@1738:     for(typename Graph::NodeIt n(g);n!=INVALID;++n)
alpar@1738:       if(countInEdges(g,n)!=countOutEdges(g,n)) return false;
alpar@1818:     return connected(g);
alpar@1738:   }
alpar@1738:   
alpar@1738: }