COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/euler.h @ 1769:a67ec111236c

Last change on this file since 1769:a67ec111236c was 1769:a67ec111236c, checked in by Balazs Dezso, 18 years ago

Removed todo
Moved to topology module

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  ///the ++ 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 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    ///       tho 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 gives back an Edge, not an EulerIt!
104    Edge operator++(int)
105    {
106      Edge e=*this;
107      ++(*this);
108      return e;
109    }
110  };
111
112  ///Checks if the graph is Euler
113
114  /// \ingroup gutils
115  ///Checks if the graph is Euler. It works for both directed and
116  ///undirected graphs.
117  ///\todo Test required
118  template<class Graph>
119#ifdef DOXYGEN
120  bool
121#else
122  typename enable_if<typename Graph::UndirTag,bool>::type
123#endif
124  euler(const Graph &g)
125  {
126    for(typename Graph::NodeIt n(g);n!=INVALID;++n)
127      if(countIncEdges(g,n)%2) return false;
128    return true;
129  }
130  template<class Graph>
131  typename disable_if<typename Graph::UndirTag,bool>::type
132  euler(const Graph &g)
133  {
134    for(typename Graph::NodeIt n(g);n!=INVALID;++n)
135      if(countInEdges(g,n)!=countOutEdges(g,n)) return false;
136    return true;
137  }
138 
139}
Note: See TracBrowser for help on using the repository browser.