lemon: comparison lemon/max

equal deleted inserted replaced

-:d5f4d84089ff
+:1ebc4b0acb38
 /// \ingroup matching
 ///
 /// \brief Maximum cardinality matching in general graphs
 ///
 /// This class implements Edmonds' alternating forest matching algorithm
-/// for finding a maximum cardinality matching in a general graph.
+/// for finding a maximum cardinality matching in a general undirected graph.
 /// It can be started from an arbitrary initial matching
 /// (the default is the empty one).
 ///
 /// The dual solution of the problem is a map of the nodes to
 /// \ref MaxMatching::Status "Status", having values \c EVEN (or \c D),
 /// with factor-critical components, the nodes in \c ODD/A form the
 /// canonical barrier, and the nodes in \c MATCHED/C induce a graph having
 /// a perfect matching. The number of the factor-critical components
 /// minus the number of barrier nodes is a lower bound on the
 /// unmatched nodes, and the matching is optimal if and only if this bound is
-/// tight. This decomposition can be obtained by calling \c
+/// tight. This decomposition can be obtained using \ref status() or
-/// decomposition() after running the algorithm.
+/// \ref statusMap() after running the algorithm.
 ///
-/// \tparam GR The graph type the algorithm runs on.
+/// \tparam GR The undirected graph type the algorithm runs on.
 template <typename GR>
 class MaxMatching {
 public:
 /// The graph type of the algorithm
 typedef GR Graph;
+/// The type of the matching map
 typedef typename Graph::template NodeMap<typename Graph::Arc>
 MatchingMap;
 ///\brief Status constants for Gallai-Edmonds decomposition.
 ///
 ODD = -1,       ///< = -1. (\c A is an alias for \c ODD.)
 A = -1,
 UNMATCHED = -2  ///< = -2.
 };
+/// The type of the status map
 typedef typename Graph::template NodeMap<Status> StatusMap;
 private:
 TEMPLATE_GRAPH_TYPEDEFS(Graph);
 /// not covered by the matching.
 Arc matching(const Node& n) const {
 return (*_matching)[n];
 }
+/// \brief Return a const reference to the matching map.
+///
+/// This function returns a const reference to a node map that stores
+/// the matching arc (or edge) incident to each node.
+const MatchingMap& matchingMap() const {
+return *_matching;
+}
 /// \brief Return the mate of the given node.
 ///
 /// This function returns the mate of the given node in the current
 /// matching or \c INVALID if the node is not covered by the matching.
 Node mate(const Node& n) const {
 /// \brief Return the status of the given node in the Edmonds-Gallai
 /// decomposition.
 ///
 /// This function returns the \ref Status "status" of the given node
 /// in the Edmonds-Gallai decomposition.
-Status decomposition(const Node& n) const {
+Status status(const Node& n) const {
 return (*_status)[n];
+}
+/// \brief Return a const reference to the status map, which stores
+/// the Edmonds-Gallai decomposition.
+///
+/// This function returns a const reference to a node map that stores the
+/// \ref Status "status" of each node in the Edmonds-Gallai decomposition.
+const StatusMap& statusMap() const {
+return *_status;
 }
 /// \brief Return \c true if the given node is in the barrier.
 ///
 /// This function returns \c true if the given node is in the barrier.
 /// \ref MaxWeightedMatching::BlossomIt "BlossomIt" nested class,
 /// which is able to iterate on the nodes of a blossom.
 /// If the value type is integer, then the dual solution is multiplied
 /// by \ref MaxWeightedMatching::dualScale "4".
 ///
-/// \tparam GR The graph type the algorithm runs on.
+/// \tparam GR The undirected graph type the algorithm runs on.
 /// \tparam WM The type edge weight map. The default type is
 /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
 #ifdef DOXYGEN
 template <typename GR, typename WM>
 #else
 /// The type of the edge weight map
 typedef WM WeightMap;
 /// The value type of the edge weights
 typedef typename WeightMap::Value Value;
+/// The type of the matching map
 typedef typename Graph::template NodeMap<typename Graph::Arc>
 MatchingMap;
 /// \brief Scaling factor for dual solution
 ///
 /// \brief Return the weight of the matching.
 ///
 /// This function returns the weight of the found matching.
 ///
 /// \pre Either run() or start() must be called before using this function.
-Value matchingValue() const {
+Value matchingWeight() const {
 Value sum = 0;
 for (NodeIt n(_graph); n != INVALID; ++n) {
 if ((*_matching)[n] != INVALID) {
 sum += _weight[(*_matching)[n]];
 }
 /// not covered by the matching.
 ///
 /// \pre Either run() or start() must be called before using this function.
 Arc matching(const Node& node) const {
 return (*_matching)[node];
+}
+/// \brief Return a const reference to the matching map.
+///
+/// This function returns a const reference to a node map that stores
+/// the matching arc (or edge) incident to each node.
+const MatchingMap& matchingMap() const {
+return *_matching;
 }
 /// \brief Return the mate of the given node.
 ///
 /// This function returns the mate of the given node in the found
 /// \ref MaxWeightedPerfectMatching::BlossomIt "BlossomIt" nested class,
 /// which is able to iterate on the nodes of a blossom.
 /// If the value type is integer, then the dual solution is multiplied
 /// by \ref MaxWeightedMatching::dualScale "4".
 ///
-/// \tparam GR The graph type the algorithm runs on.
+/// \tparam GR The undirected graph type the algorithm runs on.
 /// \tparam WM The type edge weight map. The default type is
 /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
 #ifdef DOXYGEN
 template <typename GR, typename WM>
 #else
 /// Scaling factor for dual solution, it is equal to 4 or 1
 /// according to the value type.
 static const int dualScale =
 std::numeric_limits<Value>::is_integer ? 4 : 1;
+/// The type of the matching map
 typedef typename Graph::template NodeMap<typename Graph::Arc>
 MatchingMap;
 private:
 /// \brief Return the weight of the matching.
 ///
 /// This function returns the weight of the found matching.
 ///
 /// \pre Either run() or start() must be called before using this function.
-Value matchingValue() const {
+Value matchingWeight() const {
 Value sum = 0;
 for (NodeIt n(_graph); n != INVALID; ++n) {
 if ((*_matching)[n] != INVALID) {
 sum += _weight[(*_matching)[n]];
 }
 /// not covered by the matching.
 ///
 /// \pre Either run() or start() must be called before using this function.
 Arc matching(const Node& node) const {
 return (*_matching)[node];
+}
+/// \brief Return a const reference to the matching map.
+///
+/// This function returns a const reference to a node map that stores
+/// the matching arc (or edge) incident to each node.
+const MatchingMap& matchingMap() const {
+return *_matching;
 }
 /// \brief Return the mate of the given node.
 ///
 /// This function returns the mate of the given node in the found

changeset 640	7ac52d6a268e
parent 637	b61354458b59