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 / [599:f63e87b9748e:600:0ba8dfce7259] in lemon-main


Ignore:
Files:
2 added
2 deleted
7 edited

Legend:

Unmodified
Added
Removed

  • doc/groups.dox

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

  • lemon/Makefile.am

    r567 r594  
    9090        lemon/list_graph.h \
    9191        lemon/maps.h \
     92        lemon/matching.h \
    9293        lemon/math.h \
    93         lemon/max_matching.h \
    9494        lemon/min_cost_arborescence.h \
    9595        lemon/nauty_reader.h \

  • lemon/euler.h

    r586 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)
    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/CMakeLists.txt

    r549 r594  
    3030  kruskal_test
    3131  maps_test
    32   max_matching_test
     32  matching_test
    3333  min_cost_arborescence_test
    3434  path_test

  • test/Makefile.am

    r564 r594  
    2626        test/kruskal_test \
    2727        test/maps_test \
    28         test/max_matching_test \
     28        test/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_max_matching_test_SOURCES = test/max_matching_test.cc
     73test_matching_test_SOURCES = test/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

    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;

  • tools/dimacs-solver.cc

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