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
Ignore white space 4 line context
... ... 
@@ -41,5 +41,5 @@
41 41 
  ///
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
45 45 
  /// (the default is the empty one).
... ... 
@@ -54,8 +54,8 @@
54 54 
  /// minus the number of barrier nodes is a lower bound on the
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>
61 61 
  class MaxMatching {
... ... 
@@ -64,4 +64,5 @@
64 64 
    /// The graph type of the algorithm
65 65 
    typedef GR Graph;
66 
    /// The type of the matching map
66 67 
    typedef typename Graph::template NodeMap<typename Graph::Arc>
67 68 
    MatchingMap;
... ... 
@@ -85,4 +86,5 @@
85 86 
    };
86 87 

			




	
	88
	
		
    /// The type of the status map


			




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


			




	88
	90
	
		

			




	...
	...
	
		
@@ -584,4 +586,12 @@


			




	584
	586
	
		
    }


			




	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.


			




	587
	597
	
		
    ///


			




	...
	...
	
		
@@ -606,8 +616,17 @@


			




	606
	616
	
		
    /// This function returns the \ref Status "status" of the given node


			




	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];


			




	610
	620
	
		
    }


			




	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.


			




	613
	632
	
		
    ///


			




	...
	...
	
		
@@ -663,5 +682,5 @@


			




	663
	682
	
		
  /// by \ref MaxWeightedMatching::dualScale "4".


			




	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 


			




	667
	686
	
		
  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".


			




	...
	...
	
		
@@ -682,4 +701,5 @@


			




	682
	701
	
		
    typedef typename WeightMap::Value Value;


			




	683
	702
	
		

			




	
	703
	
		
    /// The type of the matching map


			




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


			




	685
	705
	
		
    MatchingMap;


			




	...
	...
	
		
@@ -1830,5 +1850,5 @@


			




	1830
	1850
	
		
    ///


			




	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;


			




	1834
	1854
	
		
      for (NodeIt n(_graph); n != INVALID; ++n) {


			




	...
	...
	
		
@@ -1876,4 +1896,12 @@


			




	1876
	1896
	
		
    }


			




	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.


			




	1879
	1907
	
		
    ///


			




	...
	...
	
		
@@ -2051,5 +2079,5 @@


			




	2051
	2079
	
		
  /// by \ref MaxWeightedMatching::dualScale "4".


			




	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 


			




	2055
	2083
	
		
  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".


			




	...
	...
	
		
@@ -2077,4 +2105,5 @@


			




	2077
	2105
	
		
      std::numeric_limits<Value>::is_integer ? 4 : 1;


			




	2078
	2106
	
		

			




	
	2107
	
		
    /// The type of the matching map


			




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


			




	2080
	2109
	
		
    MatchingMap;


			




	...
	...
	
		
@@ -3039,5 +3068,5 @@


			




	3039
	3068
	
		
    ///


			




	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;


			




	3043
	3072
	
		
      for (NodeIt n(_graph); n != INVALID; ++n) {


			




	...
	...
	
		
@@ -3070,4 +3099,12 @@


			




	3070
	3099
	
		
    }


			




	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.


			




	3073
	3110
	
		
    ///

			




        

    

    

    

        

            

                

                    test/max_matching_test.cc
                

                

                  
                  
                  
                  Ignore white space
                  4 line context
                

                
                  
                
            

        

        

            

            



	...
	...
	
		
@@ -139,11 +139,15 @@


			




	139
	139
	
		
  const_mat_test.matching(e);


			




	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);


			




	142
	145
	
		

			




	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
	
		
}


			




	149
	153
	
		

			




	...
	...
	
		
@@ -168,8 +172,11 @@


			




	168
	172
	
		
  mat_test.run();


			




	169
	173
	
		
  


			




	170
	
	
		
  const_mat_test.matchingValue();


			




	
	174
	
		
  const_mat_test.matchingWeight();


			




	171
	175
	
		
  const_mat_test.matchingSize();


			




	172
	176
	
		
  const_mat_test.matching(e);


			




	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);


			




	175
	182
	
		
  


			




	...
	...
	
		
@@ -202,7 +209,10 @@


			




	202
	209
	
		
  mat_test.run();


			




	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);


			




	208
	218
	
		
  


			




	...
	...
	
		
@@ -225,7 +235,7 @@


			




	225
	235
	
		

			




	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;


			




	231
	241
	
		
    } else {


			




	...
	...
	
		
@@ -240,14 +250,14 @@


			




	240
	250
	
		
      ++num;


			




	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));


			




	253
	263
	
		
    }


			




	...
	...
	
		
@@ -257,5 +267,5 @@


			




	257
	267
	
		
  int odd_comp_num = 0;


			




	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);


			




	261
	271
	
		
      if (comp_root.find(root) == comp_root.end()) {


			




        

    






    
    



    


    

     
    
0 comments (0 inline)