LEMON/LEMON-official Changeset - r642:16d7255a6849

Repositories » LEMON » LEMON-official

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r642:16d7255a6849

« 639:2ebfdb
« 641:d657c7

647:0ba8df »

r642:16d7255a6849

Sat, 18 Apr 2009 09:51:54

[Not Reviewed]

0 comments (0 inline)

alpar (Alpar Juttner)
alpar@cs.elte.hu

Merge

0 2 0

merge default

0 files changed with 254 insertions and 161 deletions:

lemon/euler.h

111

test/euler_test.cc

143

↑ Collapse diff ↑

lemon/euler.h

Show inline comments

@@ -26,33 +26,31 @@
 		/// \ingroup graph_properties
 		/// \file
 		/// \brief Euler tour
+		/// \brief Euler tour iterators and a function for checking the \e Eulerian
 		/// property.
 		///
 		///This file provides an Euler tour iterator and ways to check
 		///if a digraph is euler.
+		///This file provides Euler tour iterators and a function to check
 		///if a (di)graph is \e Eulerian.
 		namespace lemon {
 		  ///Euler iterator for digraphs.
+		  ///Euler tour iterator for digraphs.
 		  /// \ingroup graph_properties
 		  ///This iterator converts to the \c Arc type of the digraph and using
 		  ///operator ++, it provides an Euler tour of a \e directed
 		  ///graph (if there exists).
 		  /// \ingroup graph_prop
 		  ///This iterator provides an Euler tour (Eulerian circuit) of a \e directed
 		  ///graph (if there exists) and it converts to the \c Arc type of the digraph.
 		  ///
 		  ///For example
 		  ///if the given digraph is 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 put the arcs of \c g
 		  ///to the vector \c et according to an
 		  ///Euler tour of \c g.
 		  ///For example, if the given digraph has an Euler tour (i.e it has only one
 		  ///non-trivial component and the in-degree is equal to the out-degree
 		  ///for all nodes), then the following code will put the arcs of \c g
 		  ///to the vector \c et according to an Euler tour of \c g.
 		  ///\code
 		  ///  std::vector<ListDigraph::Arc> et;
-		  ///  for(DiEulerIt<ListDigraph> e(g),e!=INVALID;++e)
+		  ///  for(DiEulerIt<ListDigraph> e(g); e!=INVALID; ++e)
 		  ///    et.push_back(e);
 		  ///\endcode
-		  ///If \c g is not Euler then the resulted tour will not be full or closed.
+		  ///If \c g has no Euler tour, then the resulted walk will not be closed
 		  ///or not contain all arcs.
 		  ///\sa EulerIt
 		  template<typename GR>
 		  class DiEulerIt
@@ -65,53 +63,65 @@
 		    typedef typename GR::InArcIt InArcIt;
 		    const GR &g;
-		    typename GR::template NodeMap<OutArcIt> nedge;
+		    typename GR::template NodeMap<OutArcIt> narc;
 		    std::list<Arc> euler;
 		  public:
 		    ///Constructor
 		    ///Constructor.
 		    ///\param gr A digraph.
 		    ///\param start The starting point of the tour. If it is not given
 		    ///       the tour will start from the first node.
 		    ///\param start The starting point of the tour. If it is not given,
 		    ///the tour will start from the first node that has an outgoing arc.
 		    DiEulerIt(const GR &gr, typename GR::Node start = INVALID)
-		      : g(gr), nedge(g)
+		      : g(gr), narc(g)
+		    {
 		      if(start==INVALID) start=NodeIt(g);
 		      for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n);
 		      while(nedge[start]!=INVALID) {
 		        euler.push_back(nedge[start]);
 		        Node next=g.target(nedge[start]);
 		        ++nedge[start];
-		        start=next;
+		      if (start==INVALID) {
 		        NodeIt n(g);
 		        while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n;
 		        start=n;
+		      }
 		      if (start!=INVALID) {
 		        for (NodeIt n(g); n!=INVALID; ++n) narc[n]=OutArcIt(g,n);
 		        while (narc[start]!=INVALID) {
 		          euler.push_back(narc[start]);
 		          Node next=g.target(narc[start]);
 		          ++narc[start];
 		          start=next;
+		        }
+		      }
+		    }
-		    ///Arc Conversion
+		    ///Arc conversion
 		    operator Arc() { return euler.empty()?INVALID:euler.front(); }
 		    ///Compare with \c INVALID
 		    bool operator==(Invalid) { return euler.empty(); }
 		    ///Compare with \c INVALID
 		    bool operator!=(Invalid) { return !euler.empty(); }
 		    ///Next arc of the tour
 		    ///Next arc of the tour
 		    ///
 		    DiEulerIt &operator++() {
 		      Node s=g.target(euler.front());
 		      euler.pop_front();
 		      //This produces a warning.Strange.
 		      //std::list<Arc>::iterator next=euler.begin();
 		      typename std::list<Arc>::iterator next=euler.begin();
 		      while(nedge[s]!=INVALID) {
 		        euler.insert(next,nedge[s]);
 		        Node n=g.target(nedge[s]);
 		        ++nedge[s];
 		      while(narc[s]!=INVALID) {
 		        euler.insert(next,narc[s]);
 		        Node n=g.target(narc[s]);
 		        ++narc[s];
 		        s=n;
+		      }
 		      return *this;
+		    }
 		    ///Postfix incrementation
 		    /// Postfix incrementation.
 		    ///
 		    ///\warning This incrementation
-		    ///returns an \c Arc, not an \ref DiEulerIt, as one may
+		    ///returns an \c Arc, not a \ref DiEulerIt, as one may
 		    ///expect.
 		    Arc operator++(int)
+		    {
@@ -121,30 +131,28 @@
+		    }
 		  };
 		  ///Euler iterator for graphs.
+		  ///Euler tour iterator for graphs.
 		  /// \ingroup graph_properties
 		  ///This iterator converts to the \c Arc (or \c Edge)
 		  ///type of the digraph and using
 		  ///operator ++, it provides an Euler tour of an undirected
 		  ///digraph (if there exists).
 		  ///This iterator provides an Euler tour (Eulerian circuit) of an
 		  ///\e undirected graph (if there exists) and it converts to the \c Arc
 		  ///and \c Edge types of the graph.
 		  ///
 		  ///For example
 		  ///if the given digraph if Euler (i.e it has only one nontrivial component
-		  ///and the degree of each node is even),
+		  ///For example, if the given graph has an Euler tour (i.e it has only one
 		  ///non-trivial component and the degree of each node is even),
 		  ///the following code will print the arc IDs according to an
 		  ///Euler tour of \c g.
 		  ///\code
-		  ///  for(EulerIt<ListGraph> e(g),e!=INVALID;++e) {
+		  ///  for(EulerIt<ListGraph> e(g); e!=INVALID; ++e) {
 		  ///    std::cout << g.id(Edge(e)) << std::eol;
 		  ///  }
 		  ///\endcode
 		  ///Although the iterator provides an Euler tour of an graph,
 		  ///it still returns Arcs in order to indicate the direction of the tour.
-		  ///(But Arc will convert to Edges, of course).
+		  ///Although this iterator is for undirected graphs, it still returns
 		  ///arcs in order to indicate the direction of the tour.
 		  ///(But arcs convert to edges, of course.)
 		  ///
 		  ///If \c g is not Euler then the resulted tour will not be full or closed.
 		  ///\sa EulerIt
 		  ///If \c g has no Euler tour, then the resulted walk will not be closed
 		  ///or not contain all edges.
 		  template<typename GR>
 		  class EulerIt
+		  {
@@ -157,7 +165,7 @@
 		    typedef typename GR::InArcIt InArcIt;
 		    const GR &g;
-		    typename GR::template NodeMap<OutArcIt> nedge;
+		    typename GR::template NodeMap<OutArcIt> narc;
 		    typename GR::template EdgeMap<bool> visited;
 		    std::list<Arc> euler;
@@ -165,47 +173,56 @@
 		    ///Constructor
 		    ///\param gr An graph.
 		    ///\param start The starting point of the tour. If it is not given
-		    ///       the tour will start from the first node.
+		    ///Constructor.
 		    ///\param gr A graph.
 		    ///\param start The starting point of the tour. If it is not given,
 		    ///the tour will start from the first node that has an incident edge.
 		    EulerIt(const GR &gr, typename GR::Node start = INVALID)
-		      : g(gr), nedge(g), visited(g, false)
+		      : g(gr), narc(g), visited(g, false)
+		    {
 		      if(start==INVALID) start=NodeIt(g);
 		      for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n);
 		      while(nedge[start]!=INVALID) {
 		        euler.push_back(nedge[start]);
 		        visited[nedge[start]]=true;
 		        Node next=g.target(nedge[start]);
 		        ++nedge[start];
 		        start=next;
-		        while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start];
+		      if (start==INVALID) {
 		        NodeIt n(g);
 		        while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n;
 		        start=n;
+		      }
 		      if (start!=INVALID) {
 		        for (NodeIt n(g); n!=INVALID; ++n) narc[n]=OutArcIt(g,n);
 		        while(narc[start]!=INVALID) {
 		          euler.push_back(narc[start]);
 		          visited[narc[start]]=true;
 		          Node next=g.target(narc[start]);
 		          ++narc[start];
 		          start=next;
 		          while(narc[start]!=INVALID && visited[narc[start]]) ++narc[start];
+		        }
+		      }
+		    }
-		    ///Arc Conversion
+		    ///Arc conversion
 		    operator Arc() const { return euler.empty()?INVALID:euler.front(); }
-		    ///Arc Conversion
+		    ///Edge conversion
 		    operator Edge() const { return euler.empty()?INVALID:euler.front(); }
-		    ///\e
+		    ///Compare with \c INVALID
 		    bool operator==(Invalid) const { return euler.empty(); }
-		    ///\e
+		    ///Compare with \c INVALID
 		    bool operator!=(Invalid) const { return !euler.empty(); }
 		    ///Next arc of the tour
 		    ///Next arc of the tour
 		    ///
 		    EulerIt &operator++() {
 		      Node s=g.target(euler.front());
 		      euler.pop_front();
 		      typename std::list<Arc>::iterator next=euler.begin();
 		      while(nedge[s]!=INVALID) {
 		        while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s];
 		        if(nedge[s]==INVALID) break;
 		      while(narc[s]!=INVALID) {
 		        while(narc[s]!=INVALID && visited[narc[s]]) ++narc[s];
 		        if(narc[s]==INVALID) break;
 		        else {
 		          euler.insert(next,nedge[s]);
 		          visited[nedge[s]]=true;
 		          Node n=g.target(nedge[s]);
 		          ++nedge[s];
 		          euler.insert(next,narc[s]);
 		          visited[narc[s]]=true;
 		          Node n=g.target(narc[s]);
 		          ++narc[s];
 		          s=n;
+		        }
+		      }
@@ -214,9 +231,10 @@
 		    ///Postfix incrementation
 		    ///\warning This incrementation
 		    ///returns an \c Arc, not an \ref EulerIt, as one may
-		    ///expect.
+		    /// Postfix incrementation.
 		    ///
 		    ///\warning This incrementation returns an \c Arc (which converts to
 		    ///an \c Edge), not an \ref EulerIt, as one may expect.
 		    Arc operator++(int)
+		    {
 		      Arc e=*this;
@@ -226,18 +244,23 @@
 		  };
-		  ///Checks if the graph is Eulerian
+		  ///Check if the given graph is \e Eulerian
 		  /// \ingroup graph_properties
 		  ///Checks if the graph is Eulerian. It works for both directed and undirected
 		  ///graphs.
 		  ///\note By definition, a digraph is called \e Eulerian if
 		  ///and only if it is connected and the number of its incoming and outgoing
 		  ///This function checks if the given graph is \e Eulerian.
 		  ///It works for both directed and undirected graphs.
 		  ///
 		  ///By definition, a digraph is called \e Eulerian if
 		  ///and only if it is connected and the number of incoming and outgoing
 		  ///arcs are the same for each node.
 		  ///Similarly, an undirected graph is called \e Eulerian if
 		  ///and only if it is connected and the number of incident arcs is even
 		  ///for each node. <em>Therefore, there are digraphs which are not Eulerian,
-		  ///but still have an Euler tour</em>.
+		  ///and only if it is connected and the number of incident edges is even
 		  ///for each node.
 		  ///
 		  ///\note There are (di)graphs that are not Eulerian, but still have an
 		  /// Euler tour, since they may contain isolated nodes.
 		  ///
 		  ///\sa DiEulerIt, EulerIt
 		  template<typename GR>
 		#ifdef DOXYGEN
 		  bool
@@ -256,7 +279,7 @@
+		  {
 		    for(typename GR::NodeIt n(g);n!=INVALID;++n)
 		      if(countInArcs(g,n)!=countOutArcs(g,n)) return false;
-		    return connected(Undirector<const GR>(g));
+		    return connected(undirector(g));
+		  }
+		}

test/euler_test.cc

Show inline comments

@@ -18,136 +18,206 @@
 		#include <lemon/euler.h>
 		#include <lemon/list_graph.h>
-		#include <test/test_tools.h>
+		#include <lemon/adaptors.h>
 		#include "test_tools.h"
 		using namespace lemon;
 		template <typename Digraph>
-		void checkDiEulerIt(const Digraph& g)
+		void checkDiEulerIt(const Digraph& g,
 		                    const typename Digraph::Node& start = INVALID)
+		{
 		  typename Digraph::template ArcMap<int> visitationNumber(g, 0);
 		  DiEulerIt<Digraph> e(g);
+		  DiEulerIt<Digraph> e(g, start);
 		  if (e == INVALID) return;
 		  typename Digraph::Node firstNode = g.source(e);
 		  typename Digraph::Node lastNode = g.target(e);
 		  if (start != INVALID) {
 		    check(firstNode == start, "checkDiEulerIt: Wrong first node");
+		  }
 		  for (; e != INVALID; ++e)
+		  {
 		    if (e != INVALID)
+		    {
 		      lastNode = g.target(e);
+		    }
 		  for (; e != INVALID; ++e) {
 		    if (e != INVALID) lastNode = g.target(e);
 		    ++visitationNumber[e];
+		  }
 		  check(firstNode == lastNode,
-		      "checkDiEulerIt: first and last node are not the same");
+		      "checkDiEulerIt: First and last nodes are not the same");
 		  for (typename Digraph::ArcIt a(g); a != INVALID; ++a)
+		  {
 		    check(visitationNumber[a] == 1,
-		        "checkDiEulerIt: not visited or multiple times visited arc found");
+		        "checkDiEulerIt: Not visited or multiple times visited arc found");
+		  }
+		}
 		template <typename Graph>
-		void checkEulerIt(const Graph& g)
+		void checkEulerIt(const Graph& g,
 		                  const typename Graph::Node& start = INVALID)
+		{
 		  typename Graph::template EdgeMap<int> visitationNumber(g, 0);
 		  EulerIt<Graph> e(g);
 		  typename Graph::Node firstNode = g.u(e);
-		  typename Graph::Node lastNode = g.v(e);
+		  EulerIt<Graph> e(g, start);
 		  if (e == INVALID) return;
 		  typename Graph::Node firstNode = g.source(typename Graph::Arc(e));
 		  typename Graph::Node lastNode = g.target(typename Graph::Arc(e));
 		  if (start != INVALID) {
 		    check(firstNode == start, "checkEulerIt: Wrong first node");
+		  }
 		  for (; e != INVALID; ++e)
+		  {
 		    if (e != INVALID)
+		    {
 		      lastNode = g.v(e);
+		    }
 		  for (; e != INVALID; ++e) {
 		    if (e != INVALID) lastNode = g.target(typename Graph::Arc(e));
 		    ++visitationNumber[e];
+		  }
 		  check(firstNode == lastNode,
-		      "checkEulerIt: first and last node are not the same");
+		      "checkEulerIt: First and last nodes are not the same");
 		  for (typename Graph::EdgeIt e(g); e != INVALID; ++e)
+		  {
 		    check(visitationNumber[e] == 1,
-		        "checkEulerIt: not visited or multiple times visited edge found");
+		        "checkEulerIt: Not visited or multiple times visited edge found");
+		  }
+		}
 		int main()
+		{
 		  typedef ListDigraph Digraph;
-		  typedef ListGraph Graph;
+		  typedef Undirector<Digraph> Graph;
+		  {
 		    Digraph d;
 		    Graph g(d);
 		    checkDiEulerIt(d);
 		    checkDiEulerIt(g);
 		    checkEulerIt(g);
-		  Digraph digraphWithEulerianCircuit;
+		    check(eulerian(d), "This graph is Eulerian");
 		    check(eulerian(g), "This graph is Eulerian");
+		  }
+		  {
-		    Digraph& g = digraphWithEulerianCircuit;
+		    Digraph d;
 		    Graph g(d);
 		    Digraph::Node n = d.addNode();
 		    Digraph::Node n0 = g.addNode();
 		    Digraph::Node n1 = g.addNode();
-		    Digraph::Node n2 = g.addNode();
+		    checkDiEulerIt(d);
 		    checkDiEulerIt(g);
 		    checkEulerIt(g);
 		    g.addArc(n0, n1);
 		    g.addArc(n1, n0);
 		    g.addArc(n1, n2);
 		    g.addArc(n2, n1);
 		    check(eulerian(d), "This graph is Eulerian");
 		    check(eulerian(g), "This graph is Eulerian");
+		  }
+		  {
 		    Digraph d;
 		    Graph g(d);
 		    Digraph::Node n = d.addNode();
 		    d.addArc(n, n);
-		  Digraph digraphWithoutEulerianCircuit;
+		    checkDiEulerIt(d);
 		    checkDiEulerIt(g);
 		    checkEulerIt(g);
 		    check(eulerian(d), "This graph is Eulerian");
 		    check(eulerian(g), "This graph is Eulerian");
+		  }
+		  {
-		    Digraph& g = digraphWithoutEulerianCircuit;
+		    Digraph d;
 		    Graph g(d);
 		    Digraph::Node n1 = d.addNode();
 		    Digraph::Node n2 = d.addNode();
 		    Digraph::Node n3 = d.addNode();
 		    d.addArc(n1, n2);
 		    d.addArc(n2, n1);
 		    d.addArc(n2, n3);
 		    d.addArc(n3, n2);
 		    Digraph::Node n0 = g.addNode();
 		    Digraph::Node n1 = g.addNode();
-		    Digraph::Node n2 = g.addNode();
+		    checkDiEulerIt(d);
 		    checkDiEulerIt(d, n2);
 		    checkDiEulerIt(g);
 		    checkDiEulerIt(g, n2);
 		    checkEulerIt(g);
 		    checkEulerIt(g, n2);
 		    g.addArc(n0, n1);
 		    g.addArc(n1, n0);
-		    g.addArc(n1, n2);
+		    check(eulerian(d), "This graph is Eulerian");
 		    check(eulerian(g), "This graph is Eulerian");
+		  }
+		  {
 		    Digraph d;
 		    Graph g(d);
 		    Digraph::Node n1 = d.addNode();
 		    Digraph::Node n2 = d.addNode();
 		    Digraph::Node n3 = d.addNode();
 		    Digraph::Node n4 = d.addNode();
 		    Digraph::Node n5 = d.addNode();
 		    Digraph::Node n6 = d.addNode();
 		    d.addArc(n1, n2);
 		    d.addArc(n2, n4);
 		    d.addArc(n1, n3);
 		    d.addArc(n3, n4);
 		    d.addArc(n4, n1);
 		    d.addArc(n3, n5);
 		    d.addArc(n5, n2);
 		    d.addArc(n4, n6);
 		    d.addArc(n2, n6);
 		    d.addArc(n6, n1);
 		    d.addArc(n6, n3);
-		  Graph graphWithEulerianCircuit;
+		    checkDiEulerIt(d);
 		    checkDiEulerIt(d, n1);
 		    checkDiEulerIt(d, n5);
 		    checkDiEulerIt(g);
 		    checkDiEulerIt(g, n1);
 		    checkDiEulerIt(g, n5);
 		    checkEulerIt(g);
 		    checkEulerIt(g, n1);
 		    checkEulerIt(g, n5);
 		    check(eulerian(d), "This graph is Eulerian");
 		    check(eulerian(g), "This graph is Eulerian");
+		  }
+		  {
-		    Graph& g = graphWithEulerianCircuit;
+		    Digraph d;
 		    Graph g(d);
 		    Digraph::Node n0 = d.addNode();
 		    Digraph::Node n1 = d.addNode();
 		    Digraph::Node n2 = d.addNode();
 		    Digraph::Node n3 = d.addNode();
 		    Digraph::Node n4 = d.addNode();
 		    Digraph::Node n5 = d.addNode();
 		    d.addArc(n1, n2);
 		    d.addArc(n2, n3);
 		    d.addArc(n3, n1);
 		    Graph::Node n0 = g.addNode();
 		    Graph::Node n1 = g.addNode();
-		    Graph::Node n2 = g.addNode();
+		    checkDiEulerIt(d);
 		    checkDiEulerIt(d, n2);
 		    g.addEdge(n0, n1);
 		    g.addEdge(n1, n2);
-		    g.addEdge(n2, n0);
+		    checkDiEulerIt(g);
 		    checkDiEulerIt(g, n2);
 		    checkEulerIt(g);
 		    checkEulerIt(g, n2);
 		    check(!eulerian(d), "This graph is not Eulerian");
 		    check(!eulerian(g), "This graph is not Eulerian");
+		  }
+		  {
 		    Digraph d;
 		    Graph g(d);
 		    Digraph::Node n1 = d.addNode();
 		    Digraph::Node n2 = d.addNode();
 		    Digraph::Node n3 = d.addNode();
 		    d.addArc(n1, n2);
 		    d.addArc(n2, n3);
 		  Graph graphWithoutEulerianCircuit;
+		  {
 		    Graph& g = graphWithoutEulerianCircuit;
 		    Graph::Node n0 = g.addNode();
 		    Graph::Node n1 = g.addNode();
 		    Graph::Node n2 = g.addNode();
 		    g.addEdge(n0, n1);
 		    g.addEdge(n1, n2);
 		    check(!eulerian(d), "This graph is not Eulerian");
 		    check(!eulerian(g), "This graph is not Eulerian");
+		  }
 		  checkDiEulerIt(digraphWithEulerianCircuit);
 		  checkEulerIt(graphWithEulerianCircuit);
 		  check(eulerian(digraphWithEulerianCircuit),
 		      "this graph should have an Eulerian circuit");
 		  check(!eulerian(digraphWithoutEulerianCircuit),
 		      "this graph should not have an Eulerian circuit");
 		  check(eulerian(graphWithEulerianCircuit),
 		      "this graph should have an Eulerian circuit");
 		  check(!eulerian(graphWithoutEulerianCircuit),
 		      "this graph should have an Eulerian circuit");
 		  return 0;
+		}

0 comments (0 inline)

RhodeCode

Login to your account