lemon/fractional_matching.h
changeset 950 86613aa28a0c
parent 948 636dadefe1e6
child 951 41d7ac528c3a
equal deleted inserted replaced
0:1ec5754fa4c3 1:a3f5c5ba7a87
   109   /// The algorithm can be executed with the run() function.  After it
   109   /// The algorithm can be executed with the run() function.  After it
   110   /// the matching (the primal solution) and the barrier (the dual
   110   /// the matching (the primal solution) and the barrier (the dual
   111   /// solution) can be obtained using the query functions.
   111   /// solution) can be obtained using the query functions.
   112   ///
   112   ///
   113   /// The primal solution is multiplied by
   113   /// The primal solution is multiplied by
   114   /// \ref MaxWeightedMatching::primalScale "2".
   114   /// \ref MaxFractionalMatching::primalScale "2".
   115   ///
   115   ///
   116   /// \tparam GR The undirected graph type the algorithm runs on.
   116   /// \tparam GR The undirected graph type the algorithm runs on.
   117 #ifdef DOXYGEN
   117 #ifdef DOXYGEN
   118   template <typename GR, typename TR>
   118   template <typename GR, typename TR>
   119 #else
   119 #else
   630   /// \ingroup matching
   630   /// \ingroup matching
   631   ///
   631   ///
   632   /// \brief Weighted fractional matching in general graphs
   632   /// \brief Weighted fractional matching in general graphs
   633   ///
   633   ///
   634   /// This class provides an efficient implementation of fractional
   634   /// This class provides an efficient implementation of fractional
   635   /// matching algorithm. The implementation is based on extensive use
   635   /// matching algorithm. The implementation uses priority queues and
   636   /// of priority queues and provides \f$O(nm\log n)\f$ time
   636   /// provides \f$O(nm\log n)\f$ time complexity.
   637   /// complexity.
       
   638   ///
   637   ///
   639   /// The maximum weighted fractional matching is a relaxation of the
   638   /// The maximum weighted fractional matching is a relaxation of the
   640   /// maximum weighted matching problem where the odd set constraints
   639   /// maximum weighted matching problem where the odd set constraints
   641   /// are omitted.
   640   /// are omitted.
   642   /// It can be formulated with the following linear program.
   641   /// It can be formulated with the following linear program.
   651   /// proof of the optimality. The solution of the dual problem can be
   650   /// proof of the optimality. The solution of the dual problem can be
   652   /// used to check the result of the algorithm. The dual linear
   651   /// used to check the result of the algorithm. The dual linear
   653   /// problem is the following.
   652   /// problem is the following.
   654   /// \f[ y_u + y_v \ge w_{uv} \quad \forall uv\in E\f]
   653   /// \f[ y_u + y_v \ge w_{uv} \quad \forall uv\in E\f]
   655   /// \f[y_u \ge 0 \quad \forall u \in V\f]
   654   /// \f[y_u \ge 0 \quad \forall u \in V\f]
   656   /// \f[\min \sum_{u \in V}y_u \f] ///
   655   /// \f[\min \sum_{u \in V}y_u \f]
   657   ///
   656   ///
   658   /// The algorithm can be executed with the run() function.
   657   /// The algorithm can be executed with the run() function.
   659   /// After it the matching (the primal solution) and the dual solution
   658   /// After it the matching (the primal solution) and the dual solution
   660   /// can be obtained using the query functions.
   659   /// can be obtained using the query functions.
   661   ///
   660   ///
   662   /// If the value type is integer, then the primal and the dual
   661   /// If the value type is integer, then the primal and the dual
   663   /// solutions are multiplied by
   662   /// solutions are multiplied by
   664   /// \ref MaxWeightedMatching::primalScale "2" and
   663   /// \ref MaxWeightedFractionalMatching::primalScale "2" and
   665   /// \ref MaxWeightedMatching::dualScale "4" respectively.
   664   /// \ref MaxWeightedFractionalMatching::dualScale "4" respectively.
   666   ///
   665   ///
   667   /// \tparam GR The undirected graph type the algorithm runs on.
   666   /// \tparam GR The undirected graph type the algorithm runs on.
   668   /// \tparam WM The type edge weight map. The default type is
   667   /// \tparam WM The type edge weight map. The default type is
   669   /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
   668   /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
   670 #ifdef DOXYGEN
   669 #ifdef DOXYGEN
  1268       }
  1267       }
  1269     }
  1268     }
  1270 
  1269 
  1271     /// \brief Run the algorithm.
  1270     /// \brief Run the algorithm.
  1272     ///
  1271     ///
  1273     /// This method runs the \c %MaxWeightedMatching algorithm.
  1272     /// This method runs the \c %MaxWeightedFractionalMatching algorithm.
  1274     ///
  1273     ///
  1275     /// \note mwfm.run() is just a shortcut of the following code.
  1274     /// \note mwfm.run() is just a shortcut of the following code.
  1276     /// \code
  1275     /// \code
  1277     ///   mwfm.init();
  1276     ///   mwfm.init();
  1278     ///   mwfm.start();
  1277     ///   mwfm.start();
  1398   /// \ingroup matching
  1397   /// \ingroup matching
  1399   ///
  1398   ///
  1400   /// \brief Weighted fractional perfect matching in general graphs
  1399   /// \brief Weighted fractional perfect matching in general graphs
  1401   ///
  1400   ///
  1402   /// This class provides an efficient implementation of fractional
  1401   /// This class provides an efficient implementation of fractional
  1403   /// matching algorithm. The implementation is based on extensive use
  1402   /// matching algorithm. The implementation uses priority queues and
  1404   /// of priority queues and provides \f$O(nm\log n)\f$ time
  1403   /// provides \f$O(nm\log n)\f$ time complexity.
  1405   /// complexity.
       
  1406   ///
  1404   ///
  1407   /// The maximum weighted fractional perfect matching is a relaxation
  1405   /// The maximum weighted fractional perfect matching is a relaxation
  1408   /// of the maximum weighted perfect matching problem where the odd
  1406   /// of the maximum weighted perfect matching problem where the odd
  1409   /// set constraints are omitted.
  1407   /// set constraints are omitted.
  1410   /// It can be formulated with the following linear program.
  1408   /// It can be formulated with the following linear program.
  1418   /// The algorithm calculates an optimal fractional matching and a
  1416   /// The algorithm calculates an optimal fractional matching and a
  1419   /// proof of the optimality. The solution of the dual problem can be
  1417   /// proof of the optimality. The solution of the dual problem can be
  1420   /// used to check the result of the algorithm. The dual linear
  1418   /// used to check the result of the algorithm. The dual linear
  1421   /// problem is the following.
  1419   /// problem is the following.
  1422   /// \f[ y_u + y_v \ge w_{uv} \quad \forall uv\in E\f]
  1420   /// \f[ y_u + y_v \ge w_{uv} \quad \forall uv\in E\f]
  1423   /// \f[\min \sum_{u \in V}y_u \f] ///
  1421   /// \f[\min \sum_{u \in V}y_u \f]
  1424   ///
  1422   ///
  1425   /// The algorithm can be executed with the run() function.
  1423   /// The algorithm can be executed with the run() function.
  1426   /// After it the matching (the primal solution) and the dual solution
  1424   /// After it the matching (the primal solution) and the dual solution
  1427   /// can be obtained using the query functions.
  1425   /// can be obtained using the query functions.
  1428 
  1426 
  1429   /// If the value type is integer, then the primal and the dual
  1427   /// If the value type is integer, then the primal and the dual
  1430   /// solutions are multiplied by
  1428   /// solutions are multiplied by
  1431   /// \ref MaxWeightedMatching::primalScale "2" and
  1429   /// \ref MaxWeightedPerfectFractionalMatching::primalScale "2" and
  1432   /// \ref MaxWeightedMatching::dualScale "4" respectively.
  1430   /// \ref MaxWeightedPerfectFractionalMatching::dualScale "4" respectively.
  1433   ///
  1431   ///
  1434   /// \tparam GR The undirected graph type the algorithm runs on.
  1432   /// \tparam GR The undirected graph type the algorithm runs on.
  1435   /// \tparam WM The type edge weight map. The default type is
  1433   /// \tparam WM The type edge weight map. The default type is
  1436   /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
  1434   /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
  1437 #ifdef DOXYGEN
  1435 #ifdef DOXYGEN
  2003       return true;
  2001       return true;
  2004     }
  2002     }
  2005 
  2003 
  2006     /// \brief Run the algorithm.
  2004     /// \brief Run the algorithm.
  2007     ///
  2005     ///
  2008     /// This method runs the \c %MaxWeightedMatching algorithm.
  2006     /// This method runs the \c %MaxWeightedPerfectFractionalMatching 
       
  2007     /// algorithm.
  2009     ///
  2008     ///
  2010     /// \note mwfm.run() is just a shortcut of the following code.
  2009     /// \note mwfm.run() is just a shortcut of the following code.
  2011     /// \code
  2010     /// \code
  2012     ///   mwpfm.init();
  2011     ///   mwpfm.init();
  2013     ///   mwpfm.start();
  2012     ///   mwpfm.start();