Changeset - r640:7ac52d6a268e
« 637:b61354
641:d657c7 »
gravatar
kpeter (Peter Kovacs)
kpeter@inf.elte.hu
Extend and modify the interface of matching algorithms (#265) - Rename decomposition() to status() in MaxMatching. - Add a new query function statusMap() to MaxMatching. - Add a new query function matchingMap() to all the three classes. - Rename matchingValue() to matchingWeight() in the weighted matching classes.
0 2 0
default
2 files changed with 70 insertions and 23 deletions:
lemon/max_matching.h
46
9
test/max_matching_test.cc
24
14
↑ Collapse diff ↑
lemon/max_matching.h
Show white space 6 line context
... ... 
@@ -42,3 +42,3 @@
42 42 
  /// This class implements Edmonds' alternating forest matching algorithm
43 
  /// for finding a maximum cardinality matching in a general graph.
43 
  /// for finding a maximum cardinality matching in a general undirected graph.
44 44 
  /// It can be started from an arbitrary initial matching
... ... 
@@ -55,6 +55,6 @@
55 55 
  /// unmatched nodes, and the matching is optimal if and only if this bound is
56 
  /// tight. This decomposition can be obtained by calling \c
57 
  /// decomposition() after running the algorithm.
56 
  /// tight. This decomposition can be obtained using \ref status() or
57 
  /// \ref statusMap() after running the algorithm.
58 58 
  ///
59 
  /// \tparam GR The graph type the algorithm runs on.
59 
  /// \tparam GR The undirected graph type the algorithm runs on.
60 60 
  template <typename GR>
... ... 
@@ -65,2 +65,3 @@
65 65 
    typedef GR Graph;
66 
    /// The type of the matching map
66 67 
    typedef typename Graph::template NodeMap<typename Graph::Arc>
... ... 
@@ -86,2 +87,3 @@
86 87 

			




	
	88
	
		
    /// The type of the status map


			




	87
	89
	
		
    typedef typename Graph::template NodeMap<Status> StatusMap;


			




	...
	...
	
		
@@ -585,2 +587,10 @@


			




	585
	587
	
		

			




	
	588
	
		
    /// \brief Return a const reference to the matching map.


			




	
	589
	
		
    ///


			




	
	590
	
		
    /// This function returns a const reference to a node map that stores


			




	
	591
	
		
    /// the matching arc (or edge) incident to each node.


			




	
	592
	
		
    const MatchingMap& matchingMap() const {


			




	
	593
	
		
      return *_matching;


			




	
	594
	
		
    }


			




	
	595
	
		

			




	586
	596
	
		
    /// \brief Return the mate of the given node.


			




	...
	...
	
		
@@ -607,3 +617,3 @@


			




	607
	617
	
		
    /// in the Edmonds-Gallai decomposition.


			




	608
	
	
		
    Status decomposition(const Node& n) const {


			




	
	618
	
		
    Status status(const Node& n) const {


			




	609
	619
	
		
      return (*_status)[n];


			




	...
	...
	
		
@@ -611,2 +621,11 @@


			




	611
	621
	
		

			




	
	622
	
		
    /// \brief Return a const reference to the status map, which stores


			




	
	623
	
		
    /// the Edmonds-Gallai decomposition.


			




	
	624
	
		
    ///


			




	
	625
	
		
    /// This function returns a const reference to a node map that stores the


			




	
	626
	
		
    /// \ref Status "status" of each node in the Edmonds-Gallai decomposition.


			




	
	627
	
		
    const StatusMap& statusMap() const {


			




	
	628
	
		
      return *_status;


			




	
	629
	
		
    }


			




	
	630
	
		

			




	612
	631
	
		
    /// \brief Return \c true if the given node is in the barrier.


			




	...
	...
	
		
@@ -664,3 +683,3 @@


			




	664
	683
	
		
  ///


			




	665
	
	
		
  /// \tparam GR The graph type the algorithm runs on.


			




	
	684
	
		
  /// \tparam GR The undirected graph type the algorithm runs on.


			




	666
	685
	
		
  /// \tparam WM The type edge weight map. The default type is 


			




	...
	...
	
		
@@ -683,2 +702,3 @@


			




	683
	702
	
		

			




	
	703
	
		
    /// The type of the matching map


			




	684
	704
	
		
    typedef typename Graph::template NodeMap<typename Graph::Arc>


			




	...
	...
	
		
@@ -1831,3 +1851,3 @@


			




	1831
	1851
	
		
    /// \pre Either run() or start() must be called before using this function.


			




	1832
	
	
		
    Value matchingValue() const {


			




	
	1852
	
		
    Value matchingWeight() const {


			




	1833
	1853
	
		
      Value sum = 0;


			




	...
	...
	
		
@@ -1877,2 +1897,10 @@


			




	1877
	1897
	
		

			




	
	1898
	
		
    /// \brief Return a const reference to the matching map.


			




	
	1899
	
		
    ///


			




	
	1900
	
		
    /// This function returns a const reference to a node map that stores


			




	
	1901
	
		
    /// the matching arc (or edge) incident to each node.


			




	
	1902
	
		
    const MatchingMap& matchingMap() const {


			




	
	1903
	
		
      return *_matching;


			




	
	1904
	
		
    }


			




	
	1905
	
		

			




	1878
	1906
	
		
    /// \brief Return the mate of the given node.


			




	...
	...
	
		
@@ -2052,3 +2080,3 @@


			




	2052
	2080
	
		
  ///


			




	2053
	
	
		
  /// \tparam GR The graph type the algorithm runs on.


			




	
	2081
	
		
  /// \tparam GR The undirected graph type the algorithm runs on.


			




	2054
	2082
	
		
  /// \tparam WM The type edge weight map. The default type is 


			




	...
	...
	
		
@@ -2078,2 +2106,3 @@


			




	2078
	2106
	
		

			




	
	2107
	
		
    /// The type of the matching map


			




	2079
	2108
	
		
    typedef typename Graph::template NodeMap<typename Graph::Arc>


			




	...
	...
	
		
@@ -3040,3 +3069,3 @@


			




	3040
	3069
	
		
    /// \pre Either run() or start() must be called before using this function.


			




	3041
	
	
		
    Value matchingValue() const {


			




	
	3070
	
		
    Value matchingWeight() const {


			




	3042
	3071
	
		
      Value sum = 0;


			




	...
	...
	
		
@@ -3071,2 +3100,10 @@


			




	3071
	3100
	
		

			




	
	3101
	
		
    /// \brief Return a const reference to the matching map.


			




	
	3102
	
		
    ///


			




	
	3103
	
		
    /// This function returns a const reference to a node map that stores


			




	
	3104
	
		
    /// the matching arc (or edge) incident to each node.


			




	
	3105
	
		
    const MatchingMap& matchingMap() const {


			




	
	3106
	
		
      return *_matching;


			




	
	3107
	
		
    }


			




	
	3108
	
		

			




	3072
	3109
	
		
    /// \brief Return the mate of the given node.

			




        

    

    

    

        

            

                

                    test/max_matching_test.cc
                

                

                  
                  
                  
                  Ignore white space
                  6 line context
                

                
                  
                
            

        

        

            

            



	...
	...
	
		
@@ -140,2 +140,5 @@


			




	140
	140
	
		
  const_mat_test.matching(n);


			




	
	141
	
		
  const MaxMatching<Graph>::MatchingMap& mmap =


			




	
	142
	
		
    const_mat_test.matchingMap();


			




	
	143
	
		
  e = mmap[n];


			




	141
	144
	
		
  const_mat_test.mate(n);


			




	...
	...
	
		
@@ -143,6 +146,7 @@


			




	143
	146
	
		
  MaxMatching<Graph>::Status stat = 


			




	144
	
	
		
    const_mat_test.decomposition(n);


			




	
	147
	
		
    const_mat_test.status(n);


			




	
	148
	
		
  const MaxMatching<Graph>::StatusMap& smap =


			




	
	149
	
		
    const_mat_test.statusMap();


			




	
	150
	
		
  stat = smap[n];


			




	145
	151
	
		
  const_mat_test.barrier(n);


			




	146
	
	
		
  


			




	147
	
	
		
  ignore_unused_variable_warning(stat);


			




	148
	152
	
		
}


			




	...
	...
	
		
@@ -169,3 +173,3 @@


			




	169
	173
	
		
  


			




	170
	
	
		
  const_mat_test.matchingValue();


			




	
	174
	
		
  const_mat_test.matchingWeight();


			




	171
	175
	
		
  const_mat_test.matchingSize();


			




	...
	...
	
		
@@ -173,2 +177,5 @@


			




	173
	177
	
		
  const_mat_test.matching(n);


			




	
	178
	
		
  const MaxWeightedMatching<Graph>::MatchingMap& mmap =


			




	
	179
	
		
    const_mat_test.matchingMap();


			




	
	180
	
		
  e = mmap[n];


			




	174
	181
	
		
  const_mat_test.mate(n);


			




	...
	...
	
		
@@ -203,5 +210,8 @@


			




	203
	210
	
		
  


			




	204
	
	
		
  const_mat_test.matchingValue();


			




	
	211
	
		
  const_mat_test.matchingWeight();


			




	205
	212
	
		
  const_mat_test.matching(e);


			




	206
	213
	
		
  const_mat_test.matching(n);


			




	
	214
	
		
  const MaxWeightedPerfectMatching<Graph>::MatchingMap& mmap =


			




	
	215
	
		
    const_mat_test.matchingMap();


			




	
	216
	
		
  e = mmap[n];


			




	207
	217
	
		
  const_mat_test.mate(n);


			




	...
	...
	
		
@@ -226,5 +236,5 @@


			




	226
	236
	
		
  for (NodeIt n(graph); n != INVALID; ++n) {


			




	227
	
	
		
    check(mm.decomposition(n) == MaxMatching<SmartGraph>::EVEN ||


			




	
	237
	
		
    check(mm.status(n) == MaxMatching<SmartGraph>::EVEN ||


			




	228
	238
	
		
          mm.matching(n) != INVALID, "Wrong Gallai-Edmonds decomposition");


			




	229
	
	
		
    if (mm.decomposition(n) == MaxMatching<SmartGraph>::ODD) {


			




	
	239
	
		
    if (mm.status(n) == MaxMatching<SmartGraph>::ODD) {


			




	230
	240
	
		
      ++barrier_num;


			




	...
	...
	
		
@@ -241,12 +251,12 @@


			




	241
	251
	
		
    }


			




	242
	
	
		
    check(mm.decomposition(graph.u(e)) != MaxMatching<SmartGraph>::EVEN ||


			




	243
	
	
		
          mm.decomposition(graph.v(e)) != MaxMatching<SmartGraph>::MATCHED,


			




	
	252
	
		
    check(mm.status(graph.u(e)) != MaxMatching<SmartGraph>::EVEN ||


			




	
	253
	
		
          mm.status(graph.v(e)) != MaxMatching<SmartGraph>::MATCHED,


			




	244
	254
	
		
          "Wrong Gallai-Edmonds decomposition");


			




	245
	255
	
		

			




	246
	
	
		
    check(mm.decomposition(graph.v(e)) != MaxMatching<SmartGraph>::EVEN ||


			




	247
	
	
		
          mm.decomposition(graph.u(e)) != MaxMatching<SmartGraph>::MATCHED,


			




	
	256
	
		
    check(mm.status(graph.v(e)) != MaxMatching<SmartGraph>::EVEN ||


			




	
	257
	
		
          mm.status(graph.u(e)) != MaxMatching<SmartGraph>::MATCHED,


			




	248
	258
	
		
          "Wrong Gallai-Edmonds decomposition");


			




	249
	259
	
		

			




	250
	
	
		
    if (mm.decomposition(graph.u(e)) != MaxMatching<SmartGraph>::ODD &&


			




	251
	
	
		
        mm.decomposition(graph.v(e)) != MaxMatching<SmartGraph>::ODD) {


			




	
	260
	
		
    if (mm.status(graph.u(e)) != MaxMatching<SmartGraph>::ODD &&


			




	
	261
	
		
        mm.status(graph.v(e)) != MaxMatching<SmartGraph>::ODD) {


			




	252
	262
	
		
      comp.join(graph.u(e), graph.v(e));


			




	...
	...
	
		
@@ -258,3 +268,3 @@


			




	258
	268
	
		
  for (NodeIt n(graph); n != INVALID; ++n) {


			




	259
	
	
		
    if (mm.decomposition(n) != MaxMatching<SmartGraph>::ODD) {


			




	
	269
	
		
    if (mm.status(n) != MaxMatching<SmartGraph>::ODD) {


			




	260
	270
	
		
      int root = comp.find(n);


			




        

    






    
    



    


    

     
    
0 comments (0 inline)