lemon-0.x: lemon/euler.h@a4d1362397fe

     1 /* -*- C++ -*-

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

     3  *

     4  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

     5  * (Egervary Research Group on Combinatorial Optimization, EGRES).

     6  *

     7  * Permission to use, modify and distribute this software is granted

     8  * provided that this copyright notice appears in all copies. For

     9  * precise terms see the accompanying LICENSE file.

    10  *

    11  * This software is provided "AS IS" with no warranty of any kind,

    12  * express or implied, and with no claim as to its suitability for any

    13  * purpose.

    14  *

    15  */

    16 #include<lemon/invalid.h>

    17 #include<lemon/topology.h>

    18 #include <list>

    20 /// \ingroup topology

    21 /// \file

    22 /// \brief Euler tour

    23 ///

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

    25 ///if a graph is euler.

    28 namespace lemon {

    30   ///Euler iterator for directed graphs.

    32   /// \ingroup topology

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

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

    35   ///

    36   ///For example

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

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

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

    40   ///Euler tour of \c g.

    41   ///\code

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

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

    44   ///  }

    45   ///\endcode

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

    47   ///\todo Test required

    48   template<class Graph>

    49   class EulerIt

    50   {

    51     typedef typename Graph::Node Node;

    52     typedef typename Graph::NodeIt NodeIt;

    53     typedef typename Graph::Edge Edge;

    54     typedef typename Graph::EdgeIt EdgeIt;

    55     typedef typename Graph::OutEdgeIt OutEdgeIt;

    56     typedef typename Graph::InEdgeIt InEdgeIt;

    58     const Graph &g;

    59     typename Graph::NodeMap<OutEdgeIt> nedge;

    60     std::list<Edge> euler;

    62   public:

    64     ///Constructor

    66     ///\param _g A directed graph.

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

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

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

    70       : g(_g), nedge(g)

    71     {

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

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

    74       while(nedge[start]!=INVALID) {

    75 	euler.push_back(nedge[start]);

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

    77 	++nedge[start];

    78 	start=next;

    79       }

    80     }

    82     ///Edge Conversion

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

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

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

    87     ///Next edge of the tour

    88     EulerIt &operator++() {

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

    90       euler.pop_front();

    91       //This produces a warning.Strange.

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

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

    94       while(nedge[s]!=INVALID) {

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

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

    97 	++nedge[s];

    98 	s=n;

    99       }

   100       return *this;

   101     }

   102     ///Postfix incrementation

   104     ///\warning This incrementation

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

   106     ///expect.

   107     Edge operator++(int)

   108     {

   109       Edge e=*this;

   110       ++(*this);

   111       return e;

   112     }

   113   };

   115   ///Euler iterator for undirected graphs.

   117   /// \ingroup topology

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

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

   120   ///

   121   ///For example

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

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

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

   125   ///Euler tour of \c g.

   126   ///\code

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

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

   129   ///  }

   130   ///\endcode

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

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

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

   134   ///

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

   136   ///\todo Test required

   137   template<class Graph>

   138   class UndirEulerIt

   139   {

   140     typedef typename Graph::Node Node;

   141     typedef typename Graph::NodeIt NodeIt;

   142     typedef typename Graph::Edge Edge;

   143     typedef typename Graph::EdgeIt EdgeIt;

   144     typedef typename Graph::OutEdgeIt OutEdgeIt;

   145     typedef typename Graph::InEdgeIt InEdgeIt;

   147     const Graph &g;

   148     typename Graph::NodeMap<OutEdgeIt> nedge;

   149     typename Graph::UndirEdgeMap<bool> visited;

   150     std::list<Edge> euler;

   152   public:

   154     ///Constructor

   156     ///\param _g An undirected graph.

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

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

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

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

   161     {

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

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

   164       while(nedge[start]!=INVALID) {

   165 	euler.push_back(nedge[start]);

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

   167 	++nedge[start];

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

   169       }

   170     }

   172     ///Edge Conversion

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

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

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

   177     ///Next edge of the tour

   178     UndirEulerIt &operator++() {

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

   180       euler.pop_front();

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

   183       while(nedge[s]!=INVALID) {

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

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

   186 	else {

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

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

   189 	  ++nedge[s];

   190 	  s=n;

   191 	}

   192       }

   193       return *this;

   194     }

   196     ///Postfix incrementation

   198     ///\warning This incrementation

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

   200     ///expect.

   201     Edge operator++(int)

   202     {

   203       Edge e=*this;

   204       ++(*this);

   205       return e;

   206     }

   207   };

   210   ///Checks if the graph is Euler

   212   /// \ingroup topology

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

   214   ///undirected graphs.

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

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

   217   ///are the same for each node.

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

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

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

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

   222   ///\todo Test required

   223   template<class Graph>

   224 #ifdef DOXYGEN

   225   bool

   226 #else

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

   228   euler(const Graph &g)

   229   {

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

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

   232     return connected(g);

   233   }

   234   template<class Graph>

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

   236 #endif

   237   euler(const Graph &g)

   238   {

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

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

   241     return connected(g);

   242   }

   244 }

author	hegyi
	Tue, 06 Dec 2005 10:53:38 +0000
changeset 1849	a4d1362397fe
parent 1803	ee8dd6872645
child 1875	98698b69a902
permissions	-rw-r--r--