Changeset - r330:5ba887b7def4
« 327:91d63b
333:9c2a53 »
gravatar
alpar (Alpar Juttner)
alpar@cs.elte.hu
Doc improvements in lemon/max_matching.h
0 1 0
default
1 file changed with 35 insertions and 36 deletions:
lemon/max_matching.h
35
36
↑ Collapse diff ↑
lemon/max_matching.h
Show white space 2 line context
... ... 
@@ -41,7 +41,7 @@
41 41 
  ///
42 
  /// This class provides Edmonds' alternating forest matching
43 
  /// algorithm. The starting matching (if any) can be passed to the
44 
  /// algorithm using some of init functions.
42 
  /// This class implements Edmonds' alternating forest matching
43 
  /// algorithm. The algorithm can be started from an arbitrary initial
44 
  /// matching (the default is the empty one)
45 45 
  ///
46 
  /// The dual side of a matching is a map of the nodes to
46 
  /// The dual solution of the problem is a map of the nodes to
47 47 
  /// MaxMatching::Status, having values \c EVEN/D, \c ODD/A and \c
... ... 
@@ -51,5 +51,5 @@
51 51 
  /// barrier, and the nodes in \c MATCHED/C induce a graph having a
52 
  /// perfect matching. The number of the fractor critical components
52 
  /// perfect matching. The number of the factor-critical components
53 53 
  /// minus the number of barrier nodes is a lower bound on the
54 
  /// unmatched nodes, and if the matching is optimal this bound is
54 
  /// unmatched nodes, and the matching is optimal if and only if this bound is
55 55 
  /// tight. This decomposition can be attained by calling \c
... ... 
@@ -68,4 +68,3 @@
68 68 
    ///
69 
    ///Indicates the Gallai-Edmonds decomposition of the graph, which
70 
    ///shows an upper bound on the size of a maximum matching. The
69 
    ///Indicates the Gallai-Edmonds decomposition of the graph. The
71 70 
    ///nodes with Status \c EVEN/D induce a graph with factor-critical
... ... 
@@ -412,3 +411,3 @@
412 411 
    /// \name Execution control
413 
    /// The simplest way to execute the algorithm is to use the member
412 
    /// The simplest way to execute the algorithm is to use the
414 413 
    /// \c run() member function.
... ... 
@@ -416,5 +415,5 @@
416 415 

			




	417
	
	
		
    /// If you need more control on the execution, first you must call


			




	
	416
	
		
    /// If you need better control on the execution, you must call


			




	418
	417
	
		
    /// \ref init(), \ref greedyInit() or \ref matchingInit()


			




	419
	
	
		
    /// functions, then you can start the algorithm with the \ref


			




	
	418
	
		
    /// functions first, then you can start the algorithm with the \ref


			




	420
	419
	
		
    /// startParse() or startDense() functions.


			




	...
	...
	
		
@@ -435,5 +434,5 @@


			




	435
	434
	
		

			




	436
	
	
		
    ///\brief Finds a greedy matching for initial matching.


			




	
	435
	
		
    ///\brief Finds an initial matching in a greedy way


			




	437
	436
	
		
    ///


			




	438
	
	
		
    ///For initial matchig it finds a maximal greedy matching.


			




	
	437
	
		
    ///It finds an initial matching in a greedy way.


			




	439
	438
	
		
    void greedyInit() {


			




	...
	...
	
		
@@ -461,3 +460,3 @@


			




	461
	460
	
		

			




	462
	
	
		
    /// \brief Initialize the matching from the map containing a matching.


			




	
	461
	
		
    /// \brief Initialize the matching from a map containing.


			




	463
	462
	
		
    ///


			




	...
	...
	
		
@@ -509,3 +508,3 @@


			




	509
	508
	
		
    /// It runs Edmonds' algorithm with a heuristic of postponing


			




	510
	
	
		
    /// shrinks, giving a faster algorithm for dense graphs.


			




	
	509
	
		
    /// shrinks, therefore resulting in a faster algorithm for dense graphs.


			




	511
	510
	
		
    void startDense() {


			




	...
	...
	
		
@@ -540,3 +539,3 @@


			




	540
	539
	
		
    /// \name Primal solution


			




	541
	
	
		
    /// Functions for get the primal solution, ie. the matching.


			




	
	540
	
		
    /// Functions to get the primal solution, ie. the matching.


			




	542
	541
	
		

			




	...
	...
	
		
@@ -544,5 +543,5 @@


			




	544
	543
	
		

			




	545
	
	
		
    ///\brief Returns the size of the actual matching stored.


			




	
	544
	
		
    ///\brief Returns the size of the current matching.


			




	546
	545
	
		
    ///


			




	547
	
	
		
    ///Returns the size of the actual matching stored. After \ref


			




	
	546
	
		
    ///Returns the size of the current matching. After \ref


			




	548
	547
	
		
    ///run() it returns the size of the maximum matching in the graph.


			




	...
	...
	
		
@@ -585,3 +584,3 @@


			




	585
	584
	
		
    /// \name Dual solution


			




	586
	
	
		
    /// Functions for get the dual solution, ie. the decomposition.


			




	
	585
	
		
    /// Functions to get the dual solution, ie. the decomposition.


			




	587
	586
	
		

			




	...
	...
	
		
@@ -647,3 +646,3 @@


			




	647
	646
	
		
  /// blossomValue() members and \ref MaxWeightedMatching::BlossomIt


			




	648
	
	
		
  /// "BlossomIt" nested class which is able to iterate on the nodes


			




	
	647
	
		
  /// "BlossomIt" nested class, which is able to iterate on the nodes


			




	649
	648
	
		
  /// of a blossom. If the value type is integral then the dual


			




	...
	...
	
		
@@ -1632,3 +1631,3 @@


			




	1632
	1631
	
		
    /// \name Execution control


			




	1633
	
	
		
    /// The simplest way to execute the algorithm is to use the member


			




	
	1632
	
		
    /// The simplest way to execute the algorithm is to use the


			




	1634
	1633
	
		
    /// \c run() member function.


			




	...
	...
	
		
@@ -1793,3 +1792,3 @@


			




	1793
	1792
	
		
    /// \name Primal solution


			




	1794
	
	
		
    /// Functions for get the primal solution, ie. the matching.


			




	
	1793
	
		
    /// Functions to get the primal solution, ie. the matching.


			




	1795
	1794
	
		

			




	...
	...
	
		
@@ -1797,5 +1796,5 @@


			




	1797
	1796
	
		

			




	1798
	
	
		
    /// \brief Returns the matching value.


			




	
	1797
	
		
    /// \brief Returns the weight of the matching.


			




	1799
	1798
	
		
    ///


			




	1800
	
	
		
    /// Returns the matching value.


			




	
	1799
	
		
    /// Returns the weight of the matching.


			




	1801
	1800
	
		
    Value matchingValue() const {


			




	...
	...
	
		
@@ -1850,3 +1849,3 @@


			




	1850
	1849
	
		
    /// \name Dual solution


			




	1851
	
	
		
    /// Functions for get the dual solution.


			




	
	1850
	
		
    /// Functions to get the dual solution.


			




	1852
	1851
	
		

			




	...
	...
	
		
@@ -1900,6 +1899,6 @@


			




	1900
	1899
	
		

			




	1901
	
	
		
    /// \brief Lemon iterator for get the items of the blossom.


			




	
	1900
	
		
    /// \brief Iterator for obtaining the nodes of the blossom.


			




	1902
	1901
	
		
    ///


			




	1903
	
	
		
    /// Lemon iterator for get the nodes of the blossom. This class


			




	1904
	
	
		
    /// provides a common style lemon iterator which gives back a


			




	
	1902
	
		
    /// Iterator for obtaining the nodes of the blossom. This class


			




	
	1903
	
		
    /// provides a common lemon style iterator for listing a


			




	1905
	1904
	
		
    /// subset of the nodes.


			




	...
	...
	
		
@@ -1910,3 +1909,3 @@


			




	1910
	1909
	
		
      ///


			




	1911
	
	
		
      /// Constructor for get the nodes of the variable.


			




	
	1910
	
		
      /// Constructor to get the nodes of the variable.


			




	1912
	1911
	
		
      BlossomIt(const MaxWeightedMatching& algorithm, int variable)


			




	...
	...
	
		
@@ -2819,3 +2818,3 @@


			




	2819
	2818
	
		
    /// \name Execution control


			




	2820
	
	
		
    /// The simplest way to execute the algorithm is to use the member


			




	
	2819
	
		
    /// The simplest way to execute the algorithm is to use the


			




	2821
	2820
	
		
    /// \c run() member function.


			




	...
	...
	
		
@@ -2957,3 +2956,3 @@


			




	2957
	2956
	
		
    /// \name Primal solution


			




	2958
	
	
		
    /// Functions for get the primal solution, ie. the matching.


			




	
	2957
	
		
    /// Functions to get the primal solution, ie. the matching.


			




	2959
	2958
	
		

			




	...
	...
	
		
@@ -2998,3 +2997,3 @@


			




	2998
	2997
	
		
    /// \name Dual solution


			




	2999
	
	
		
    /// Functions for get the dual solution.


			




	
	2998
	
		
    /// Functions to get the dual solution.


			




	3000
	2999
	
		

			




	...
	...
	
		
@@ -3048,6 +3047,6 @@


			




	3048
	3047
	
		

			




	3049
	
	
		
    /// \brief Lemon iterator for get the items of the blossom.


			




	
	3048
	
		
    /// \brief Iterator for obtaining the nodes of the blossom.


			




	3050
	3049
	
		
    ///


			




	3051
	
	
		
    /// Lemon iterator for get the nodes of the blossom. This class


			




	3052
	
	
		
    /// provides a common style lemon iterator which gives back a


			




	
	3050
	
		
    /// Iterator for obtaining the nodes of the blossom. This class


			




	
	3051
	
		
    /// provides a common lemon style iterator for listing a


			




	3053
	3052
	
		
    /// subset of the nodes.


			




	...
	...
	
		
@@ -3058,3 +3057,3 @@


			




	3058
	3057
	
		
      ///


			




	3059
	
	
		
      /// Constructor for get the nodes of the variable.


			




	
	3058
	
		
      /// Constructor to get the nodes of the variable.


			




	3060
	3059
	
		
      BlossomIt(const MaxWeightedPerfectMatching& algorithm, int variable)


			




        

    






    
    



    


    

     
    
0 comments (0 inline)