COIN-OR::LEMON - Graph Library

Changeset 639:2ebfdb89ec66 in lemon for lemon


Ignore:
Timestamp:
04/15/09 11:47:19 (15 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Improvements for the Euler tools and the test file (#264)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/euler.h

    r638 r639  
    2727/// \ingroup graph_properties
    2828/// \file
    29 /// \brief Euler tour
     29/// \brief Euler tour iterators and a function for checking the \e Eulerian
     30/// property.
    3031///
    31 ///This file provides an Euler tour iterator and ways to check
    32 ///if a digraph is euler.
    33 
     32///This file provides Euler tour iterators and a function to check
     33///if a (di)graph is \e Eulerian.
    3434
    3535namespace lemon {
    3636
    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).
    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.
     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.
     42  ///
     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.
    5047  ///\code
    5148  ///  std::vector<ListDigraph::Arc> et;
    52   ///  for(DiEulerIt<ListDigraph> e(g),e!=INVALID;++e)
     49  ///  for(DiEulerIt<ListDigraph> e(g); e!=INVALID; ++e)
    5350  ///    et.push_back(e);
    5451  ///\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.
    5654  ///\sa EulerIt
    5755  template<typename GR>
     
    6664
    6765    const GR &g;
    68     typename GR::template NodeMap<OutArcIt> nedge;
     66    typename GR::template NodeMap<OutArcIt> narc;
    6967    std::list<Arc> euler;
    7068
     
    7371    ///Constructor
    7472
     73    ///Constructor.
    7574    ///\param gr 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.
     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.
    7877    DiEulerIt(const GR &gr, typename GR::Node start = INVALID)
    79       : g(gr), nedge(g)
     78      : g(gr), narc(g)
    8079    {
    8180      if (start==INVALID) {
     
    8584      }
    8685      if (start!=INVALID) {
    87         for (NodeIt n(g); n!=INVALID; ++n) nedge[n]=OutArcIt(g,n);
    88         while (nedge[start]!=INVALID) {
    89           euler.push_back(nedge[start]);
    90           Node next=g.target(nedge[start]);
    91           ++nedge[start];
     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];
    9291          start=next;
    9392        }
     
    9594    }
    9695
    97     ///Arc Conversion
     96    ///Arc conversion
    9897    operator Arc() { return euler.empty()?INVALID:euler.front(); }
     98    ///Compare with \c INVALID
    9999    bool operator==(Invalid) { return euler.empty(); }
     100    ///Compare with \c INVALID
    100101    bool operator!=(Invalid) { return !euler.empty(); }
    101102
    102103    ///Next arc of the tour
     104
     105    ///Next arc of the tour
     106    ///
    103107    DiEulerIt &operator++() {
    104108      Node s=g.target(euler.front());
    105109      euler.pop_front();
    106       //This produces a warning.Strange.
    107       //std::list<Arc>::iterator next=euler.begin();
    108110      typename std::list<Arc>::iterator next=euler.begin();
    109       while(nedge[s]!=INVALID) {
    110         euler.insert(next,nedge[s]);
    111         Node n=g.target(nedge[s]);
    112         ++nedge[s];
     111      while(narc[s]!=INVALID) {
     112        euler.insert(next,narc[s]);
     113        Node n=g.target(narc[s]);
     114        ++narc[s];
    113115        s=n;
    114116      }
     
    117119    ///Postfix incrementation
    118120
     121    /// Postfix incrementation.
     122    ///
    119123    ///\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
    121125    ///expect.
    122126    Arc operator++(int)
     
    128132  };
    129133
    130   ///Euler iterator for graphs.
     134  ///Euler tour iterator for graphs.
    131135
    132136  /// \ingroup graph_properties
    133   ///This iterator converts to the \c Arc (or \c Edge)
    134   ///type of the digraph and using
    135   ///operator ++, it provides an Euler tour of an undirected
    136   ///digraph (if there exists).
    137   ///
    138   ///For example
    139   ///if the given digraph if Euler (i.e it has only one nontrivial component
    140   ///and the degree of each node is even),
     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.
     140  ///
     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),
    141143  ///the following code will print the arc IDs according to an
    142144  ///Euler tour of \c g.
    143145  ///\code
    144   ///  for(EulerIt<ListGraph> e(g),e!=INVALID;++e) {
     146  ///  for(EulerIt<ListGraph> e(g); e!=INVALID; ++e) {
    145147  ///    std::cout << g.id(Edge(e)) << std::eol;
    146148  ///  }
    147149  ///\endcode
    148   ///Although the iterator provides an Euler tour of an graph,
    149   ///it still returns Arcs in order to indicate the direction of the tour.
    150   ///(But Arc will convert to Edges, of course).
    151   ///
    152   ///If \c g is not Euler then the resulted tour will not be full or closed.
    153   ///\sa EulerIt
     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.)
     153  ///
     154  ///If \c g has no Euler tour, then the resulted walk will not be closed
     155  ///or not contain all edges.
    154156  template<typename GR>
    155157  class EulerIt
     
    164166
    165167    const GR &g;
    166     typename GR::template NodeMap<OutArcIt> nedge;
     168    typename GR::template NodeMap<OutArcIt> narc;
    167169    typename GR::template EdgeMap<bool> visited;
    168170    std::list<Arc> euler;
     
    172174    ///Constructor
    173175
    174     ///\param gr An graph.
    175     ///\param start The starting point of the tour. If it is not given
    176     ///       the tour will start from the first node.
     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.
    177180    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)
    179182    {
    180183      if (start==INVALID) {
     
    184187      }
    185188      if (start!=INVALID) {
    186         for (NodeIt n(g); n!=INVALID; ++n) nedge[n]=OutArcIt(g,n);
    187         while(nedge[start]!=INVALID) {
    188           euler.push_back(nedge[start]);
    189           visited[nedge[start]]=true;
    190           Node next=g.target(nedge[start]);
    191           ++nedge[start];
     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];
    192195          start=next;
    193           while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start];
     196          while(narc[start]!=INVALID && visited[narc[start]]) ++narc[start];
    194197        }
    195198      }
    196199    }
    197200
    198     ///Arc Conversion
     201    ///Arc conversion
    199202    operator Arc() const { return euler.empty()?INVALID:euler.front(); }
    200     ///Arc Conversion
     203    ///Edge conversion
    201204    operator Edge() const { return euler.empty()?INVALID:euler.front(); }
    202     ///\e
     205    ///Compare with \c INVALID
    203206    bool operator==(Invalid) const { return euler.empty(); }
    204     ///\e
     207    ///Compare with \c INVALID
    205208    bool operator!=(Invalid) const { return !euler.empty(); }
    206209
    207210    ///Next arc of the tour
     211
     212    ///Next arc of the tour
     213    ///
    208214    EulerIt &operator++() {
    209215      Node s=g.target(euler.front());
    210216      euler.pop_front();
    211217      typename std::list<Arc>::iterator next=euler.begin();
    212 
    213       while(nedge[s]!=INVALID) {
    214         while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s];
    215         if(nedge[s]==INVALID) break;
     218      while(narc[s]!=INVALID) {
     219        while(narc[s]!=INVALID && visited[narc[s]]) ++narc[s];
     220        if(narc[s]==INVALID) break;
    216221        else {
    217           euler.insert(next,nedge[s]);
    218           visited[nedge[s]]=true;
    219           Node n=g.target(nedge[s]);
    220           ++nedge[s];
     222          euler.insert(next,narc[s]);
     223          visited[narc[s]]=true;
     224          Node n=g.target(narc[s]);
     225          ++narc[s];
    221226          s=n;
    222227        }
     
    227232    ///Postfix incrementation
    228233
    229     ///\warning This incrementation
    230     ///returns an \c Arc, not an \ref EulerIt, as one may
    231     ///expect.
     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.
    232238    Arc operator++(int)
    233239    {
     
    239245
    240246
    241   ///Checks if the graph is Eulerian
     247  ///Check if the given graph is \e Eulerian
    242248
    243249  /// \ingroup graph_properties
    244   ///Checks if the graph is Eulerian. It works for both directed and undirected
    245   ///graphs.
    246   ///\note By definition, a digraph is called \e Eulerian if
    247   ///and only if it is connected and the number of its incoming and outgoing
     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
    248255  ///arcs are the same for each node.
    249256  ///Similarly, an undirected graph is called \e Eulerian if
    250   ///and only if it is connected and the number of incident arcs is even
    251   ///for each node. <em>Therefore, there are digraphs which are not Eulerian,
    252   ///but still have an Euler tour</em>.
     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
    253264  template<typename GR>
    254265#ifdef DOXYGEN
     
    269280    for(typename GR::NodeIt n(g);n!=INVALID;++n)
    270281      if(countInArcs(g,n)!=countOutArcs(g,n)) return false;
    271     return connected(Undirector<const GR>(g));
     282    return connected(undirector(g));
    272283  }
    273284
Note: See TracChangeset for help on using the changeset viewer.