/* -*- C++ -*-

 * lemon/euler.h - Part of LEMON, a generic C++ optimization library

 *

 * Copyright (C) 2006 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.

 *

 */

#include<lemon/invalid.h>

#include<lemon/topology.h>

#include <list>

/// \ingroup topology

/// \file

/// \brief Euler tour

///

///This file provides an Euler tour iterator and ways to check

///if a graph is euler.

namespace lemon {

  ///Euler iterator for directed graphs.

  /// \ingroup topology

  ///This iterator converts to the \c Edge type of the graph and using

  ///operator ++ it provides an Euler tour of the graph (if there exists).

  ///

  ///For example

  ///if the given graph if Euler (i.e it has only one nontrivial component

  ///and the in-degree is equal to the out-degree for all nodes),

  ///the following code will print the edge IDs according to an

  ///Euler tour of \c g.

  ///\code

  ///  for(EulerIt<ListGraph> e(g),e!=INVALID;++e) {

  ///    std::cout << g.id(e) << std::eol;

  ///  }

  ///\endcode

  ///If \c g is not Euler then the resulted tour will not be full or closed.

  ///\todo Test required

  template<class Graph>

  class EulerIt 

  {

    typedef typename Graph::Node Node;

    typedef typename Graph::NodeIt NodeIt;

    typedef typename Graph::Edge Edge;

    typedef typename Graph::EdgeIt EdgeIt;

    typedef typename Graph::OutEdgeIt OutEdgeIt;

    typedef typename Graph::InEdgeIt InEdgeIt;

    const Graph &g;

    typename Graph::NodeMap<OutEdgeIt> nedge;

    std::list<Edge> euler;

  public:

    ///Constructor

    ///\param _g A directed graph.

    ///\param start The starting point of the tour. If it is not given

    ///       the tour will start from the first node.

    EulerIt(const Graph &_g,typename Graph::Node start=INVALID)

      : g(_g), nedge(g)

    {

      if(start==INVALID) start=NodeIt(g);

      for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutEdgeIt(g,n);

      while(nedge[start]!=INVALID) {

	euler.push_back(nedge[start]);

	Node next=g.target(nedge[start]);

	++nedge[start];

	start=next;

      }

    }

    ///Edge Conversion

    operator Edge() { return euler.empty()?INVALID:euler.front(); }

    bool operator==(Invalid) { return euler.empty(); }

    bool operator!=(Invalid) { return !euler.empty(); }

    ///Next edge of the tour

    EulerIt &operator++() {

      Node s=g.target(euler.front());

      euler.pop_front();

      //This produces a warning.Strange.

      //std::list<Edge>::iterator next=euler.begin();

      typename std::list<Edge>::iterator next=euler.begin();

      while(nedge[s]!=INVALID) {

	euler.insert(next,nedge[s]);

	Node n=g.target(nedge[s]);

	++nedge[s];

	s=n;

      }

      return *this;

    }

    ///Postfix incrementation

    ///\warning This incrementation

    ///returns an \c Edge, not an \ref EulerIt, as one may

    ///expect.

    Edge operator++(int) 

    {

      Edge e=*this;

      ++(*this);

      return e;

    }

  };

  ///Euler iterator for undirected graphs.

  /// \ingroup topology

  ///This iterator converts to the \c Edge type of the graph and using

  ///operator ++ it provides an Euler tour of the graph (if there exists).

  ///

  ///For example

  ///if the given graph if Euler (i.e it has only one nontrivial component

  ///and the degree of each node is even),

  ///the following code will print the edge IDs according to an

  ///Euler tour of \c g.

  ///\code

  ///  for(UndirEulerIt<UndirListGraph> e(g),e!=INVALID;++e) {

  ///    std::cout << g.id(UndirEdge(e)) << std::eol;

  ///  }

  ///\endcode

  ///Although the iterator provides an Euler tour of an undirected graph,

  ///in order to indicate the direction of the tour, UndirEulerIt

  ///returns directed edges (that convert to the undirected ones, of course).

  ///

  ///If \c g is not Euler then the resulted tour will not be full or closed.

  ///\todo Test required

  template<class Graph>

  class UndirEulerIt

  {

    typedef typename Graph::Node Node;

    typedef typename Graph::NodeIt NodeIt;

    typedef typename Graph::Edge Edge;

    typedef typename Graph::EdgeIt EdgeIt;

    typedef typename Graph::OutEdgeIt OutEdgeIt;

    typedef typename Graph::InEdgeIt InEdgeIt;

    const Graph &g;

    typename Graph::NodeMap<OutEdgeIt> nedge;

    typename Graph::UndirEdgeMap<bool> visited;

    std::list<Edge> euler;

  public:

    ///Constructor

    ///\param _g An undirected graph.

    ///\param start The starting point of the tour. If it is not given

    ///       the tour will start from the first node.

    UndirEulerIt(const Graph &_g,typename Graph::Node start=INVALID)

      : g(_g), nedge(g), visited(g,false)

    {

      if(start==INVALID) start=NodeIt(g);

      for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutEdgeIt(g,n);

      while(nedge[start]!=INVALID) {

	euler.push_back(nedge[start]);

	Node next=g.target(nedge[start]);

	++nedge[start];

	start=next;	while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start];

      }

    }

    ///Edge Conversion

    operator Edge() { return euler.empty()?INVALID:euler.front(); }

    bool operator==(Invalid) { return euler.empty(); }

    bool operator!=(Invalid) { return !euler.empty(); }

    ///Next edge of the tour

    UndirEulerIt &operator++() {

      Node s=g.target(euler.front());

      euler.pop_front();

      typename std::list<Edge>::iterator next=euler.begin();

      while(nedge[s]!=INVALID) {

	while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s];

	if(nedge[s]==INVALID) break;

	else {

	  euler.insert(next,nedge[s]);

	  Node n=g.target(nedge[s]);

	  ++nedge[s];

	  s=n;

	}

      }

      return *this;

    }

    ///Postfix incrementation

    ///\warning This incrementation

    ///returns an \c Edge, not an \ref UndirEulerIt, as one may

    ///expect.

    Edge operator++(int) 

    {

      Edge e=*this;

      ++(*this);

      return e;

    }

  };

  ///Checks if the graph is Euler

  /// \ingroup topology

  ///Checks if the graph is Euler. It works for both directed and

  ///undirected graphs.

  ///\note By definition, a directed graph is called \e Euler if

  ///and only if connected and the number of it is incoming and outgoing edges

  ///are the same for each node.

  ///Similarly, an undirected graph is called \e Euler if

  ///and only if it is connected and the number of incident edges is even

  ///for each node. <em>Therefore, there are graphs which are not Euler, but

  ///still have an Euler tour</em>.

  ///\todo Test required

  template<class Graph>

#ifdef DOXYGEN

  bool

#else

  typename enable_if<typename Graph::UndirTag,bool>::type

  euler(const Graph &g) 

  {

    for(typename Graph::NodeIt n(g);n!=INVALID;++n)

      if(countIncEdges(g,n)%2) return false;

    return connected(g);

  }

  template<class Graph>

  typename disable_if<typename Graph::UndirTag,bool>::type

#endif

  euler(const Graph &g) 

  {

    for(typename Graph::NodeIt n(g);n!=INVALID;++n)

      if(countInEdges(g,n)!=countOutEdges(g,n)) return false;

    return connected(g);

  }

}