lemon-0.x: comparison lemon/bipartite

equal deleted inserted replaced

-:431174367c0c
+:c662d76e072e
 /// \return The number of the matching edges.
 template <typename MatchingMap>
 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;
 }
 /// Set true all matching uedge in the map and the others to false.
 /// \return The number of the matching edges.
 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.
 ///
 /// It returns true if the given uedge is in the matching.
 bool matchingEdge(const UEdge& edge) const {
 queue.swap(newqueue);
 }
 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;
 }
 }
 return size;
 }
 queue.swap(newqueue);
 }
 for (ANodeIt it(*graph); it != INVALID; ++it) {
-barrier[it] = areached[it] || anode_matching[it] == INVALID;
+barrier.set(it, areached[it] || anode_matching[it] == INVALID);
 }
 }
 /// \brief Gives back a barrier on the B-nodes
 }
 queue.swap(newqueue);
 }
 for (BNodeIt it(*graph); it != INVALID; ++it) {
-barrier[it] = !breached[it];
+barrier.set(it, !breached[it]);
 }
 }
 /// @}
 /// 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 undirected edge map which will be set to
+/// \return The size of the matching.
-/// 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();
 }
 /// \brief Default traits class for weighted bipartite matching algoritms.
 ///
 /// 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]);
 }
 }
 /// \brief Set true all matching uedge in the map.
 ///
 /// \return The number of the matching edges.
 template <typename MatchingMap>
 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;
 }
 /// Set true all matching uedge in the map and the others to false.
 /// \return The number of the matching edges.
 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 Gives back the potential in the NodeMap
 ///
-/// Gives back the potential in the NodeMap. The potential is optimal with
+/// Gives back the potential in the NodeMap. The matching is optimal
-/// the current number of edges if \f$ \pi(a) - \pi(b) + w(ab) = 0 \f$ for
+/// with the current number of edges if \f$ \pi(a) + \pi(b) - w(ab) = 0 \f$
-/// each matching edges and \f$ \pi(a) - \pi(b) + w(ab) \ge 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]);
 }
 }
 /// \brief Set true all matching uedge in the map.
 ///
 /// \return The number of the matching edges.
 template <typename MatchingMap>
 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;
 }
 /// Set true all matching uedge in the map and the others to false.
 /// \return The number of the matching edges.
 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.
 ///
 /// It returns true if the given uedge is in the matching.
 bool matchingEdge(const UEdge& edge) const {
 /// \ingroup matching
 ///
 /// \brief Minimum cost maximum cardinality bipartite matching
 ///
-/// This function calculates the minimum cost matching of the maximum
+/// This function calculates the maximum cardinality matching with
-/// cardinality matchings of a bipartite graph. It gives back the matching
+/// minimum cost of a bipartite graph. It gives back the matching in
-/// in an undirected edge map.
+/// an undirected edge map.
 ///
 /// \param graph The bipartite graph.
 /// \param cost The undirected edge map which contains the costs.
 /// \retval matching The undirected edge map which will be set to
 /// the matching.

changeset 2465	df09310da558
parent 2462	7a096a6bf53a
child 2466	feb7974cf4ec