lemon/euler.h
changeset 631 d21b38647e53
parent 591 493533ead9df
child 648 4ff8041e9c2e
equal deleted inserted replaced
5:8f69b8d48b3a 6:79fb63356af8
    24 #include<lemon/connectivity.h>
    24 #include<lemon/connectivity.h>
    25 #include <list>
    25 #include <list>
    26 
    26 
    27 /// \ingroup graph_properties
    27 /// \ingroup graph_properties
    28 /// \file
    28 /// \file
    29 /// \brief Euler tour
    29 /// \brief Euler tour iterators and a function for checking the \e Eulerian 
       
    30 /// property.
    30 ///
    31 ///
    31 ///This file provides an Euler tour iterator and ways to check
    32 ///This file provides Euler tour iterators and a function to check
    32 ///if a digraph is euler.
    33 ///if a (di)graph is \e Eulerian.
    33 
       
    34 
    34 
    35 namespace lemon {
    35 namespace lemon {
    36 
    36 
    37   ///Euler iterator for digraphs.
    37   ///Euler tour iterator for digraphs.
    38 
    38 
    39   /// \ingroup graph_properties
    39   /// \ingroup graph_prop
    40   ///This iterator converts to the \c Arc type of the digraph and using
    40   ///This iterator provides an Euler tour (Eulerian circuit) of a \e directed
    41   ///operator ++, it provides an Euler tour of a \e directed
    41   ///graph (if there exists) and it converts to the \c Arc type of the digraph.
    42   ///graph (if there exists).
    42   ///
    43   ///
    43   ///For example, if the given digraph has an Euler tour (i.e it has only one
    44   ///For example
    44   ///non-trivial component and the in-degree is equal to the out-degree 
    45   ///if the given digraph is Euler (i.e it has only one nontrivial component
    45   ///for all nodes), then the following code will put the arcs of \c g
    46   ///and the in-degree is equal to the out-degree for all nodes),
    46   ///to the vector \c et according to an Euler tour of \c g.
    47   ///the following code will put the arcs of \c g
       
    48   ///to the vector \c et according to an
       
    49   ///Euler tour of \c g.
       
    50   ///\code
    47   ///\code
    51   ///  std::vector<ListDigraph::Arc> et;
    48   ///  std::vector<ListDigraph::Arc> et;
    52   ///  for(DiEulerIt<ListDigraph> e(g),e!=INVALID;++e)
    49   ///  for(DiEulerIt<ListDigraph> e(g); e!=INVALID; ++e)
    53   ///    et.push_back(e);
    50   ///    et.push_back(e);
    54   ///\endcode
    51   ///\endcode
    55   ///If \c g is not Euler then the resulted tour will not be full or closed.
    52   ///If \c g has no Euler tour, then the resulted walk will not be closed
       
    53   ///or not contain all arcs.
    56   ///\sa EulerIt
    54   ///\sa EulerIt
    57   template<typename GR>
    55   template<typename GR>
    58   class DiEulerIt
    56   class DiEulerIt
    59   {
    57   {
    60     typedef typename GR::Node Node;
    58     typedef typename GR::Node Node;
    63     typedef typename GR::ArcIt ArcIt;
    61     typedef typename GR::ArcIt ArcIt;
    64     typedef typename GR::OutArcIt OutArcIt;
    62     typedef typename GR::OutArcIt OutArcIt;
    65     typedef typename GR::InArcIt InArcIt;
    63     typedef typename GR::InArcIt InArcIt;
    66 
    64 
    67     const GR &g;
    65     const GR &g;
    68     typename GR::template NodeMap<OutArcIt> nedge;
    66     typename GR::template NodeMap<OutArcIt> narc;
    69     std::list<Arc> euler;
    67     std::list<Arc> euler;
    70 
    68 
    71   public:
    69   public:
    72 
    70 
    73     ///Constructor
    71     ///Constructor
    74 
    72 
       
    73     ///Constructor.
    75     ///\param gr A digraph.
    74     ///\param gr A digraph.
    76     ///\param start The starting point of the tour. If it is not given
    75     ///\param start The starting point of the tour. If it is not given,
    77     ///       the tour will start from the first node.
    76     ///the tour will start from the first node that has an outgoing arc.
    78     DiEulerIt(const GR &gr, typename GR::Node start = INVALID)
    77     DiEulerIt(const GR &gr, typename GR::Node start = INVALID)
    79       : g(gr), nedge(g)
    78       : g(gr), narc(g)
    80     {
    79     {
    81       if (start==INVALID) {
    80       if (start==INVALID) {
    82         NodeIt n(g);
    81         NodeIt n(g);
    83         while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n;
    82         while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n;
    84         start=n;
    83         start=n;
    85       }
    84       }
    86       if (start!=INVALID) {
    85       if (start!=INVALID) {
    87         for (NodeIt n(g); n!=INVALID; ++n) nedge[n]=OutArcIt(g,n);
    86         for (NodeIt n(g); n!=INVALID; ++n) narc[n]=OutArcIt(g,n);
    88         while (nedge[start]!=INVALID) {
    87         while (narc[start]!=INVALID) {
    89           euler.push_back(nedge[start]);
    88           euler.push_back(narc[start]);
    90           Node next=g.target(nedge[start]);
    89           Node next=g.target(narc[start]);
    91           ++nedge[start];
    90           ++narc[start];
    92           start=next;
    91           start=next;
    93         }
    92         }
    94       }
    93       }
    95     }
    94     }
    96 
    95 
    97     ///Arc Conversion
    96     ///Arc conversion
    98     operator Arc() { return euler.empty()?INVALID:euler.front(); }
    97     operator Arc() { return euler.empty()?INVALID:euler.front(); }
       
    98     ///Compare with \c INVALID
    99     bool operator==(Invalid) { return euler.empty(); }
    99     bool operator==(Invalid) { return euler.empty(); }
       
   100     ///Compare with \c INVALID
   100     bool operator!=(Invalid) { return !euler.empty(); }
   101     bool operator!=(Invalid) { return !euler.empty(); }
   101 
   102 
   102     ///Next arc of the tour
   103     ///Next arc of the tour
       
   104 
       
   105     ///Next arc of the tour
       
   106     ///
   103     DiEulerIt &operator++() {
   107     DiEulerIt &operator++() {
   104       Node s=g.target(euler.front());
   108       Node s=g.target(euler.front());
   105       euler.pop_front();
   109       euler.pop_front();
   106       //This produces a warning.Strange.
       
   107       //std::list<Arc>::iterator next=euler.begin();
       
   108       typename std::list<Arc>::iterator next=euler.begin();
   110       typename std::list<Arc>::iterator next=euler.begin();
   109       while(nedge[s]!=INVALID) {
   111       while(narc[s]!=INVALID) {
   110         euler.insert(next,nedge[s]);
   112         euler.insert(next,narc[s]);
   111         Node n=g.target(nedge[s]);
   113         Node n=g.target(narc[s]);
   112         ++nedge[s];
   114         ++narc[s];
   113         s=n;
   115         s=n;
   114       }
   116       }
   115       return *this;
   117       return *this;
   116     }
   118     }
   117     ///Postfix incrementation
   119     ///Postfix incrementation
   118 
   120 
       
   121     /// Postfix incrementation.
       
   122     ///
   119     ///\warning This incrementation
   123     ///\warning This incrementation
   120     ///returns an \c Arc, not an \ref DiEulerIt, as one may
   124     ///returns an \c Arc, not a \ref DiEulerIt, as one may
   121     ///expect.
   125     ///expect.
   122     Arc operator++(int)
   126     Arc operator++(int)
   123     {
   127     {
   124       Arc e=*this;
   128       Arc e=*this;
   125       ++(*this);
   129       ++(*this);
   126       return e;
   130       return e;
   127     }
   131     }
   128   };
   132   };
   129 
   133 
   130   ///Euler iterator for graphs.
   134   ///Euler tour iterator for graphs.
   131 
   135 
   132   /// \ingroup graph_properties
   136   /// \ingroup graph_properties
   133   ///This iterator converts to the \c Arc (or \c Edge)
   137   ///This iterator provides an Euler tour (Eulerian circuit) of an
   134   ///type of the digraph and using
   138   ///\e undirected graph (if there exists) and it converts to the \c Arc
   135   ///operator ++, it provides an Euler tour of an undirected
   139   ///and \c Edge types of the graph.
   136   ///digraph (if there exists).
   140   ///
   137   ///
   141   ///For example, if the given graph has an Euler tour (i.e it has only one 
   138   ///For example
   142   ///non-trivial component and the degree of each node is even),
   139   ///if the given digraph if Euler (i.e it has only one nontrivial component
       
   140   ///and the degree of each node is even),
       
   141   ///the following code will print the arc IDs according to an
   143   ///the following code will print the arc IDs according to an
   142   ///Euler tour of \c g.
   144   ///Euler tour of \c g.
   143   ///\code
   145   ///\code
   144   ///  for(EulerIt<ListGraph> e(g),e!=INVALID;++e) {
   146   ///  for(EulerIt<ListGraph> e(g); e!=INVALID; ++e) {
   145   ///    std::cout << g.id(Edge(e)) << std::eol;
   147   ///    std::cout << g.id(Edge(e)) << std::eol;
   146   ///  }
   148   ///  }
   147   ///\endcode
   149   ///\endcode
   148   ///Although the iterator provides an Euler tour of an graph,
   150   ///Although this iterator is for undirected graphs, it still returns 
   149   ///it still returns Arcs in order to indicate the direction of the tour.
   151   ///arcs in order to indicate the direction of the tour.
   150   ///(But Arc will convert to Edges, of course).
   152   ///(But arcs convert to edges, of course.)
   151   ///
   153   ///
   152   ///If \c g is not Euler then the resulted tour will not be full or closed.
   154   ///If \c g has no Euler tour, then the resulted walk will not be closed
   153   ///\sa EulerIt
   155   ///or not contain all edges.
   154   template<typename GR>
   156   template<typename GR>
   155   class EulerIt
   157   class EulerIt
   156   {
   158   {
   157     typedef typename GR::Node Node;
   159     typedef typename GR::Node Node;
   158     typedef typename GR::NodeIt NodeIt;
   160     typedef typename GR::NodeIt NodeIt;
   161     typedef typename GR::ArcIt ArcIt;
   163     typedef typename GR::ArcIt ArcIt;
   162     typedef typename GR::OutArcIt OutArcIt;
   164     typedef typename GR::OutArcIt OutArcIt;
   163     typedef typename GR::InArcIt InArcIt;
   165     typedef typename GR::InArcIt InArcIt;
   164 
   166 
   165     const GR &g;
   167     const GR &g;
   166     typename GR::template NodeMap<OutArcIt> nedge;
   168     typename GR::template NodeMap<OutArcIt> narc;
   167     typename GR::template EdgeMap<bool> visited;
   169     typename GR::template EdgeMap<bool> visited;
   168     std::list<Arc> euler;
   170     std::list<Arc> euler;
   169 
   171 
   170   public:
   172   public:
   171 
   173 
   172     ///Constructor
   174     ///Constructor
   173 
   175 
   174     ///\param gr An graph.
   176     ///Constructor.
   175     ///\param start The starting point of the tour. If it is not given
   177     ///\param gr A graph.
   176     ///       the tour will start from the first node.
   178     ///\param start The starting point of the tour. If it is not given,
       
   179     ///the tour will start from the first node that has an incident edge.
   177     EulerIt(const GR &gr, typename GR::Node start = INVALID)
   180     EulerIt(const GR &gr, typename GR::Node start = INVALID)
   178       : g(gr), nedge(g), visited(g, false)
   181       : g(gr), narc(g), visited(g, false)
   179     {
   182     {
   180       if (start==INVALID) {
   183       if (start==INVALID) {
   181         NodeIt n(g);
   184         NodeIt n(g);
   182         while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n;
   185         while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n;
   183         start=n;
   186         start=n;
   184       }
   187       }
   185       if (start!=INVALID) {
   188       if (start!=INVALID) {
   186         for (NodeIt n(g); n!=INVALID; ++n) nedge[n]=OutArcIt(g,n);
   189         for (NodeIt n(g); n!=INVALID; ++n) narc[n]=OutArcIt(g,n);
   187         while(nedge[start]!=INVALID) {
   190         while(narc[start]!=INVALID) {
   188           euler.push_back(nedge[start]);
   191           euler.push_back(narc[start]);
   189           visited[nedge[start]]=true;
   192           visited[narc[start]]=true;
   190           Node next=g.target(nedge[start]);
   193           Node next=g.target(narc[start]);
   191           ++nedge[start];
   194           ++narc[start];
   192           start=next;
   195           start=next;
   193           while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start];
   196           while(narc[start]!=INVALID && visited[narc[start]]) ++narc[start];
   194         }
   197         }
   195       }
   198       }
   196     }
   199     }
   197 
   200 
   198     ///Arc Conversion
   201     ///Arc conversion
   199     operator Arc() const { return euler.empty()?INVALID:euler.front(); }
   202     operator Arc() const { return euler.empty()?INVALID:euler.front(); }
   200     ///Arc Conversion
   203     ///Edge conversion
   201     operator Edge() const { return euler.empty()?INVALID:euler.front(); }
   204     operator Edge() const { return euler.empty()?INVALID:euler.front(); }
   202     ///\e
   205     ///Compare with \c INVALID
   203     bool operator==(Invalid) const { return euler.empty(); }
   206     bool operator==(Invalid) const { return euler.empty(); }
   204     ///\e
   207     ///Compare with \c INVALID
   205     bool operator!=(Invalid) const { return !euler.empty(); }
   208     bool operator!=(Invalid) const { return !euler.empty(); }
   206 
   209 
   207     ///Next arc of the tour
   210     ///Next arc of the tour
       
   211 
       
   212     ///Next arc of the tour
       
   213     ///
   208     EulerIt &operator++() {
   214     EulerIt &operator++() {
   209       Node s=g.target(euler.front());
   215       Node s=g.target(euler.front());
   210       euler.pop_front();
   216       euler.pop_front();
   211       typename std::list<Arc>::iterator next=euler.begin();
   217       typename std::list<Arc>::iterator next=euler.begin();
   212 
   218       while(narc[s]!=INVALID) {
   213       while(nedge[s]!=INVALID) {
   219         while(narc[s]!=INVALID && visited[narc[s]]) ++narc[s];
   214         while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s];
   220         if(narc[s]==INVALID) break;
   215         if(nedge[s]==INVALID) break;
       
   216         else {
   221         else {
   217           euler.insert(next,nedge[s]);
   222           euler.insert(next,narc[s]);
   218           visited[nedge[s]]=true;
   223           visited[narc[s]]=true;
   219           Node n=g.target(nedge[s]);
   224           Node n=g.target(narc[s]);
   220           ++nedge[s];
   225           ++narc[s];
   221           s=n;
   226           s=n;
   222         }
   227         }
   223       }
   228       }
   224       return *this;
   229       return *this;
   225     }
   230     }
   226 
   231 
   227     ///Postfix incrementation
   232     ///Postfix incrementation
   228 
   233 
   229     ///\warning This incrementation
   234     /// Postfix incrementation.
   230     ///returns an \c Arc, not an \ref EulerIt, as one may
   235     ///
   231     ///expect.
   236     ///\warning This incrementation returns an \c Arc (which converts to 
       
   237     ///an \c Edge), not an \ref EulerIt, as one may expect.
   232     Arc operator++(int)
   238     Arc operator++(int)
   233     {
   239     {
   234       Arc e=*this;
   240       Arc e=*this;
   235       ++(*this);
   241       ++(*this);
   236       return e;
   242       return e;
   237     }
   243     }
   238   };
   244   };
   239 
   245 
   240 
   246 
   241   ///Checks if the graph is Eulerian
   247   ///Check if the given graph is \e Eulerian
   242 
   248 
   243   /// \ingroup graph_properties
   249   /// \ingroup graph_properties
   244   ///Checks if the graph is Eulerian. It works for both directed and undirected
   250   ///This function checks if the given graph is \e Eulerian.
   245   ///graphs.
   251   ///It works for both directed and undirected graphs.
   246   ///\note By definition, a digraph is called \e Eulerian if
   252   ///
   247   ///and only if it is connected and the number of its incoming and outgoing
   253   ///By definition, a digraph is called \e Eulerian if
       
   254   ///and only if it is connected and the number of incoming and outgoing
   248   ///arcs are the same for each node.
   255   ///arcs are the same for each node.
   249   ///Similarly, an undirected graph is called \e Eulerian if
   256   ///Similarly, an undirected graph is called \e Eulerian if
   250   ///and only if it is connected and the number of incident arcs is even
   257   ///and only if it is connected and the number of incident edges is even
   251   ///for each node. <em>Therefore, there are digraphs which are not Eulerian,
   258   ///for each node.
   252   ///but still have an Euler tour</em>.
   259   ///
       
   260   ///\note There are (di)graphs that are not Eulerian, but still have an
       
   261   /// Euler tour, since they may contain isolated nodes.
       
   262   ///
       
   263   ///\sa DiEulerIt, EulerIt
   253   template<typename GR>
   264   template<typename GR>
   254 #ifdef DOXYGEN
   265 #ifdef DOXYGEN
   255   bool
   266   bool
   256 #else
   267 #else
   257   typename enable_if<UndirectedTagIndicator<GR>,bool>::type
   268   typename enable_if<UndirectedTagIndicator<GR>,bool>::type
   266 #endif
   277 #endif
   267   eulerian(const GR &g)
   278   eulerian(const GR &g)
   268   {
   279   {
   269     for(typename GR::NodeIt n(g);n!=INVALID;++n)
   280     for(typename GR::NodeIt n(g);n!=INVALID;++n)
   270       if(countInArcs(g,n)!=countOutArcs(g,n)) return false;
   281       if(countInArcs(g,n)!=countOutArcs(g,n)) return false;
   271     return connected(Undirector<const GR>(g));
   282     return connected(undirector(g));
   272   }
   283   }
   273 
   284 
   274 }
   285 }
   275 
   286 
   276 #endif
   287 #endif