COIN-OR::LEMON - Graph Library

Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/euler.h

    r592 r586  
    2727/// \ingroup graph_properties
    2828/// \file
    29 /// \brief Euler tour iterators and a function for checking the \e Eulerian
    30 /// property.
     29/// \brief Euler tour
    3130///
    32 ///This file provides Euler tour iterators and a function to check
    33 ///if a (di)graph is \e Eulerian.
     31///This file provides an Euler tour iterator and ways to check
     32///if a digraph is euler.
     33
    3434
    3535namespace lemon {
    3636
    37   ///Euler tour iterator for digraphs.
    38 
    39   /// \ingroup graph_prop
    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.
     37  ///Euler iterator for digraphs.
     38
     39  /// \ingroup graph_properties
     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).
    4243  ///
    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
    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.
     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.
    4750  ///\code
    4851  ///  std::vector<ListDigraph::Arc> et;
    49   ///  for(DiEulerIt<ListDigraph> e(g); e!=INVALID; ++e)
     52  ///  for(DiEulerIt<ListDigraph> e(g),e!=INVALID;++e)
    5053  ///    et.push_back(e);
    5154  ///\endcode
    52   ///If \c g has no Euler tour, then the resulted walk will not be closed
    53   ///or not contain all arcs.
     55  ///If \c g is not Euler then the resulted tour will not be full or closed.
    5456  ///\sa EulerIt
    5557  template<typename GR>
     
    6466
    6567    const GR &g;
    66     typename GR::template NodeMap<OutArcIt> narc;
     68    typename GR::template NodeMap<OutArcIt> nedge;
    6769    std::list<Arc> euler;
    6870
     
    7173    ///Constructor
    7274
    73     ///Constructor.
    7475    ///\param gr A digraph.
    75     ///\param start The starting point of the tour. If it is not given,
    76     ///the tour will start from the first node that has an outgoing arc.
     76    ///\param start The starting point of the tour. If it is not given
     77    ///       the tour will start from the first node.
    7778    DiEulerIt(const GR &gr, typename GR::Node start = INVALID)
    78       : g(gr), narc(g)
    79     {
    80       if (start==INVALID) {
    81         NodeIt n(g);
    82         while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n;
    83         start=n;
    84       }
    85       if (start!=INVALID) {
    86         for (NodeIt n(g); n!=INVALID; ++n) narc[n]=OutArcIt(g,n);
    87         while (narc[start]!=INVALID) {
    88           euler.push_back(narc[start]);
    89           Node next=g.target(narc[start]);
    90           ++narc[start];
    91           start=next;
    92         }
    93       }
    94     }
    95 
    96     ///Arc conversion
     79      : g(gr), 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
    9792    operator Arc() { return euler.empty()?INVALID:euler.front(); }
    98     ///Compare with \c INVALID
    9993    bool operator==(Invalid) { return euler.empty(); }
    100     ///Compare with \c INVALID
    10194    bool operator!=(Invalid) { return !euler.empty(); }
    10295
    10396    ///Next arc of the tour
    104 
    105     ///Next arc of the tour
    106     ///
    10797    DiEulerIt &operator++() {
    10898      Node s=g.target(euler.front());
    10999      euler.pop_front();
     100      //This produces a warning.Strange.
     101      //std::list<Arc>::iterator next=euler.begin();
    110102      typename std::list<Arc>::iterator next=euler.begin();
    111       while(narc[s]!=INVALID) {
    112         euler.insert(next,narc[s]);
    113         Node n=g.target(narc[s]);
    114         ++narc[s];
     103      while(nedge[s]!=INVALID) {
     104        euler.insert(next,nedge[s]);
     105        Node n=g.target(nedge[s]);
     106        ++nedge[s];
    115107        s=n;
    116108      }
     
    119111    ///Postfix incrementation
    120112
    121     /// Postfix incrementation.
    122     ///
    123113    ///\warning This incrementation
    124     ///returns an \c Arc, not a \ref DiEulerIt, as one may
     114    ///returns an \c Arc, not an \ref DiEulerIt, as one may
    125115    ///expect.
    126116    Arc operator++(int)
     
    132122  };
    133123
    134   ///Euler tour iterator for graphs.
     124  ///Euler iterator for graphs.
    135125
    136126  /// \ingroup graph_properties
    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
    139   ///and \c Edge types of the graph.
     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).
    140131  ///
    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),
     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),
    143135  ///the following code will print the arc IDs according to an
    144136  ///Euler tour of \c g.
    145137  ///\code
    146   ///  for(EulerIt<ListGraph> e(g); e!=INVALID; ++e) {
     138  ///  for(EulerIt<ListGraph> e(g),e!=INVALID;++e) {
    147139  ///    std::cout << g.id(Edge(e)) << std::eol;
    148140  ///  }
    149141  ///\endcode
    150   ///Although this iterator is for undirected graphs, it still returns
    151   ///arcs in order to indicate the direction of the tour.
    152   ///(But arcs convert to edges, of course.)
     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).
    153145  ///
    154   ///If \c g has no Euler tour, then the resulted walk will not be closed
    155   ///or not contain all edges.
     146  ///If \c g is not Euler then the resulted tour will not be full or closed.
     147  ///\sa EulerIt
    156148  template<typename GR>
    157149  class EulerIt
     
    166158
    167159    const GR &g;
    168     typename GR::template NodeMap<OutArcIt> narc;
     160    typename GR::template NodeMap<OutArcIt> nedge;
    169161    typename GR::template EdgeMap<bool> visited;
    170162    std::list<Arc> euler;
     
    174166    ///Constructor
    175167
    176     ///Constructor.
    177     ///\param gr A graph.
    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.
     168    ///\param gr 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.
    180171    EulerIt(const GR &gr, typename GR::Node start = INVALID)
    181       : g(gr), narc(g), visited(g, false)
    182     {
    183       if (start==INVALID) {
    184         NodeIt n(g);
    185         while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n;
    186         start=n;
    187       }
    188       if (start!=INVALID) {
    189         for (NodeIt n(g); n!=INVALID; ++n) narc[n]=OutArcIt(g,n);
    190         while(narc[start]!=INVALID) {
    191           euler.push_back(narc[start]);
    192           visited[narc[start]]=true;
    193           Node next=g.target(narc[start]);
    194           ++narc[start];
    195           start=next;
    196           while(narc[start]!=INVALID && visited[narc[start]]) ++narc[start];
    197         }
    198       }
    199     }
    200 
    201     ///Arc conversion
     172      : g(gr), 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
    202187    operator Arc() const { return euler.empty()?INVALID:euler.front(); }
    203     ///Edge conversion
     188    ///Arc Conversion
    204189    operator Edge() const { return euler.empty()?INVALID:euler.front(); }
    205     ///Compare with \c INVALID
     190    ///\e
    206191    bool operator==(Invalid) const { return euler.empty(); }
    207     ///Compare with \c INVALID
     192    ///\e
    208193    bool operator!=(Invalid) const { return !euler.empty(); }
    209194
    210195    ///Next arc of the tour
    211 
    212     ///Next arc of the tour
    213     ///
    214196    EulerIt &operator++() {
    215197      Node s=g.target(euler.front());
    216198      euler.pop_front();
    217199      typename std::list<Arc>::iterator next=euler.begin();
    218       while(narc[s]!=INVALID) {
    219         while(narc[s]!=INVALID && visited[narc[s]]) ++narc[s];
    220         if(narc[s]==INVALID) break;
     200
     201      while(nedge[s]!=INVALID) {
     202        while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s];
     203        if(nedge[s]==INVALID) break;
    221204        else {
    222           euler.insert(next,narc[s]);
    223           visited[narc[s]]=true;
    224           Node n=g.target(narc[s]);
    225           ++narc[s];
     205          euler.insert(next,nedge[s]);
     206          visited[nedge[s]]=true;
     207          Node n=g.target(nedge[s]);
     208          ++nedge[s];
    226209          s=n;
    227210        }
     
    232215    ///Postfix incrementation
    233216
    234     /// Postfix incrementation.
    235     ///
    236     ///\warning This incrementation returns an \c Arc (which converts to
    237     ///an \c Edge), not an \ref EulerIt, as one may expect.
     217    ///\warning This incrementation
     218    ///returns an \c Arc, not an \ref EulerIt, as one may
     219    ///expect.
    238220    Arc operator++(int)
    239221    {
     
    245227
    246228
    247   ///Check if the given graph is \e Eulerian
     229  ///Checks if the graph is Eulerian
    248230
    249231  /// \ingroup graph_properties
    250   ///This function checks if the given graph is \e Eulerian.
    251   ///It works for both directed and undirected graphs.
    252   ///
    253   ///By definition, a digraph is called \e Eulerian if
    254   ///and only if it is connected and the number of incoming and outgoing
     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
    255236  ///arcs are the same for each node.
    256237  ///Similarly, an undirected graph is called \e Eulerian if
    257   ///and only if it is connected and the number of incident edges is even
    258   ///for each node.
    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
     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>.
    264241  template<typename GR>
    265242#ifdef DOXYGEN
     
    280257    for(typename GR::NodeIt n(g);n!=INVALID;++n)
    281258      if(countInArcs(g,n)!=countOutArcs(g,n)) return false;
    282     return connected(undirector(g));
     259    return connected(Undirector<const GR>(g));
    283260  }
    284261
Note: See TracChangeset for help on using the changeset viewer.