COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changes in / [595:16d7255a6849:594:d657c71db7db] in lemon-main


Ignore:
Files:
2 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

  • test/euler_test.cc

    r592 r531  
    1919#include <lemon/euler.h>
    2020#include <lemon/list_graph.h>
    21 #include <lemon/adaptors.h>
    22 #include "test_tools.h"
     21#include <test/test_tools.h>
    2322
    2423using namespace lemon;
    2524
    2625template <typename Digraph>
    27 void checkDiEulerIt(const Digraph& g,
    28                     const typename Digraph::Node& start = INVALID)
     26void checkDiEulerIt(const Digraph& g)
    2927{
    3028  typename Digraph::template ArcMap<int> visitationNumber(g, 0);
    3129
    32   DiEulerIt<Digraph> e(g, start);
    33   if (e == INVALID) return;
     30  DiEulerIt<Digraph> e(g);
    3431  typename Digraph::Node firstNode = g.source(e);
    3532  typename Digraph::Node lastNode = g.target(e);
    36   if (start != INVALID) {
    37     check(firstNode == start, "checkDiEulerIt: Wrong first node");
    38   }
    3933
    40   for (; e != INVALID; ++e) {
    41     if (e != INVALID) lastNode = g.target(e);
     34  for (; e != INVALID; ++e)
     35  {
     36    if (e != INVALID)
     37    {
     38      lastNode = g.target(e);
     39    }
    4240    ++visitationNumber[e];
    4341  }
    4442
    4543  check(firstNode == lastNode,
    46       "checkDiEulerIt: First and last nodes are not the same");
     44      "checkDiEulerIt: first and last node are not the same");
    4745
    4846  for (typename Digraph::ArcIt a(g); a != INVALID; ++a)
    4947  {
    5048    check(visitationNumber[a] == 1,
    51         "checkDiEulerIt: Not visited or multiple times visited arc found");
     49        "checkDiEulerIt: not visited or multiple times visited arc found");
    5250  }
    5351}
    5452
    5553template <typename Graph>
    56 void checkEulerIt(const Graph& g,
    57                   const typename Graph::Node& start = INVALID)
     54void checkEulerIt(const Graph& g)
    5855{
    5956  typename Graph::template EdgeMap<int> visitationNumber(g, 0);
    6057
    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   }
     58  EulerIt<Graph> e(g);
     59  typename Graph::Node firstNode = g.u(e);
     60  typename Graph::Node lastNode = g.v(e);
    6861
    69   for (; e != INVALID; ++e) {
    70     if (e != INVALID) lastNode = g.target(typename Graph::Arc(e));
     62  for (; e != INVALID; ++e)
     63  {
     64    if (e != INVALID)
     65    {
     66      lastNode = g.v(e);
     67    }
    7168    ++visitationNumber[e];
    7269  }
    7370
    7471  check(firstNode == lastNode,
    75       "checkEulerIt: First and last nodes are not the same");
     72      "checkEulerIt: first and last node are not the same");
    7673
    7774  for (typename Graph::EdgeIt e(g); e != INVALID; ++e)
    7875  {
    7976    check(visitationNumber[e] == 1,
    80         "checkEulerIt: Not visited or multiple times visited edge found");
     77        "checkEulerIt: not visited or multiple times visited edge found");
    8178  }
    8279}
    … …  
    8582{
    8683  typedef ListDigraph Digraph;
    87   typedef Undirector<Digraph> Graph;
    88  
     84  typedef ListGraph Graph;
     85
     86  Digraph digraphWithEulerianCircuit;
    8987  {
    90     Digraph d;
    91     Graph g(d);
    92    
    93     checkDiEulerIt(d);
    94     checkDiEulerIt(g);
    95     checkEulerIt(g);
     88    Digraph& g = digraphWithEulerianCircuit;
    9689
    97     check(eulerian(d), "This graph is Eulerian");
    98     check(eulerian(g), "This graph is Eulerian");
     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);
    9998  }
     99
     100  Digraph digraphWithoutEulerianCircuit;
    100101  {
    101     Digraph d;
    102     Graph g(d);
    103     Digraph::Node n = d.addNode();
     102    Digraph& g = digraphWithoutEulerianCircuit;
    104103
    105     checkDiEulerIt(d);
    106     checkDiEulerIt(g);
    107     checkEulerIt(g);
     104    Digraph::Node n0 = g.addNode();
     105    Digraph::Node n1 = g.addNode();
     106    Digraph::Node n2 = g.addNode();
    108107
    109     check(eulerian(d), "This graph is Eulerian");
    110     check(eulerian(g), "This graph is Eulerian");
     108    g.addArc(n0, n1);
     109    g.addArc(n1, n0);
     110    g.addArc(n1, n2);
    111111  }
     112
     113  Graph graphWithEulerianCircuit;
    112114  {
    113     Digraph d;
    114     Graph g(d);
    115     Digraph::Node n = d.addNode();
    116     d.addArc(n, n);
     115    Graph& g = graphWithEulerianCircuit;
    117116
    118     checkDiEulerIt(d);
    119     checkDiEulerIt(g);
    120     checkEulerIt(g);
     117    Graph::Node n0 = g.addNode();
     118    Graph::Node n1 = g.addNode();
     119    Graph::Node n2 = g.addNode();
    121120
    122     check(eulerian(d), "This graph is Eulerian");
    123     check(eulerian(g), "This graph is Eulerian");
     121    g.addEdge(n0, n1);
     122    g.addEdge(n1, n2);
     123    g.addEdge(n2, n0);
    124124  }
     125
     126  Graph graphWithoutEulerianCircuit;
    125127  {
    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);
     128    Graph& g = graphWithoutEulerianCircuit;
    136129
    137     checkDiEulerIt(d);
    138     checkDiEulerIt(d, n2);
    139     checkDiEulerIt(g);
    140     checkDiEulerIt(g, n2);
    141     checkEulerIt(g);
    142     checkEulerIt(g, n2);
     130    Graph::Node n0 = g.addNode();
     131    Graph::Node n1 = g.addNode();
     132    Graph::Node n2 = g.addNode();
    143133
    144     check(eulerian(d), "This graph is Eulerian");
    145     check(eulerian(g), "This graph is Eulerian");
     134    g.addEdge(n0, n1);
     135    g.addEdge(n1, n2);
    146136  }
    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);
    168137
    169     checkDiEulerIt(d);
    170     checkDiEulerIt(d, n1);
    171     checkDiEulerIt(d, n5);
     138  checkDiEulerIt(digraphWithEulerianCircuit);
    172139
    173     checkDiEulerIt(g);
    174     checkDiEulerIt(g, n1);
    175     checkDiEulerIt(g, n5);
    176     checkEulerIt(g);
    177     checkEulerIt(g, n1);
    178     checkEulerIt(g, n5);
     140  checkEulerIt(graphWithEulerianCircuit);
    179141
    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);
     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");
    196146
    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   }
     147  check(eulerian(graphWithEulerianCircuit),
     148      "this graph should have an Eulerian circuit");
     149  check(!eulerian(graphWithoutEulerianCircuit),
     150      "this graph should have an Eulerian circuit");
    221151
    222152  return 0;
Note: See TracChangeset for help on using the changeset viewer.