1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/euler.h Mon Oct 24 15:58:38 2005 +0000
1.3 @@ -0,0 +1,141 @@
1.4 +/* -*- C++ -*-
1.5 + * lemon/topology.h - Part of LEMON, a generic C++ optimization library
1.6 + *
1.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.9 + *
1.10 + * Permission to use, modify and distribute this software is granted
1.11 + * provided that this copyright notice appears in all copies. For
1.12 + * precise terms see the accompanying LICENSE file.
1.13 + *
1.14 + * This software is provided "AS IS" with no warranty of any kind,
1.15 + * express or implied, and with no claim as to its suitability for any
1.16 + * purpose.
1.17 + *
1.18 + */
1.19 +#include<lemon/invalid.h>
1.20 +#include <list>
1.21 +
1.22 +/// \ingroup gutils
1.23 +/// \file
1.24 +/// \brief Euler tour
1.25 +///
1.26 +///This file provides an Euler tour iterator and ways to check
1.27 +///if a graph is euler.
1.28 +
1.29 +
1.30 +namespace lemon {
1.31 +
1.32 + ///Euler iterator in directed graphs.
1.33 +
1.34 + /// \ingroup gutils
1.35 + ///This iterator converts to the \c Edge type of the graph and using
1.36 + ///the ++ operator it provides an Euler tour of the graph (if there exists).
1.37 + ///
1.38 + ///For example
1.39 + ///if the given graph if Euler (i.e it has only one nontrivial component
1.40 + ///and the in-degree is equal to the out-degree for all nodes),
1.41 + ///the the following code will print the edge IDs according to an
1.42 + ///Euler tour of \c g.
1.43 + ///\code
1.44 + /// for(EulerIt<ListGraph> e(g),e!=INVALID;++e) {
1.45 + /// std::cout << g.id(e) << std::eol;
1.46 + /// }
1.47 + ///\endcode
1.48 + ///If \c g is not Euler then the resulted tour will not be full or closed.
1.49 + ///\todo Test required
1.50 + template<class Graph>
1.51 + class EulerIt
1.52 + {
1.53 + typedef typename Graph::Node Node;
1.54 + typedef typename Graph::NodeIt NodeIt;
1.55 + typedef typename Graph::Edge Edge;
1.56 + typedef typename Graph::EdgeIt EdgeIt;
1.57 + typedef typename Graph::OutEdgeIt OutEdgeIt;
1.58 + typedef typename Graph::InEdgeIt InEdgeIt;
1.59 +
1.60 + const Graph &g;
1.61 + typename Graph::NodeMap<OutEdgeIt> nedge;
1.62 + std::list<Edge> euler;
1.63 +
1.64 + public:
1.65 +
1.66 + ///Constructor
1.67 +
1.68 + ///\param _g A directed graph.
1.69 + ///\param start The starting point of the tour. If it is not given
1.70 + /// tho tour will start from the first node.
1.71 + EulerIt(const Graph &_g,typename Graph::Node start=INVALID)
1.72 + : g(_g), nedge(g)
1.73 + {
1.74 + if(start==INVALID) start=NodeIt(g);
1.75 + for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutEdgeIt(g,n);
1.76 + while(nedge[start]!=INVALID) {
1.77 + euler.push_back(nedge[start]);
1.78 + Node next=g.target(nedge[start]);
1.79 + ++nedge[start];
1.80 + start=next;
1.81 + }
1.82 + }
1.83 +
1.84 + ///Edge Conversion
1.85 + operator Edge() { return euler.empty()?INVALID:euler.front(); }
1.86 + bool operator==(Invalid) { return euler.empty(); }
1.87 + bool operator!=(Invalid) { return !euler.empty(); }
1.88 +
1.89 + ///Next edge of the tour
1.90 + EulerIt &operator++() {
1.91 + Node s=g.target(euler.front());
1.92 + euler.pop_front();
1.93 + //This produces a warning.Strange.
1.94 + //std::list<Edge>::iterator next=euler.begin();
1.95 + typename std::list<Edge>::iterator next=euler.begin();
1.96 + while(nedge[s]!=INVALID) {
1.97 + euler.insert(next,nedge[s]);
1.98 + Node n=g.target(nedge[s]);
1.99 + ++nedge[s];
1.100 + s=n;
1.101 + }
1.102 + return *this;
1.103 + }
1.104 + ///Postfix incrementation
1.105 +
1.106 + ///\warning This gives back an Edge, not an EulerIt!
1.107 + ///\todo Is this what we want?
1.108 + Edge operator++(int)
1.109 + {
1.110 + Edge e=*this;
1.111 + ++(*this);
1.112 + return e;
1.113 + }
1.114 + };
1.115 +
1.116 + ///Checks if the graph is Euler
1.117 +
1.118 + /// \ingroup gutils
1.119 + ///Checks if the graph is Euler. It works for both directed and
1.120 + ///undirected graphs.
1.121 + ///\todo What to do with the isolated points?
1.122 + ///\todo Test required
1.123 + template<class Graph>
1.124 +#ifdef DOXYGEN
1.125 + bool
1.126 +#else
1.127 + typename enable_if<typename Graph::UndirTag,bool>::type
1.128 +#endif
1.129 + euler(const Graph &g)
1.130 + {
1.131 + for(typename Graph::NodeIt n(g);n!=INVALID;++n)
1.132 + if(countIncEdges(g,n)%2) return false;
1.133 + return true;
1.134 + }
1.135 + template<class Graph>
1.136 + typename disable_if<typename Graph::UndirTag,bool>::type
1.137 + isEuler(const Graph &g)
1.138 + {
1.139 + for(typename Graph::NodeIt n(g);n!=INVALID;++n)
1.140 + if(countInEdges(g,n)!=countOutEdges(g,n)) return false;
1.141 + return true;
1.142 + }
1.143 +
1.144 +}