lemon/euler.h
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 24 Mar 2009 00:18:25 +0100
changeset 604 8c3112a66878
parent 521 3af83b6be1df
child 559 c5fd2d996909
permissions -rw-r--r--
Use XTI implementation instead of ATI in NetworkSimplex (#234)

XTI (eXtended Threaded Index) is an imporved version of the widely
known ATI (Augmented Threaded Index) method for storing and updating
the spanning tree structure in Network Simplex algorithms.

In the ATI data structure three indices are stored for each node:
predecessor, thread and depth. In the XTI data structure depth is
replaced by the number of successors and the last successor
(according to the thread index).
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2009
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #ifndef LEMON_EULER_H
    20 #define LEMON_EULER_H
    21 
    22 #include<lemon/core.h>
    23 #include<lemon/adaptors.h>
    24 #include<lemon/connectivity.h>
    25 #include <list>
    26 
    27 /// \ingroup graph_prop
    28 /// \file
    29 /// \brief Euler tour
    30 ///
    31 ///This file provides an Euler tour iterator and ways to check
    32 ///if a digraph is euler.
    33 
    34 
    35 namespace lemon {
    36 
    37   ///Euler iterator for digraphs.
    38 
    39   /// \ingroup graph_prop
    40   ///This iterator converts to the \c Arc type of the digraph and using
    41   ///operator ++, it provides an Euler tour of a \e directed
    42   ///graph (if there exists).
    43   ///
    44   ///For example
    45   ///if the given digraph is Euler (i.e it has only one nontrivial component
    46   ///and the in-degree is equal to the out-degree for all nodes),
    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
    51   ///  std::vector<ListDigraph::Arc> et;
    52   ///  for(DiEulerIt<ListDigraph> e(g),e!=INVALID;++e)
    53   ///    et.push_back(e);
    54   ///\endcode
    55   ///If \c g is not Euler then the resulted tour will not be full or closed.
    56   ///\sa EulerIt
    57   template<class Digraph>
    58   class DiEulerIt
    59   {
    60     typedef typename Digraph::Node Node;
    61     typedef typename Digraph::NodeIt NodeIt;
    62     typedef typename Digraph::Arc Arc;
    63     typedef typename Digraph::ArcIt ArcIt;
    64     typedef typename Digraph::OutArcIt OutArcIt;
    65     typedef typename Digraph::InArcIt InArcIt;
    66 
    67     const Digraph &g;
    68     typename Digraph::template NodeMap<OutArcIt> nedge;
    69     std::list<Arc> euler;
    70 
    71   public:
    72 
    73     ///Constructor
    74 
    75     ///\param _g A digraph.
    76     ///\param start The starting point of the tour. If it is not given
    77     ///       the tour will start from the first node.
    78     DiEulerIt(const Digraph &_g,typename Digraph::Node start=INVALID)
    79       : g(_g), nedge(g)
    80     {
    81       if(start==INVALID) start=NodeIt(g);
    82       for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n);
    83       while(nedge[start]!=INVALID) {
    84         euler.push_back(nedge[start]);
    85         Node next=g.target(nedge[start]);
    86         ++nedge[start];
    87         start=next;
    88       }
    89     }
    90 
    91     ///Arc Conversion
    92     operator Arc() { return euler.empty()?INVALID:euler.front(); }
    93     bool operator==(Invalid) { return euler.empty(); }
    94     bool operator!=(Invalid) { return !euler.empty(); }
    95 
    96     ///Next arc of the tour
    97     DiEulerIt &operator++() {
    98       Node s=g.target(euler.front());
    99       euler.pop_front();
   100       //This produces a warning.Strange.
   101       //std::list<Arc>::iterator next=euler.begin();
   102       typename std::list<Arc>::iterator next=euler.begin();
   103       while(nedge[s]!=INVALID) {
   104         euler.insert(next,nedge[s]);
   105         Node n=g.target(nedge[s]);
   106         ++nedge[s];
   107         s=n;
   108       }
   109       return *this;
   110     }
   111     ///Postfix incrementation
   112 
   113     ///\warning This incrementation
   114     ///returns an \c Arc, not an \ref DiEulerIt, as one may
   115     ///expect.
   116     Arc operator++(int)
   117     {
   118       Arc e=*this;
   119       ++(*this);
   120       return e;
   121     }
   122   };
   123 
   124   ///Euler iterator for graphs.
   125 
   126   /// \ingroup graph_prop
   127   ///This iterator converts to the \c Arc (or \c Edge)
   128   ///type of the digraph and using
   129   ///operator ++, it provides an Euler tour of an undirected
   130   ///digraph (if there exists).
   131   ///
   132   ///For example
   133   ///if the given digraph if Euler (i.e it has only one nontrivial component
   134   ///and the degree of each node is even),
   135   ///the following code will print the arc IDs according to an
   136   ///Euler tour of \c g.
   137   ///\code
   138   ///  for(EulerIt<ListGraph> e(g),e!=INVALID;++e) {
   139   ///    std::cout << g.id(Edge(e)) << std::eol;
   140   ///  }
   141   ///\endcode
   142   ///Although the iterator provides an Euler tour of an graph,
   143   ///it still returns Arcs in order to indicate the direction of the tour.
   144   ///(But Arc will convert to Edges, of course).
   145   ///
   146   ///If \c g is not Euler then the resulted tour will not be full or closed.
   147   ///\sa EulerIt
   148   template<class Digraph>
   149   class EulerIt
   150   {
   151     typedef typename Digraph::Node Node;
   152     typedef typename Digraph::NodeIt NodeIt;
   153     typedef typename Digraph::Arc Arc;
   154     typedef typename Digraph::Edge Edge;
   155     typedef typename Digraph::ArcIt ArcIt;
   156     typedef typename Digraph::OutArcIt OutArcIt;
   157     typedef typename Digraph::InArcIt InArcIt;
   158 
   159     const Digraph &g;
   160     typename Digraph::template NodeMap<OutArcIt> nedge;
   161     typename Digraph::template EdgeMap<bool> visited;
   162     std::list<Arc> euler;
   163 
   164   public:
   165 
   166     ///Constructor
   167 
   168     ///\param _g An graph.
   169     ///\param start The starting point of the tour. If it is not given
   170     ///       the tour will start from the first node.
   171     EulerIt(const Digraph &_g,typename Digraph::Node start=INVALID)
   172       : g(_g), nedge(g), visited(g,false)
   173     {
   174       if(start==INVALID) start=NodeIt(g);
   175       for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n);
   176       while(nedge[start]!=INVALID) {
   177         euler.push_back(nedge[start]);
   178         visited[nedge[start]]=true;
   179         Node next=g.target(nedge[start]);
   180         ++nedge[start];
   181         start=next;
   182         while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start];
   183       }
   184     }
   185 
   186     ///Arc Conversion
   187     operator Arc() const { return euler.empty()?INVALID:euler.front(); }
   188     ///Arc Conversion
   189     operator Edge() const { return euler.empty()?INVALID:euler.front(); }
   190     ///\e
   191     bool operator==(Invalid) const { return euler.empty(); }
   192     ///\e
   193     bool operator!=(Invalid) const { return !euler.empty(); }
   194 
   195     ///Next arc of the tour
   196     EulerIt &operator++() {
   197       Node s=g.target(euler.front());
   198       euler.pop_front();
   199       typename std::list<Arc>::iterator next=euler.begin();
   200 
   201       while(nedge[s]!=INVALID) {
   202         while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s];
   203         if(nedge[s]==INVALID) break;
   204         else {
   205           euler.insert(next,nedge[s]);
   206           visited[nedge[s]]=true;
   207           Node n=g.target(nedge[s]);
   208           ++nedge[s];
   209           s=n;
   210         }
   211       }
   212       return *this;
   213     }
   214 
   215     ///Postfix incrementation
   216 
   217     ///\warning This incrementation
   218     ///returns an \c Arc, not an \ref EulerIt, as one may
   219     ///expect.
   220     Arc operator++(int)
   221     {
   222       Arc e=*this;
   223       ++(*this);
   224       return e;
   225     }
   226   };
   227 
   228 
   229   ///Checks if the graph is Eulerian
   230 
   231   /// \ingroup graph_prop
   232   ///Checks if the graph is Eulerian. It works for both directed and undirected
   233   ///graphs.
   234   ///\note By definition, a digraph is called \e Eulerian if
   235   ///and only if it is connected and the number of its incoming and outgoing
   236   ///arcs are the same for each node.
   237   ///Similarly, an undirected graph is called \e Eulerian if
   238   ///and only if it is connected and the number of incident arcs is even
   239   ///for each node. <em>Therefore, there are digraphs which are not Eulerian,
   240   ///but still have an Euler tour</em>.
   241   template<class Digraph>
   242 #ifdef DOXYGEN
   243   bool
   244 #else
   245   typename enable_if<UndirectedTagIndicator<Digraph>,bool>::type
   246   eulerian(const Digraph &g)
   247   {
   248     for(typename Digraph::NodeIt n(g);n!=INVALID;++n)
   249       if(countIncEdges(g,n)%2) return false;
   250     return connected(g);
   251   }
   252   template<class Digraph>
   253   typename disable_if<UndirectedTagIndicator<Digraph>,bool>::type
   254 #endif
   255   eulerian(const Digraph &g)
   256   {
   257     for(typename Digraph::NodeIt n(g);n!=INVALID;++n)
   258       if(countInArcs(g,n)!=countOutArcs(g,n)) return false;
   259     return connected(Undirector<const Digraph>(g));
   260   }
   261 
   262 }
   263 
   264 #endif