lemon/euler.h
changeset 912 09282720100b
parent 648 4ff8041e9c2e
child 919 e0cef67fe565
equal deleted inserted replaced
7:619fb75f39d9 8:721947dc62be
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     4  *
     5  * Copyright (C) 2003-2009
     5  * Copyright (C) 2003-2010
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     8  *
     9  * Permission to use, modify and distribute this software is granted
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    10  * provided that this copyright notice appears in all copies. For
    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 iterators and a function for checking the \e Eulerian 
    29 /// \brief Euler tour iterators and a function for checking the \e Eulerian
    30 /// property.
    30 /// property.
    31 ///
    31 ///
    32 ///This file provides Euler tour iterators and a function to check
    32 ///This file provides Euler tour iterators and a function to check
    33 ///if a (di)graph is \e Eulerian.
    33 ///if a (di)graph is \e Eulerian.
    34 
    34 
    39   /// \ingroup graph_prop
    39   /// \ingroup graph_prop
    40   ///This iterator provides an Euler tour (Eulerian circuit) of a \e directed
    40   ///This iterator provides an Euler tour (Eulerian circuit) of a \e directed
    41   ///graph (if there exists) and it converts to the \c Arc type of the digraph.
    41   ///graph (if there exists) and it converts to the \c Arc type of the digraph.
    42   ///
    42   ///
    43   ///For example, if the given digraph has an Euler tour (i.e it has only one
    43   ///For example, if the given digraph has an Euler tour (i.e it has only one
    44   ///non-trivial component and the in-degree is equal to the out-degree 
    44   ///non-trivial component and the in-degree is equal to the out-degree
    45   ///for all nodes), then the following code will put the arcs of \c g
    45   ///for all nodes), then the following code will put the arcs of \c g
    46   ///to the vector \c et according to an Euler tour of \c g.
    46   ///to the vector \c et according to an Euler tour of \c g.
    47   ///\code
    47   ///\code
    48   ///  std::vector<ListDigraph::Arc> et;
    48   ///  std::vector<ListDigraph::Arc> et;
    49   ///  for(DiEulerIt<ListDigraph> e(g); e!=INVALID; ++e)
    49   ///  for(DiEulerIt<ListDigraph> e(g); e!=INVALID; ++e)
   136   /// \ingroup graph_properties
   136   /// \ingroup graph_properties
   137   ///This iterator provides an Euler tour (Eulerian circuit) of an
   137   ///This iterator provides an Euler tour (Eulerian circuit) of an
   138   ///\e undirected graph (if there exists) and it converts to the \c Arc
   138   ///\e undirected graph (if there exists) and it converts to the \c Arc
   139   ///and \c Edge types of the graph.
   139   ///and \c Edge types of the graph.
   140   ///
   140   ///
   141   ///For example, if the given graph has an Euler tour (i.e it has only one 
   141   ///For example, if the given graph has an Euler tour (i.e it has only one
   142   ///non-trivial component and the degree of each node is even),
   142   ///non-trivial component and the degree of each node is even),
   143   ///the following code will print the arc IDs according to an
   143   ///the following code will print the arc IDs according to an
   144   ///Euler tour of \c g.
   144   ///Euler tour of \c g.
   145   ///\code
   145   ///\code
   146   ///  for(EulerIt<ListGraph> e(g); e!=INVALID; ++e) {
   146   ///  for(EulerIt<ListGraph> e(g); e!=INVALID; ++e) {
   147   ///    std::cout << g.id(Edge(e)) << std::eol;
   147   ///    std::cout << g.id(Edge(e)) << std::eol;
   148   ///  }
   148   ///  }
   149   ///\endcode
   149   ///\endcode
   150   ///Although this iterator is for undirected graphs, it still returns 
   150   ///Although this iterator is for undirected graphs, it still returns
   151   ///arcs in order to indicate the direction of the tour.
   151   ///arcs in order to indicate the direction of the tour.
   152   ///(But arcs convert to edges, of course.)
   152   ///(But arcs convert to edges, of course.)
   153   ///
   153   ///
   154   ///If \c g has no Euler tour, then the resulted walk will not be closed
   154   ///If \c g has no Euler tour, then the resulted walk will not be closed
   155   ///or not contain all edges.
   155   ///or not contain all edges.
   231 
   231 
   232     ///Postfix incrementation
   232     ///Postfix incrementation
   233 
   233 
   234     /// Postfix incrementation.
   234     /// Postfix incrementation.
   235     ///
   235     ///
   236     ///\warning This incrementation returns an \c Arc (which converts to 
   236     ///\warning This incrementation returns an \c Arc (which converts to
   237     ///an \c Edge), not an \ref EulerIt, as one may expect.
   237     ///an \c Edge), not an \ref EulerIt, as one may expect.
   238     Arc operator++(int)
   238     Arc operator++(int)
   239     {
   239     {
   240       Arc e=*this;
   240       Arc e=*this;
   241       ++(*this);
   241       ++(*this);