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

Timestamp:

11/21/05 10:08:16 (18 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2367

Message:

UndirEulerIt? added

File:

• lemon/euler.h (modified) (5 diffs)

lemon/euler.h

@@ -1 +1 @@
 /* -*- C++ -*-
- * lemon/topology.h - Part of LEMON, a generic C++ optimization library
+ * lemon/euler.h - Part of LEMON, a generic C++ optimization library
  *
  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
@@ -15 +15 @@
  */
 #include<lemon/invalid.h>
+#include<lemon/topology.h>
 #include <list>
 
@@ -27 +28 @@
 namespace lemon {
 
-  ///Euler iterator in directed graphs.
+  ///Euler iterator for directed graphs.
 
   /// \ingroup topology
@@ -112 +113 @@
   };
 
+  ///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 gutils
+  /// \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>
@@ -123 +226 @@
 #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(countIncEdges(g,n)%2) return false;
-    return true;
-  }
-  template<class Graph>
-  typename disable_if<typename Graph::UndirTag,bool>::type
-  euler(const Graph &g) 
-  {
-    for(typename Graph::NodeIt n(g);n!=INVALID;++n)
       if(countInEdges(g,n)!=countOutEdges(g,n)) return false;
-    return true;
+    return connected(g);
   }