# Changes in /[646:f63e87b9748e:647:0ba8dfce7259] in lemon

Ignore:
Files:
2 deleted
7 edited

Unmodified
Removed
• ## doc/groups.dox

 r633 \brief Algorithms for finding matchings in graphs and bipartite graphs. This group contains algorithm objects and functions to calculate This group contains the algorithms for calculating matchings in graphs and bipartite graphs. The general matching problem is finding a subset of the arcs which does not shares common endpoints. finding a subset of the edges for which each node has at most one incident edge. There are several different algorithms for calculate matchings in
• ## lemon/Makefile.am

 r614 lemon/list_graph.h \ lemon/maps.h \ lemon/matching.h \ lemon/math.h \ lemon/max_matching.h \ lemon/min_cost_arborescence.h \ lemon/nauty_reader.h \
• ## lemon/euler.h

 r633 /// \ingroup graph_properties /// \file /// \brief Euler tour /// \brief Euler tour iterators and a function for checking the \e Eulerian /// property. /// ///This file provides an Euler tour iterator and ways to check ///if a digraph is euler. ///This file provides Euler tour iterators and a function to check ///if a (di)graph is \e Eulerian. namespace lemon { ///Euler iterator for digraphs. /// \ingroup graph_properties ///This iterator converts to the \c Arc type of the digraph and using ///operator ++, it provides an Euler tour of a \e directed ///graph (if there exists). /// ///For example ///if the given digraph is Euler (i.e it has only one nontrivial component ///and the in-degree is equal to the out-degree for all nodes), ///the following code will put the arcs of \c g ///to the vector \c et according to an ///Euler tour of \c g. ///Euler tour iterator for digraphs. /// \ingroup graph_prop ///This iterator provides an Euler tour (Eulerian circuit) of a \e directed ///graph (if there exists) and it converts to the \c Arc type of the digraph. /// ///For example, if the given digraph has an Euler tour (i.e it has only one ///non-trivial component and the in-degree is equal to the out-degree ///for all nodes), then the following code will put the arcs of \c g ///to the vector \c et according to an Euler tour of \c g. ///\code ///  std::vector et; ///  for(DiEulerIt e(g),e!=INVALID;++e) ///  for(DiEulerIt e(g); e!=INVALID; ++e) ///    et.push_back(e); ///\endcode ///If \c g is not Euler then the resulted tour will not be full or closed. ///If \c g has no Euler tour, then the resulted walk will not be closed ///or not contain all arcs. ///\sa EulerIt template const GR &g; typename GR::template NodeMap nedge; typename GR::template NodeMap narc; std::list euler; ///Constructor ///Constructor. ///\param gr A digraph. ///\param start The starting point of the tour. If it is not given ///       the tour will start from the first node. ///\param start The starting point of the tour. If it is not given, ///the tour will start from the first node that has an outgoing arc. DiEulerIt(const GR &gr, typename GR::Node start = INVALID) : g(gr), nedge(g) { if(start==INVALID) start=NodeIt(g); for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n); while(nedge[start]!=INVALID) { euler.push_back(nedge[start]); Node next=g.target(nedge[start]); ++nedge[start]; start=next; } } ///Arc Conversion : g(gr), narc(g) { if (start==INVALID) { NodeIt n(g); while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n; start=n; } if (start!=INVALID) { for (NodeIt n(g); n!=INVALID; ++n) narc[n]=OutArcIt(g,n); while (narc[start]!=INVALID) { euler.push_back(narc[start]); Node next=g.target(narc[start]); ++narc[start]; start=next; } } } ///Arc conversion operator Arc() { return euler.empty()?INVALID:euler.front(); } ///Compare with \c INVALID bool operator==(Invalid) { return euler.empty(); } ///Compare with \c INVALID bool operator!=(Invalid) { return !euler.empty(); } ///Next arc of the tour ///Next arc of the tour /// DiEulerIt &operator++() { Node s=g.target(euler.front()); euler.pop_front(); //This produces a warning.Strange. //std::list::iterator next=euler.begin(); typename std::list::iterator next=euler.begin(); while(nedge[s]!=INVALID) { euler.insert(next,nedge[s]); Node n=g.target(nedge[s]); ++nedge[s]; while(narc[s]!=INVALID) { euler.insert(next,narc[s]); Node n=g.target(narc[s]); ++narc[s]; s=n; } ///Postfix incrementation /// Postfix incrementation. /// ///\warning This incrementation ///returns an \c Arc, not an \ref DiEulerIt, as one may ///returns an \c Arc, not a \ref DiEulerIt, as one may ///expect. Arc operator++(int) }; ///Euler iterator for graphs. ///Euler tour iterator for graphs. /// \ingroup graph_properties ///This iterator converts to the \c Arc (or \c Edge) ///type of the digraph and using ///operator ++, it provides an Euler tour of an undirected ///digraph (if there exists). /// ///For example ///if the given digraph if Euler (i.e it has only one nontrivial component ///and the degree of each node is even), ///This iterator provides an Euler tour (Eulerian circuit) of an ///\e undirected graph (if there exists) and it converts to the \c Arc ///and \c Edge types of the graph. /// ///For example, if the given graph has an Euler tour (i.e it has only one ///non-trivial component and the degree of each node is even), ///the following code will print the arc IDs according to an ///Euler tour of \c g. ///\code ///  for(EulerIt e(g),e!=INVALID;++e) { ///  for(EulerIt e(g); e!=INVALID; ++e) { ///    std::cout << g.id(Edge(e)) << std::eol; ///  } ///\endcode ///Although the iterator provides an Euler tour of an graph, ///it still returns Arcs in order to indicate the direction of the tour. ///(But Arc will convert to Edges, of course). /// ///If \c g is not Euler then the resulted tour will not be full or closed. ///\sa EulerIt ///Although this iterator is for undirected graphs, it still returns ///arcs in order to indicate the direction of the tour. ///(But arcs convert to edges, of course.) /// ///If \c g has no Euler tour, then the resulted walk will not be closed ///or not contain all edges. template class EulerIt const GR &g; typename GR::template NodeMap nedge; typename GR::template NodeMap narc; typename GR::template EdgeMap visited; std::list euler; ///Constructor ///\param gr An graph. ///\param start The starting point of the tour. If it is not given ///       the tour will start from the first node. ///Constructor. ///\param gr A graph. ///\param start The starting point of the tour. If it is not given, ///the tour will start from the first node that has an incident edge. EulerIt(const GR &gr, typename GR::Node start = INVALID) : g(gr), nedge(g), visited(g, false) { if(start==INVALID) start=NodeIt(g); for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n); while(nedge[start]!=INVALID) { euler.push_back(nedge[start]); visited[nedge[start]]=true; Node next=g.target(nedge[start]); ++nedge[start]; start=next; while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start]; } } ///Arc Conversion : g(gr), narc(g), visited(g, false) { if (start==INVALID) { NodeIt n(g); while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n; start=n; } if (start!=INVALID) { for (NodeIt n(g); n!=INVALID; ++n) narc[n]=OutArcIt(g,n); while(narc[start]!=INVALID) { euler.push_back(narc[start]); visited[narc[start]]=true; Node next=g.target(narc[start]); ++narc[start]; start=next; while(narc[start]!=INVALID && visited[narc[start]]) ++narc[start]; } } } ///Arc conversion operator Arc() const { return euler.empty()?INVALID:euler.front(); } ///Arc Conversion ///Edge conversion operator Edge() const { return euler.empty()?INVALID:euler.front(); } ///\e ///Compare with \c INVALID bool operator==(Invalid) const { return euler.empty(); } ///\e ///Compare with \c INVALID bool operator!=(Invalid) const { return !euler.empty(); } ///Next arc of the tour ///Next arc of the tour /// EulerIt &operator++() { Node s=g.target(euler.front()); euler.pop_front(); typename std::list::iterator next=euler.begin(); while(nedge[s]!=INVALID) { while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s]; if(nedge[s]==INVALID) break; while(narc[s]!=INVALID) { while(narc[s]!=INVALID && visited[narc[s]]) ++narc[s]; if(narc[s]==INVALID) break; else { euler.insert(next,nedge[s]); visited[nedge[s]]=true; Node n=g.target(nedge[s]); ++nedge[s]; euler.insert(next,narc[s]); visited[narc[s]]=true; Node n=g.target(narc[s]); ++narc[s]; s=n; } ///Postfix incrementation ///\warning This incrementation ///returns an \c Arc, not an \ref EulerIt, as one may ///expect. /// Postfix incrementation. /// ///\warning This incrementation returns an \c Arc (which converts to ///an \c Edge), not an \ref EulerIt, as one may expect. Arc operator++(int) { ///Checks if the graph is Eulerian ///Check if the given graph is \e Eulerian /// \ingroup graph_properties ///Checks if the graph is Eulerian. It works for both directed and undirected ///graphs. ///\note By definition, a digraph is called \e Eulerian if ///and only if it is connected and the number of its incoming and outgoing ///This function checks if the given graph is \e Eulerian. ///It works for both directed and undirected graphs. /// ///By definition, a digraph is called \e Eulerian if ///and only if it is connected and the number of incoming and outgoing ///arcs are the same for each node. ///Similarly, an undirected graph is called \e Eulerian if ///and only if it is connected and the number of incident arcs is even ///for each node. Therefore, there are digraphs which are not Eulerian, ///but still have an Euler tour. ///and only if it is connected and the number of incident edges is even ///for each node. /// ///\note There are (di)graphs that are not Eulerian, but still have an /// Euler tour, since they may contain isolated nodes. /// ///\sa DiEulerIt, EulerIt template #ifdef DOXYGEN for(typename GR::NodeIt n(g);n!=INVALID;++n) if(countInArcs(g,n)!=countOutArcs(g,n)) return false; return connected(Undirector(g)); return connected(undirector(g)); }
• ## test/CMakeLists.txt

 r596 kruskal_test maps_test max_matching_test matching_test min_cost_arborescence_test path_test
• ## test/Makefile.am

 r611 test/kruskal_test \ test/maps_test \ test/max_matching_test \ test/matching_test \ test/min_cost_arborescence_test \ test/path_test \ test_maps_test_SOURCES = test/maps_test.cc test_mip_test_SOURCES = test/mip_test.cc test_max_matching_test_SOURCES = test/max_matching_test.cc test_matching_test_SOURCES = test/matching_test.cc test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc test_path_test_SOURCES = test/path_test.cc