# HG changeset patch # User Alpar Juttner # Date 2009-02-23 12:30:15 # Node ID 42d4b889903a37e9df65f779bd47de262cdd9ef0 # Parent c786cd201266424f9fd055dd74af570a563a3a9a Port Euler walk tools from SVN -r3512 (#65) diff --git a/lemon/Makefile.am b/lemon/Makefile.am --- a/lemon/Makefile.am +++ b/lemon/Makefile.am @@ -64,6 +64,7 @@ lemon/edge_set.h \ lemon/elevator.h \ lemon/error.h \ + lemon/euler.h \ lemon/full_graph.h \ lemon/glpk.h \ lemon/graph_to_eps.h \ diff --git a/lemon/euler.h b/lemon/euler.h new file mode 100644 --- /dev/null +++ b/lemon/euler.h @@ -0,0 +1,267 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2009 + * 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. + * + */ + +#ifndef LEMON_EULER_H +#define LEMON_EULER_H + +#include +#include +#include +#include + +/// \ingroup graph_prop +/// \file +/// \brief Euler tour +/// +///This file provides an Euler tour iterator and ways to check +///if a digraph is euler. + + +namespace lemon { + + ///Euler iterator for digraphs. + + /// \ingroup graph_prop + ///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). + /// + ///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. + ///\code + /// std::vector et; + /// for(DiEulerIt 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. + ///\sa EulerIt + ///\todo Test required + template + class DiEulerIt + { + typedef typename Digraph::Node Node; + typedef typename Digraph::NodeIt NodeIt; + typedef typename Digraph::Arc Arc; + typedef typename Digraph::ArcIt ArcIt; + typedef typename Digraph::OutArcIt OutArcIt; + typedef typename Digraph::InArcIt InArcIt; + + const Digraph &g; + typename Digraph::template NodeMap nedge; + std::list euler; + + public: + + ///Constructor + + ///\param _g A digraph. + ///\param start The starting point of the tour. If it is not given + /// the tour will start from the first node. + DiEulerIt(const Digraph &_g,typename Digraph::Node start=INVALID) + : g(_g), nedge(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; + } + } + + ///Arc Conversion + operator Arc() { return euler.empty()?INVALID:euler.front(); } + bool operator==(Invalid) { return euler.empty(); } + bool operator!=(Invalid) { return !euler.empty(); } + + ///Next arc of the tour + DiEulerIt &operator++() { + Node s=g.target(euler.front()); + euler.pop_front(); + //This produces a warning.Strange. + //std::list::iterator next=euler.begin(); + typename std::list::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 Arc, not an \ref DiEulerIt, as one may + ///expect. + Arc operator++(int) + { + Arc e=*this; + ++(*this); + return e; + } + }; + + ///Euler iterator for graphs. + + /// \ingroup graph_prop + ///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). + /// + ///For example + ///if the given digraph if Euler (i.e it has only one nontrivial 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 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). + /// + ///If \c g is not Euler then the resulted tour will not be full or closed. + ///\sa EulerIt + ///\todo Test required + template + class EulerIt + { + typedef typename Digraph::Node Node; + typedef typename Digraph::NodeIt NodeIt; + typedef typename Digraph::Arc Arc; + typedef typename Digraph::Edge Edge; + typedef typename Digraph::ArcIt ArcIt; + typedef typename Digraph::OutArcIt OutArcIt; + typedef typename Digraph::InArcIt InArcIt; + + const Digraph &g; + typename Digraph::template NodeMap nedge; + typename Digraph::template EdgeMap visited; + std::list euler; + + public: + + ///Constructor + + ///\param _g An graph. + ///\param start The starting point of the tour. If it is not given + /// the tour will start from the first node. + EulerIt(const Digraph &_g,typename Digraph::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]=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]; + } + } + + ///Arc Conversion + operator Arc() const { return euler.empty()?INVALID:euler.front(); } + ///Arc Conversion + operator Edge() const { return euler.empty()?INVALID:euler.front(); } + ///\e + bool operator==(Invalid) const { return euler.empty(); } + ///\e + bool operator!=(Invalid) const { return !euler.empty(); } + + ///Next arc of the tour + EulerIt &operator++() { + Node s=g.target(euler.front()); + euler.pop_front(); + typename std::list::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]); + visited[nedge[s]]=true; + Node n=g.target(nedge[s]); + ++nedge[s]; + s=n; + } + } + return *this; + } + + ///Postfix incrementation + + ///\warning This incrementation + ///returns an \c Arc, not an \ref EulerIt, as one may + ///expect. + Arc operator++(int) + { + Arc e=*this; + ++(*this); + return e; + } + }; + + + ///Checks if the graph is Euler + + /// \ingroup graph_prop + ///Checks if the graph is Euler. It works for both directed and undirected + ///graphs. + ///\note By definition, a digraph is called \e Euler if + ///and only if it is connected and the number of its incoming and outgoing + ///arcs 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 arcs is even + ///for each node. Therefore, there are digraphs which are not Euler, but + ///still have an Euler tour. + ///\todo Test required + template +#ifdef DOXYGEN + bool +#else + typename enable_if,bool>::type + euler(const Digraph &g) + { + for(typename Digraph::NodeIt n(g);n!=INVALID;++n) + if(countIncEdges(g,n)%2) return false; + return connected(g); + } + template + typename disable_if,bool>::type +#endif + euler(const Digraph &g) + { + for(typename Digraph::NodeIt n(g);n!=INVALID;++n) + if(countInArcs(g,n)!=countOutArcs(g,n)) return false; + return connected(Undirector(g)); + } + +} + +#endif