COIN-OR::LEMON - Graph Library

Changeset 1818:8f9905c4e1c1 in lemon-0.x for lemon/euler.h


Ignore:
Timestamp:
11/21/05 10:08:16 (14 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2367
Message:

UndirEulerIt? added

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/euler.h

    r1803 r1818  
    11/* -*- C++ -*-
    2  * lemon/topology.h - Part of LEMON, a generic C++ optimization library
     2 * lemon/euler.h - Part of LEMON, a generic C++ optimization library
    33 *
    44 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     
    1515 */
    1616#include<lemon/invalid.h>
     17#include<lemon/topology.h>
    1718#include <list>
    1819
     
    2728namespace lemon {
    2829
    29   ///Euler iterator in directed graphs.
     30  ///Euler iterator for directed graphs.
    3031
    3132  /// \ingroup topology
     
    112113  };
    113114
     115  ///Euler iterator for undirected graphs.
     116
     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;
     146   
     147    const Graph &g;
     148    typename Graph::NodeMap<OutEdgeIt> nedge;
     149    typename Graph::UndirEdgeMap<bool> visited;
     150    std::list<Edge> euler;
     151
     152  public:
     153   
     154    ///Constructor
     155
     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    }
     171   
     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(); }
     176   
     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();
     182
     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    }
     195   
     196    ///Postfix incrementation
     197   
     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  };
     208
     209
    114210  ///Checks if the graph is Euler
    115211
    116   /// \ingroup gutils
     212  /// \ingroup topology
    117213  ///Checks if the graph is Euler. It works for both directed and
    118214  ///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>.
    119222  ///\todo Test required
    120223  template<class Graph>
     
    123226#else
    124227  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
    125236#endif
    126237  euler(const Graph &g)
    127238  {
    128239    for(typename Graph::NodeIt n(g);n!=INVALID;++n)
    129       if(countIncEdges(g,n)%2) return false;
    130     return true;
    131   }
    132   template<class Graph>
    133   typename disable_if<typename Graph::UndirTag,bool>::type
    134   euler(const Graph &g)
    135   {
    136     for(typename Graph::NodeIt n(g);n!=INVALID;++n)
    137240      if(countInEdges(g,n)!=countOutEdges(g,n)) return false;
    138     return true;
     241    return connected(g);
    139242  }
    140243 
Note: See TracChangeset for help on using the changeset viewer.