# HG changeset patch
# User deba
# Date 1187702541 0
# Node ID 19651a04d056aa342b9ef0c976b209d9d8b2eb04
# Parent 7a096a6bf53ad27fdfa447f4988ec78ee3f3866c
Query functions: aMatching and bMatching
Modified algorithm function interfaces
ANodeMap<UEdge> matching map
BNodeMap<bool> barrier map
Consistency between augmenting path and push-relabel algorithm
diff -r 7a096a6bf53a -r 19651a04d056 lemon/bipartite_matching.h
--- a/lemon/bipartite_matching.h Sat Aug 11 16:34:41 2007 +0000
+++ b/lemon/bipartite_matching.h Tue Aug 21 13:22:21 2007 +0000
@@ -359,7 +359,7 @@
int quickMatching(MatchingMap& mm) const {
for (ANodeIt it(*graph); it != INVALID; ++it) {
if (anode_matching[it] != INVALID) {
- mm[anode_matching[it]] = true;
+ mm.set(anode_matching[it], true);
}
}
return matching_size;
@@ -372,11 +372,36 @@
template <typename MatchingMap>
int matching(MatchingMap& mm) const {
for (UEdgeIt it(*graph); it != INVALID; ++it) {
- mm[it] = it == anode_matching[graph->aNode(it)];
+ mm.set(it, it == anode_matching[graph->aNode(it)]);
}
return matching_size;
}
+ ///Gives back the matching in an ANodeMap.
+
+ ///Gives back the matching in an ANodeMap. The parameter should
+ ///be a write ANodeMap of UEdge values.
+ ///\return The number of the matching edges.
+ template<class MatchingMap>
+ int aMatching(MatchingMap& mm) const {
+ for (ANodeIt it(*graph); it != INVALID; ++it) {
+ mm.set(it, anode_matching[it]);
+ }
+ return matching_size;
+ }
+
+ ///Gives back the matching in a BNodeMap.
+
+ ///Gives back the matching in a BNodeMap. The parameter should
+ ///be a write BNodeMap of UEdge values.
+ ///\return The number of the matching edges.
+ template<class MatchingMap>
+ int bMatching(MatchingMap& mm) const {
+ for (BNodeIt it(*graph); it != INVALID; ++it) {
+ mm.set(it, bnode_matching[it]);
+ }
+ return matching_size;
+ }
/// \brief Return true if the given uedge is in the matching.
///
@@ -445,13 +470,13 @@
int size = 0;
for (ANodeIt it(*graph); it != INVALID; ++it) {
- covering[it] = !areached[it] && anode_matching[it] != INVALID;
+ covering.set(it, !areached[it] && anode_matching[it] != INVALID);
if (!areached[it] && anode_matching[it] != INVALID) {
++size;
}
}
for (BNodeIt it(*graph); it != INVALID; ++it) {
- covering[it] = breached[it];
+ covering.set(it, breached[it]);
if (breached[it]) {
++size;
}
@@ -499,7 +524,7 @@
}
for (ANodeIt it(*graph); it != INVALID; ++it) {
- barrier[it] = areached[it] || anode_matching[it] == INVALID;
+ barrier.set(it, areached[it] || anode_matching[it] == INVALID);
}
}
@@ -543,7 +568,7 @@
}
for (BNodeIt it(*graph); it != INVALID; ++it) {
- barrier[it] = !breached[it];
+ barrier.set(it, !breached[it]);
}
}
@@ -568,14 +593,55 @@
/// edge map.
///
/// \param graph The bipartite graph.
- /// \retval matching The undirected edge map which will be set to
- /// the matching.
+ /// \return The size of the matching.
+ template <typename BpUGraph>
+ int maxBipartiteMatching(const BpUGraph& graph) {
+ MaxBipartiteMatching<BpUGraph> bpmatching(graph);
+ bpmatching.run();
+ return bpmatching.matchingSize();
+ }
+
+ /// \ingroup matching
+ ///
+ /// \brief Maximum cardinality bipartite matching
+ ///
+ /// This function calculates the maximum cardinality matching
+ /// in a bipartite graph. It gives back the matching in an undirected
+ /// edge map.
+ ///
+ /// \param graph The bipartite graph.
+ /// \retval matching The ANodeMap of UEdges which will be set to covered
+ /// matching undirected edge.
/// \return The size of the matching.
template <typename BpUGraph, typename MatchingMap>
int maxBipartiteMatching(const BpUGraph& graph, MatchingMap& matching) {
MaxBipartiteMatching<BpUGraph> bpmatching(graph);
bpmatching.run();
- bpmatching.matching(matching);
+ bpmatching.aMatching(matching);
+ return bpmatching.matchingSize();
+ }
+
+ /// \ingroup matching
+ ///
+ /// \brief Maximum cardinality bipartite matching
+ ///
+ /// This function calculates the maximum cardinality matching
+ /// in a bipartite graph. It gives back the matching in an undirected
+ /// edge map.
+ ///
+ /// \param graph The bipartite graph.
+ /// \retval matching The ANodeMap of UEdges which will be set to covered
+ /// matching undirected edge.
+ /// \retval barrier The BNodeMap of bools which will be set to a barrier
+ /// of the BNode-set.
+ /// \return The size of the matching.
+ template <typename BpUGraph, typename MatchingMap, typename BarrierMap>
+ int maxBipartiteMatching(const BpUGraph& graph,
+ MatchingMap& matching, BarrierMap& barrier) {
+ MaxBipartiteMatching<BpUGraph> bpmatching(graph);
+ bpmatching.run();
+ bpmatching.aMatching(matching);
+ bpmatching.bBarrier(barrier);
return bpmatching.matchingSize();
}
@@ -987,10 +1053,10 @@
template <typename PotentialMap>
void potential(PotentialMap& pt) const {
for (ANodeIt it(*graph); it != INVALID; ++it) {
- pt[it] = anode_potential[it];
+ pt.set(it, anode_potential[it]);
}
for (BNodeIt it(*graph); it != INVALID; ++it) {
- pt[it] = bnode_potential[it];
+ pt.set(it, bnode_potential[it]);
}
}
@@ -1003,7 +1069,7 @@
int quickMatching(MatchingMap& mm) const {
for (ANodeIt it(*graph); it != INVALID; ++it) {
if (anode_matching[it] != INVALID) {
- mm[anode_matching[it]] = true;
+ mm.set(anode_matching[it], true);
}
}
return matching_size;
@@ -1016,7 +1082,33 @@
template <typename MatchingMap>
int matching(MatchingMap& mm) const {
for (UEdgeIt it(*graph); it != INVALID; ++it) {
- mm[it] = it == anode_matching[graph->aNode(it)];
+ mm.set(it, it == anode_matching[graph->aNode(it)]);
+ }
+ return matching_size;
+ }
+
+ ///Gives back the matching in an ANodeMap.
+
+ ///Gives back the matching in an ANodeMap. The parameter should
+ ///be a write ANodeMap of UEdge values.
+ ///\return The number of the matching edges.
+ template<class MatchingMap>
+ int aMatching(MatchingMap& mm) const {
+ for (ANodeIt it(*graph); it != INVALID; ++it) {
+ mm.set(it, anode_matching[it]);
+ }
+ return matching_size;
+ }
+
+ ///Gives back the matching in a BNodeMap.
+
+ ///Gives back the matching in a BNodeMap. The parameter should
+ ///be a write BNodeMap of UEdge values.
+ ///\return The number of the matching edges.
+ template<class MatchingMap>
+ int bMatching(MatchingMap& mm) const {
+ for (BNodeIt it(*graph); it != INVALID; ++it) {
+ mm.set(it, bnode_matching[it]);
}
return matching_size;
}
@@ -1533,17 +1625,17 @@
/// \brief Gives back the potential in the NodeMap
///
- /// Gives back the potential in the NodeMap. The potential is optimal with
- /// the current number of edges if \f$ \pi(a) - \pi(b) + w(ab) = 0 \f$ for
- /// each matching edges and \f$ \pi(a) - \pi(b) + w(ab) \ge 0 \f$
- /// for each edges.
+ /// Gives back the potential in the NodeMap. The matching is optimal
+ /// with the current number of edges if \f$ \pi(a) + \pi(b) - w(ab) = 0 \f$
+ /// for each matching edges and \f$ \pi(a) + \pi(b) - w(ab) \ge 0 \f$
+ /// for each edges.
template <typename PotentialMap>
void potential(PotentialMap& pt) const {
for (ANodeIt it(*graph); it != INVALID; ++it) {
- pt[it] = anode_potential[it];
+ pt.set(it, anode_potential[it]);
}
for (BNodeIt it(*graph); it != INVALID; ++it) {
- pt[it] = bnode_potential[it];
+ pt.set(it, bnode_potential[it]);
}
}
@@ -1556,7 +1648,7 @@
int quickMatching(MatchingMap& mm) const {
for (ANodeIt it(*graph); it != INVALID; ++it) {
if (anode_matching[it] != INVALID) {
- mm[anode_matching[it]] = true;
+ mm.set(anode_matching[it], true);
}
}
return matching_size;
@@ -1569,11 +1661,36 @@
template <typename MatchingMap>
int matching(MatchingMap& mm) const {
for (UEdgeIt it(*graph); it != INVALID; ++it) {
- mm[it] = it == anode_matching[graph->aNode(it)];
+ mm.set(it, it == anode_matching[graph->aNode(it)]);
}
return matching_size;
}
+ /// \brief Gives back the matching in an ANodeMap.
+ ///
+ /// Gives back the matching in an ANodeMap. The parameter should
+ /// be a write ANodeMap of UEdge values.
+ /// \return The number of the matching edges.
+ template<class MatchingMap>
+ int aMatching(MatchingMap& mm) const {
+ for (ANodeIt it(*graph); it != INVALID; ++it) {
+ mm.set(it, anode_matching[it]);
+ }
+ return matching_size;
+ }
+
+ /// \brief Gives back the matching in a BNodeMap.
+ ///
+ /// Gives back the matching in a BNodeMap. The parameter should
+ /// be a write BNodeMap of UEdge values.
+ /// \return The number of the matching edges.
+ template<class MatchingMap>
+ int bMatching(MatchingMap& mm) const {
+ for (BNodeIt it(*graph); it != INVALID; ++it) {
+ mm.set(it, bnode_matching[it]);
+ }
+ return matching_size;
+ }
/// \brief Return true if the given uedge is in the matching.
///
@@ -1655,9 +1772,9 @@
///
/// \brief Minimum cost maximum cardinality bipartite matching
///
- /// This function calculates the minimum cost matching of the maximum
- /// cardinality matchings of a bipartite graph. It gives back the matching
- /// in an undirected edge map.
+ /// This function calculates the maximum cardinality matching with
+ /// minimum cost of a bipartite graph. It gives back the matching in
+ /// an undirected edge map.
///
/// \param graph The bipartite graph.
/// \param cost The undirected edge map which contains the costs.
diff -r 7a096a6bf53a -r 19651a04d056 lemon/pr_bipartite_matching.h
--- a/lemon/pr_bipartite_matching.h Sat Aug 11 16:34:41 2007 +0000
+++ b/lemon/pr_bipartite_matching.h Tue Aug 21 13:22:21 2007 +0000
@@ -315,11 +315,11 @@
/// either run() or start() must be called.
///@{
- /// \brief Set true all matching uedge in the map.
- ///
- /// Set true all matching uedge in the map. It does not change the
- /// value mapped to the other uedges.
- /// \return The number of the matching edges.
+ ///Set true all matching uedge in the map.
+
+ ///Set true all matching uedge in the map. It does not change the
+ ///value mapped to the other uedges.
+ ///\return The number of the matching edges.
template <typename MatchingMap>
int quickMatching(MatchingMap& mm) const {
for (ANodeIt n(_g);n!=INVALID;++n) {
@@ -328,7 +328,7 @@
return _matching_size;
}
- ///\brief Set true all matching uedge in the map and the others to false.
+ ///Set true all matching uedge in the map and the others to false.
///Set true all matching uedge in the map and the others to false.
///\return The number of the matching edges.
@@ -340,6 +340,36 @@
return _matching_size;
}
+ ///Gives back the matching in an ANodeMap.
+
+ ///Gives back the matching in an ANodeMap. The parameter should
+ ///be a write ANodeMap of UEdge values.
+ ///\return The number of the matching edges.
+ template<class MatchingMap>
+ int aMatching(MatchingMap& mm) const {
+ for (ANodeIt n(_g);n!=INVALID;++n) {
+ mm.set(n,_matching[n]);
+ }
+ return _matching_size;
+ }
+
+ ///Gives back the matching in a BNodeMap.
+
+ ///Gives back the matching in a BNodeMap. The parameter should
+ ///be a write BNodeMap of UEdge values.
+ ///\return The number of the matching edges.
+ template<class MatchingMap>
+ int bMatching(MatchingMap& mm) const {
+ for (BNodeIt n(_g);n!=INVALID;++n) {
+ mm.set(n,INVALID);
+ }
+ for (ANodeIt n(_g);n!=INVALID;++n) {
+ if (_matching[n]!=INVALID)
+ mm.set(_g.bNode(_matching[n]),_matching[n]);
+ }
+ return _matching_size;
+ }
+
///Returns true if the given uedge is in the matching.
@@ -457,8 +487,10 @@
///This function finds a maximum cardinality matching
///in a bipartite graph \c g.
///\param g An undirected bipartite graph.
- ///\retval matching A write UEdgeMap of value type \c bool.
- /// The found edges will be returned in this map.
+ ///\retval matching A write ANodeMap of value type \c UEdge.
+ /// The found edges will be returned in this map,
+ /// i.e. for an \c ANode \c n the edge <tt>matching[n]</tt> is the one
+ /// that covers the node \c n.
///\return The cardinality of the maximum matching.
///
///\note The the implementation is based
@@ -468,7 +500,7 @@
{
PrBipartiteMatching<Graph> bpm(g);
bpm.run();
- bpm.matching(matching);
+ bpm.aMatching(matching);
return bpm.matchingSize();
}
@@ -478,8 +510,10 @@
///This function finds a maximum cardinality matching
///in a bipartite graph \c g.
///\param g An undirected bipartite graph.
- ///\retval matching A write UEdgeMap of value type \c bool.
- /// The found edges will be returned in this map.
+ ///\retval matching A write ANodeMap of value type \c UEdge.
+ /// The found edges will be returned in this map,
+ /// i.e. for an \c ANode \c n the edge <tt>matching[n]</tt> is the one
+ /// that covers the node \c n.
///\retval barrier A \c bool WriteMap on the BNodes. The map will be set
/// exactly once for each BNode. The nodes with \c true value represent
/// a barrier \e B, i.e. the cardinality of \e B minus the number of its
@@ -494,7 +528,7 @@
{
PrBipartiteMatching<Graph> bpm(g);
bpm.run();
- bpm.matching(matching);
+ bpm.aMatching(matching);
bpm.bBarrier(barrier);
return bpm.matchingSize();
}
@@ -521,8 +555,10 @@
///\ingroup matching
///This function finds a perfect matching in a bipartite graph \c g.
///\param g An undirected bipartite graph.
- ///\retval matching A write UEdgeMap of value type \c bool.
- /// The found edges will be returned in this map.
+ ///\retval matching A write ANodeMap of value type \c UEdge.
+ /// The found edges will be returned in this map,
+ /// i.e. for an \c ANode \c n the edge <tt>matching[n]</tt> is the one
+ /// that covers the node \c n.
/// The values are unchanged if the graph
/// has no perfect matching.
///\return \c true iff \c g has a perfect matching.
@@ -533,8 +569,8 @@
bool prPerfectBipartiteMatching(const Graph &g,MT &matching)
{
PrBipartiteMatching<Graph> bpm(g);
- bool ret = bpm.runPerfect();
- if (ret) bpm.matching(matching);
+ bool ret = bpm.checkedRunPerfect();
+ if (ret) bpm.aMatching(matching);
return ret;
}
@@ -543,8 +579,10 @@
///\ingroup matching
///This function finds a perfect matching in a bipartite graph \c g.
///\param g An undirected bipartite graph.
- ///\retval matching A readwrite UEdgeMap of value type \c bool.
- /// The found edges will be returned in this map.
+ ///\retval matching A write ANodeMap of value type \c UEdge.
+ /// The found edges will be returned in this map,
+ /// i.e. for an \c ANode \c n the edge <tt>matching[n]</tt> is the one
+ /// that covers the node \c n.
/// The values are unchanged if the graph
/// has no perfect matching.
///\retval barrier A \c bool WriteMap on the BNodes. The map will only
@@ -557,12 +595,12 @@
///\note The the implementation is based
///on the push-relabel principle.
template<class Graph,class MT, class GT>
- int prPerfectBipartiteMatching(const Graph &g,MT &matching,GT &barrier)
+ bool prPerfectBipartiteMatching(const Graph &g,MT &matching,GT &barrier)
{
PrBipartiteMatching<Graph> bpm(g);
- bool ret=bpm.runPerfect();
+ bool ret=bpm.checkedRunPerfect();
if(ret)
- bpm.matching(matching);
+ bpm.aMatching(matching);
else
bpm.bBarrier(barrier);
return ret;
diff -r 7a096a6bf53a -r 19651a04d056 test/bipartite_matching_test.cc
--- a/test/bipartite_matching_test.cc Sat Aug 11 16:34:41 2007 +0000
+++ b/test/bipartite_matching_test.cc Tue Aug 21 13:22:21 2007 +0000
@@ -136,15 +136,32 @@
}
{
- Graph::UEdgeMap<bool> mm(graph);
+ Graph::ANodeMap<UEdge> mm(graph);
check(max_cardinality == maxBipartiteMatching(graph, mm),
"WRONG MATCHING");
- for (ANodeIt it(graph); it != INVALID; ++it) {
+ for (BNodeIt it(graph); it != INVALID; ++it) {
int num = 0;
+
for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
- if (mm[jt]) ++num;
+ if (mm[graph.aNode(jt)] == jt) ++num;
+ }
+ check(num <= 1, "INVALID PRIMAL");
+ }
+ }
+
+ {
+ Graph::ANodeMap<UEdge> mm(graph);
+
+ check(max_cardinality == prBipartiteMatching(graph, mm),
+ "WRONG MATCHING");
+
+ for (BNodeIt it(graph); it != INVALID; ++it) {
+ int num = 0;
+
+ for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
+ if (mm[graph.aNode(jt)] == jt) ++num;
}
check(num <= 1, "INVALID PRIMAL");
}