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 added
2 deleted
7 edited

Legend:

Unmodified
Added
Removed

  • doc/groups.dox

    r637 r633  
    436436\brief Algorithms for finding matchings in graphs and bipartite graphs.
    437437
    438 This group contains the algorithms for calculating
     438This group contains algorithm objects and functions to calculate
    439439matchings in graphs and bipartite graphs. The general matching problem is
    440 finding a subset of the edges for which each node has at most one incident
    441 edge.
     440finding a subset of the arcs which does not shares common endpoints.
    442441
    443442There are several different algorithms for calculate matchings in

  • lemon/Makefile.am

    r641 r614  
    9090        lemon/list_graph.h \
    9191        lemon/maps.h \
    92         lemon/matching.h \
    9392        lemon/math.h \
     93        lemon/max_matching.h \
    9494        lemon/min_cost_arborescence.h \
    9595        lemon/nauty_reader.h \

  • lemon/euler.h

    r639 r633  
    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/CMakeLists.txt

    r641 r596  
    3030  kruskal_test
    3131  maps_test
    32   matching_test
     32  max_matching_test
    3333  min_cost_arborescence_test
    3434  path_test

  • test/Makefile.am

    r641 r611  
    2626        test/kruskal_test \
    2727        test/maps_test \
    28         test/matching_test \
     28        test/max_matching_test \
    2929        test/min_cost_arborescence_test \
    3030        test/path_test \
    … …  
    7171test_maps_test_SOURCES = test/maps_test.cc
    7272test_mip_test_SOURCES = test/mip_test.cc
    73 test_matching_test_SOURCES = test/matching_test.cc
     73test_max_matching_test_SOURCES = test/max_matching_test.cc
    7474test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc
    7575test_path_test_SOURCES = test/path_test.cc

  • test/euler_test.cc

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

  • tools/dimacs-solver.cc

    r641 r631  
    4343#include <lemon/dijkstra.h>
    4444#include <lemon/preflow.h>
    45 #include <lemon/matching.h>
     45#include <lemon/max_matching.h>
    4646
    4747using namespace lemon;
Note: See TracChangeset for help on using the changeset viewer.