/* -*- C++ -*- * lemon/euler.h - Part of LEMON, a generic C++ optimization library * * Copyright (C) 2005 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. * */ #include #include #include /// \ingroup topology /// \file /// \brief Euler tour /// ///This file provides an Euler tour iterator and ways to check ///if a graph is euler. namespace lemon { ///Euler iterator for directed 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 in-degree is equal to the out-degree for all nodes), ///the following code will print the edge IDs according to an ///Euler tour of \c g. ///\code /// for(EulerIt e(g),e!=INVALID;++e) { /// std::cout << g.id(e) << std::eol; /// } ///\endcode ///If \c g is not Euler then the resulted tour will not be full or closed. ///\todo Test required template class EulerIt { 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 nedge; std::list euler; public: ///Constructor ///\param _g A directed graph. ///\param start The starting point of the tour. If it is not given /// the tour will start from the first node. EulerIt(const Graph &_g,typename Graph::Node start=INVALID) : g(_g), nedge(g) { 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; } } ///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 EulerIt &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 Edge, not an \ref EulerIt, as one may ///expect. Edge operator++(int) { Edge e=*this; ++(*this); return e; } }; ///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 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 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 nedge; typename Graph::UndirEdgeMap visited; std::list 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::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 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. Therefore, there are graphs which are not Euler, but ///still have an Euler tour. ///\todo Test required template #ifdef DOXYGEN bool #else typename enable_if::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 typename disable_if::type #endif euler(const Graph &g) { for(typename Graph::NodeIt n(g);n!=INVALID;++n) if(countInEdges(g,n)!=countOutEdges(g,n)) return false; return connected(g); } }