# source:lemon-0.x/lemon/euler.h@1817:dc3516405f8f

Last change on this file since 1817:dc3516405f8f was 1803:ee8dd6872645, checked in by Alpar Juttner, 14 years ago

Better doc.

File size: 3.9 KB
Line
1/* -*- C++ -*-
2 * lemon/topology.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
16#include<lemon/invalid.h>
17#include <list>
18
19/// \ingroup topology
20/// \file
21/// \brief Euler tour
22///
23///This file provides an Euler tour iterator and ways to check
24///if a graph is euler.
25
26
27namespace lemon {
28
29  ///Euler iterator in directed graphs.
30
31  /// \ingroup topology
32  ///This iterator converts to the \c Edge type of the graph and using
33  ///operator ++ it provides an Euler tour of the graph (if there exists).
34  ///
35  ///For example
36  ///if the given graph if Euler (i.e it has only one nontrivial component
37  ///and the in-degree is equal to the out-degree for all nodes),
38  ///the following code will print the edge IDs according to an
39  ///Euler tour of \c g.
40  ///\code
41  ///  for(EulerIt<ListGraph> e(g),e!=INVALID;++e) {
42  ///    std::cout << g.id(e) << std::eol;
43  ///  }
44  ///\endcode
45  ///If \c g is not Euler then the resulted tour will not be full or closed.
46  ///\todo Test required
47  template<class Graph>
48  class EulerIt
49  {
50    typedef typename Graph::Node Node;
51    typedef typename Graph::NodeIt NodeIt;
52    typedef typename Graph::Edge Edge;
53    typedef typename Graph::EdgeIt EdgeIt;
54    typedef typename Graph::OutEdgeIt OutEdgeIt;
55    typedef typename Graph::InEdgeIt InEdgeIt;
56
57    const Graph &g;
58    typename Graph::NodeMap<OutEdgeIt> nedge;
59    std::list<Edge> euler;
60
61  public:
62
63    ///Constructor
64
65    ///\param _g A directed graph.
66    ///\param start The starting point of the tour. If it is not given
67    ///       the tour will start from the first node.
68    EulerIt(const Graph &_g,typename Graph::Node start=INVALID)
69      : g(_g), nedge(g)
70    {
71      if(start==INVALID) start=NodeIt(g);
72      for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutEdgeIt(g,n);
73      while(nedge[start]!=INVALID) {
74        euler.push_back(nedge[start]);
75        Node next=g.target(nedge[start]);
76        ++nedge[start];
77        start=next;
78      }
79    }
80
81    ///Edge Conversion
82    operator Edge() { return euler.empty()?INVALID:euler.front(); }
83    bool operator==(Invalid) { return euler.empty(); }
84    bool operator!=(Invalid) { return !euler.empty(); }
85
86    ///Next edge of the tour
87    EulerIt &operator++() {
88      Node s=g.target(euler.front());
89      euler.pop_front();
90      //This produces a warning.Strange.
91      //std::list<Edge>::iterator next=euler.begin();
92      typename std::list<Edge>::iterator next=euler.begin();
93      while(nedge[s]!=INVALID) {
94        euler.insert(next,nedge[s]);
95        Node n=g.target(nedge[s]);
96        ++nedge[s];
97        s=n;
98      }
99      return *this;
100    }
101    ///Postfix incrementation
102
103    ///\warning This incrementation
104    ///returns an \c Edge, not an \ref EulerIt, as one may
105    ///expect.
106    Edge operator++(int)
107    {
108      Edge e=*this;
109      ++(*this);
110      return e;
111    }
112  };
113
114  ///Checks if the graph is Euler
115
116  /// \ingroup gutils
117  ///Checks if the graph is Euler. It works for both directed and
118  ///undirected graphs.
119  ///\todo Test required
120  template<class Graph>
121#ifdef DOXYGEN
122  bool
123#else
124  typename enable_if<typename Graph::UndirTag,bool>::type
125#endif
126  euler(const Graph &g)
127  {
128    for(typename Graph::NodeIt n(g);n!=INVALID;++n)
129      if(countIncEdges(g,n)%2) return false;
130    return true;
131  }
132  template<class Graph>
133  typename disable_if<typename Graph::UndirTag,bool>::type
134  euler(const Graph &g)
135  {
136    for(typename Graph::NodeIt n(g);n!=INVALID;++n)
137      if(countInEdges(g,n)!=countOutEdges(g,n)) return false;
138    return true;
139  }
140
141}
Note: See TracBrowser for help on using the repository browser.