COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 592:2ebfdb89ec66 in lemon-main


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

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

Files:
2 edited

Legend:

Unmodified
Added
Removed

  • lemon/euler.h

    r591 r592  
    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

  • test/euler_test.cc

    r531 r592  
    1919#include <lemon/euler.h>
    2020#include <lemon/list_graph.h>
    21 #include <test/test_tools.h>
     21#include <lemon/adaptors.h>
     22#include "test_tools.h"
    2223
    2324using namespace lemon;
    2425
    2526template <typename Digraph>
    26 void checkDiEulerIt(const Digraph& g)
     27void checkDiEulerIt(const Digraph& g,
     28                    const typename Digraph::Node& start = INVALID)
    2729{
    2830  typename Digraph::template ArcMap<int> visitationNumber(g, 0);
    2931
    30   DiEulerIt<Digraph> e(g);
     32  DiEulerIt<Digraph> e(g, start);
     33  if (e == INVALID) return;
    3134  typename Digraph::Node firstNode = g.source(e);
    3235  typename Digraph::Node lastNode = g.target(e);
    33 
    34   for (; e != INVALID; ++e)
    35   {
    36     if (e != INVALID)
    37     {
    38       lastNode = g.target(e);
    39     }
     36  if (start != INVALID) {
     37    check(firstNode == start, "checkDiEulerIt: Wrong first node");
     38  }
     39
     40  for (; e != INVALID; ++e) {
     41    if (e != INVALID) lastNode = g.target(e);
    4042    ++visitationNumber[e];
    4143  }
    4244
    4345  check(firstNode == lastNode,
    44       "checkDiEulerIt: first and last node are not the same");
     46      "checkDiEulerIt: First and last nodes are not the same");
    4547
    4648  for (typename Digraph::ArcIt a(g); a != INVALID; ++a)
    4749  {
    4850    check(visitationNumber[a] == 1,
    49         "checkDiEulerIt: not visited or multiple times visited arc found");
     51        "checkDiEulerIt: Not visited or multiple times visited arc found");
    5052  }
    5153}
    5254
    5355template <typename Graph>
    54 void checkEulerIt(const Graph& g)
     56void checkEulerIt(const Graph& g,
     57                  const typename Graph::Node& start = INVALID)
    5558{
    5659  typename Graph::template EdgeMap<int> visitationNumber(g, 0);
    5760
    58   EulerIt<Graph> e(g);
    59   typename Graph::Node firstNode = g.u(e);
    60   typename Graph::Node lastNode = g.v(e);
    61 
    62   for (; e != INVALID; ++e)
    63   {
    64     if (e != INVALID)
    65     {
    66       lastNode = g.v(e);
    67     }
     61  EulerIt<Graph> e(g, start);
     62  if (e == INVALID) return;
     63  typename Graph::Node firstNode = g.source(typename Graph::Arc(e));
     64  typename Graph::Node lastNode = g.target(typename Graph::Arc(e));
     65  if (start != INVALID) {
     66    check(firstNode == start, "checkEulerIt: Wrong first node");
     67  }
     68
     69  for (; e != INVALID; ++e) {
     70    if (e != INVALID) lastNode = g.target(typename Graph::Arc(e));
    6871    ++visitationNumber[e];
    6972  }
    7073
    7174  check(firstNode == lastNode,
    72       "checkEulerIt: first and last node are not the same");
     75      "checkEulerIt: First and last nodes are not the same");
    7376
    7477  for (typename Graph::EdgeIt e(g); e != INVALID; ++e)
    7578  {
    7679    check(visitationNumber[e] == 1,
    77         "checkEulerIt: not visited or multiple times visited edge found");
     80        "checkEulerIt: Not visited or multiple times visited edge found");
    7881  }
    7982}
    … …  
    8285{
    8386  typedef ListDigraph Digraph;
    84   typedef ListGraph Graph;
    85 
    86   Digraph digraphWithEulerianCircuit;
    87   {
    88     Digraph& g = digraphWithEulerianCircuit;
    89 
    90     Digraph::Node n0 = g.addNode();
    91     Digraph::Node n1 = g.addNode();
    92     Digraph::Node n2 = g.addNode();
    93 
    94     g.addArc(n0, n1);
    95     g.addArc(n1, n0);
    96     g.addArc(n1, n2);
    97     g.addArc(n2, n1);
    98   }
    99 
    100   Digraph digraphWithoutEulerianCircuit;
    101   {
    102     Digraph& g = digraphWithoutEulerianCircuit;
    103 
    104     Digraph::Node n0 = g.addNode();
    105     Digraph::Node n1 = g.addNode();
    106     Digraph::Node n2 = g.addNode();
    107 
    108     g.addArc(n0, n1);
    109     g.addArc(n1, n0);
    110     g.addArc(n1, n2);
    111   }
    112 
    113   Graph graphWithEulerianCircuit;
    114   {
    115     Graph& g = graphWithEulerianCircuit;
    116 
    117     Graph::Node n0 = g.addNode();
    118     Graph::Node n1 = g.addNode();
    119     Graph::Node n2 = g.addNode();
    120 
    121     g.addEdge(n0, n1);
    122     g.addEdge(n1, n2);
    123     g.addEdge(n2, n0);
    124   }
    125 
    126   Graph graphWithoutEulerianCircuit;
    127   {
    128     Graph& g = graphWithoutEulerianCircuit;
    129 
    130     Graph::Node n0 = g.addNode();
    131     Graph::Node n1 = g.addNode();
    132     Graph::Node n2 = g.addNode();
    133 
    134     g.addEdge(n0, n1);
    135     g.addEdge(n1, n2);
    136   }
    137 
    138   checkDiEulerIt(digraphWithEulerianCircuit);
    139 
    140   checkEulerIt(graphWithEulerianCircuit);
    141 
    142   check(eulerian(digraphWithEulerianCircuit),
    143       "this graph should have an Eulerian circuit");
    144   check(!eulerian(digraphWithoutEulerianCircuit),
    145       "this graph should not have an Eulerian circuit");
    146 
    147   check(eulerian(graphWithEulerianCircuit),
    148       "this graph should have an Eulerian circuit");
    149   check(!eulerian(graphWithoutEulerianCircuit),
    150       "this graph should have an Eulerian circuit");
     87  typedef Undirector<Digraph> Graph;
     88 
     89  {
     90    Digraph d;
     91    Graph g(d);
     92   
     93    checkDiEulerIt(d);
     94    checkDiEulerIt(g);
     95    checkEulerIt(g);
     96
     97    check(eulerian(d), "This graph is Eulerian");
     98    check(eulerian(g), "This graph is Eulerian");
     99  }
     100  {
     101    Digraph d;
     102    Graph g(d);
     103    Digraph::Node n = d.addNode();
     104
     105    checkDiEulerIt(d);
     106    checkDiEulerIt(g);
     107    checkEulerIt(g);
     108
     109    check(eulerian(d), "This graph is Eulerian");
     110    check(eulerian(g), "This graph is Eulerian");
     111  }
     112  {
     113    Digraph d;
     114    Graph g(d);
     115    Digraph::Node n = d.addNode();
     116    d.addArc(n, n);
     117
     118    checkDiEulerIt(d);
     119    checkDiEulerIt(g);
     120    checkEulerIt(g);
     121
     122    check(eulerian(d), "This graph is Eulerian");
     123    check(eulerian(g), "This graph is Eulerian");
     124  }
     125  {
     126    Digraph d;
     127    Graph g(d);
     128    Digraph::Node n1 = d.addNode();
     129    Digraph::Node n2 = d.addNode();
     130    Digraph::Node n3 = d.addNode();
     131   
     132    d.addArc(n1, n2);
     133    d.addArc(n2, n1);
     134    d.addArc(n2, n3);
     135    d.addArc(n3, n2);
     136
     137    checkDiEulerIt(d);
     138    checkDiEulerIt(d, n2);
     139    checkDiEulerIt(g);
     140    checkDiEulerIt(g, n2);
     141    checkEulerIt(g);
     142    checkEulerIt(g, n2);
     143
     144    check(eulerian(d), "This graph is Eulerian");
     145    check(eulerian(g), "This graph is Eulerian");
     146  }
     147  {
     148    Digraph d;
     149    Graph g(d);
     150    Digraph::Node n1 = d.addNode();
     151    Digraph::Node n2 = d.addNode();
     152    Digraph::Node n3 = d.addNode();
     153    Digraph::Node n4 = d.addNode();
     154    Digraph::Node n5 = d.addNode();
     155    Digraph::Node n6 = d.addNode();
     156   
     157    d.addArc(n1, n2);
     158    d.addArc(n2, n4);
     159    d.addArc(n1, n3);
     160    d.addArc(n3, n4);
     161    d.addArc(n4, n1);
     162    d.addArc(n3, n5);
     163    d.addArc(n5, n2);
     164    d.addArc(n4, n6);
     165    d.addArc(n2, n6);
     166    d.addArc(n6, n1);
     167    d.addArc(n6, n3);
     168
     169    checkDiEulerIt(d);
     170    checkDiEulerIt(d, n1);
     171    checkDiEulerIt(d, n5);
     172
     173    checkDiEulerIt(g);
     174    checkDiEulerIt(g, n1);
     175    checkDiEulerIt(g, n5);
     176    checkEulerIt(g);
     177    checkEulerIt(g, n1);
     178    checkEulerIt(g, n5);
     179
     180    check(eulerian(d), "This graph is Eulerian");
     181    check(eulerian(g), "This graph is Eulerian");
     182  }
     183  {
     184    Digraph d;
     185    Graph g(d);
     186    Digraph::Node n0 = d.addNode();
     187    Digraph::Node n1 = d.addNode();
     188    Digraph::Node n2 = d.addNode();
     189    Digraph::Node n3 = d.addNode();
     190    Digraph::Node n4 = d.addNode();
     191    Digraph::Node n5 = d.addNode();
     192   
     193    d.addArc(n1, n2);
     194    d.addArc(n2, n3);
     195    d.addArc(n3, n1);
     196
     197    checkDiEulerIt(d);
     198    checkDiEulerIt(d, n2);
     199
     200    checkDiEulerIt(g);
     201    checkDiEulerIt(g, n2);
     202    checkEulerIt(g);
     203    checkEulerIt(g, n2);
     204
     205    check(!eulerian(d), "This graph is not Eulerian");
     206    check(!eulerian(g), "This graph is not Eulerian");
     207  }
     208  {
     209    Digraph d;
     210    Graph g(d);
     211    Digraph::Node n1 = d.addNode();
     212    Digraph::Node n2 = d.addNode();
     213    Digraph::Node n3 = d.addNode();
     214   
     215    d.addArc(n1, n2);
     216    d.addArc(n2, n3);
     217
     218    check(!eulerian(d), "This graph is not Eulerian");
     219    check(!eulerian(g), "This graph is not Eulerian");
     220  }
    151221
    152222  return 0;
Note: See TracChangeset for help on using the changeset viewer.