COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search


Ignore:
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • lemon/euler.h

    r633 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)
    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
     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
    9297    operator Arc() { return euler.empty()?INVALID:euler.front(); }
     98    ///Compare with \c INVALID
    9399    bool operator==(Invalid) { return euler.empty(); }
     100    ///Compare with \c INVALID
    94101    bool operator!=(Invalid) { return !euler.empty(); }
    95102
    96103    ///Next arc of the tour
     104
     105    ///Next arc of the tour
     106    ///
    97107    DiEulerIt &operator++() {
    98108      Node s=g.target(euler.front());
    99109      euler.pop_front();
    100       //This produces a warning.Strange.
    101       //std::list<Arc>::iterator next=euler.begin();
    102110      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];
     111      while(narc[s]!=INVALID) {
     112        euler.insert(next,narc[s]);
     113        Node n=g.target(narc[s]);
     114        ++narc[s];
    107115        s=n;
    108116      }
    … …  
    111119    ///Postfix incrementation
    112120
     121    /// Postfix incrementation.
     122    ///
    113123    ///\warning This incrementation
    114     ///returns an \c Arc, not an \ref DiEulerIt, as one may
     124    ///returns an \c Arc, not a \ref DiEulerIt, as one may
    115125    ///expect.
    116126    Arc operator++(int)
    … …  
    122132  };
    123133
    124   ///Euler iterator for graphs.
     134  ///Euler tour iterator for graphs.
    125135
    126136  /// \ingroup graph_properties
    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),
     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),
    135143  ///the following code will print the arc IDs according to an
    136144  ///Euler tour of \c g.
    137145  ///\code
    138   ///  for(EulerIt<ListGraph> e(g),e!=INVALID;++e) {
     146  ///  for(EulerIt<ListGraph> e(g); e!=INVALID; ++e) {
    139147  ///    std::cout << g.id(Edge(e)) << std::eol;
    140148  ///  }
    141149  ///\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
     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.
    148156  template<typename GR>
    149157  class EulerIt
    … …  
    158166
    159167    const GR &g;
    160     typename GR::template NodeMap<OutArcIt> nedge;
     168    typename GR::template NodeMap<OutArcIt> narc;
    161169    typename GR::template EdgeMap<bool> visited;
    162170    std::list<Arc> euler;
    … …  
    166174    ///Constructor
    167175
    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.
     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.
    171180    EulerIt(const GR &gr, typename GR::Node start = INVALID)
    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
     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
    187202    operator Arc() const { return euler.empty()?INVALID:euler.front(); }
    188     ///Arc Conversion
     203    ///Edge conversion
    189204    operator Edge() const { return euler.empty()?INVALID:euler.front(); }
    190     ///\e
     205    ///Compare with \c INVALID
    191206    bool operator==(Invalid) const { return euler.empty(); }
    192     ///\e
     207    ///Compare with \c INVALID
    193208    bool operator!=(Invalid) const { return !euler.empty(); }
    194209
    195210    ///Next arc of the tour
     211
     212    ///Next arc of the tour
     213    ///
    196214    EulerIt &operator++() {
    197215      Node s=g.target(euler.front());
    198216      euler.pop_front();
    199217      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;
     218      while(narc[s]!=INVALID) {
     219        while(narc[s]!=INVALID && visited[narc[s]]) ++narc[s];
     220        if(narc[s]==INVALID) break;
    204221        else {
    205           euler.insert(next,nedge[s]);
    206           visited[nedge[s]]=true;
    207           Node n=g.target(nedge[s]);
    208           ++nedge[s];
     222          euler.insert(next,narc[s]);
     223          visited[narc[s]]=true;
     224          Node n=g.target(narc[s]);
     225          ++narc[s];
    209226          s=n;
    210227        }
    … …  
    215232    ///Postfix incrementation
    216233
    217     ///\warning This incrementation
    218     ///returns an \c Arc, not an \ref EulerIt, as one may
    219     ///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.
    220238    Arc operator++(int)
    221239    {
    … …  
    227245
    228246
    229   ///Checks if the graph is Eulerian
     247  ///Check if the given graph is \e Eulerian
    230248
    231249  /// \ingroup graph_properties
    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
     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
    236255  ///arcs are the same for each node.
    237256  ///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>.
     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
    241264  template<typename GR>
    242265#ifdef DOXYGEN
    … …  
    257280    for(typename GR::NodeIt n(g);n!=INVALID;++n)
    258281      if(countInArcs(g,n)!=countOutArcs(g,n)) return false;
    259     return connected(Undirector<const GR>(g));
     282    return connected(undirector(g));
    260283  }
    261284

  • test/euler_test.cc

    r578 r639  
    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.