Imrovements for the interface of the matching algorithms

[Peter Kovacs]

I have some idea and questions about the interface of the matching algorithms:

1. I suggest two new query functions for MaxMatching:

   const MatchingMap& matchingMap() const {
     return *_matching;
   }
   
   const SatusMap& decompositionMap() const {
     return *_status;
   }
   

   And there should be doc for the public types MatchingMap and StatusMap, of course. (Maybe the later one could be called DecompositionMap or decomposition() could be renamed to status().

2. The first one of the above functions should also be introduced to the weighted matching classes.

3. What about using matchingWeight() instead of matchingValue() in the two weighted matching classes?

4. What about moving MaxWeightedMatching and MaxWeightedPerfectMatching to a separate source file max_weighted_matching.h instead of max_matching.h?

[Alpar Juttner]

Replying to kpeter:

I have some idea and questions about the interface of the matching algorithms:

1. I suggest two new query functions for MaxMatching:

   const MatchingMap& matchingMap() const {
     return *_matching;
   }
   
   const SatusMap& decompositionMap() const {
     return *_status;
   }
   

   And there should be doc for the public types MatchingMap and StatusMap, of course. (Maybe the later one could be called DecompositionMap or decomposition() could be renamed to status().

2. The first one of the above functions should also be introduced to the weighted matching classes.

All these are good ideas, though they aren't blokker of release 1.1.

3. What about using matchingWeight() instead of matchingValue() in the two weighted matching classes?

I agree with this change. According to the (vague) analogy with the flows, the value of a matching should be the number of edges in it.

Btw. it is quite annoying in itself that some algorithms use lengths/distances others use cost, others use weights. Unfortunately we have nothing to do with it.

4. What about moving MaxWeightedMatching and MaxWeightedPerfectMatching to a separate source file max_weighted_matching.h instead of max_matching.h?

I'm not a big fan of splitting everything into an own header file.

But at least the file should be renamed to e.g. matching.h.

[Balazs Dezso]

Replying to kpeter:

I have some idea and questions about the interface of the matching algorithms:

1. I suggest two new query functions for MaxMatching:

   const MatchingMap& matchingMap() const {
     return *_matching;
   }
   
   const SatusMap& decompositionMap() const {
     return *_status;
   }
   

   And there should be doc for the public types MatchingMap and StatusMap, of course. (Maybe the later one could be called DecompositionMap or decomposition() could be renamed to status().

Ok, it is useful, I think the status will be preferred.

2. The first one of the above functions should also be introduced to the weighted matching classes.

Ok.

3. What about using matchingWeight() instead of matchingValue() in the two weighted matching classes?

It might be a better name.

4. What about moving MaxWeightedMatching and MaxWeightedPerfectMatching to a separate source file max_weighted_matching.h instead of max_matching.h?

What is the advantage of this? I think we should consider also the names of the non-ported bipartite matching files and classes. Could you advice names for those classes and files?

[Alpar Juttner]

Replying to deba:

4. What about moving MaxWeightedMatching and MaxWeightedPerfectMatching to a separate source file max_weighted_matching.h instead of max_matching.h?

What is the advantage of this? I think we should consider also the names of the non-ported bipartite matching files and classes. Could you advice names for those classes and files?

My suggestion is matching.h for the non-bipartite matching and bipartite_matching.h for the bipartite version.

Alternatively, we can indicate the algorithm names like edmonds.h But than the class names should be something similar like Edmonds and WeightedEdmonds, or EdmondsMaxMatching and EdmondsWeightedMatching.

[Peter Kovacs]

Replying to deba:

Ok, it is useful

Let's introduce matchingMap() and statusMap() into the classes. It is not so important for release 1.1, but they are trivial, so we could do it now.

I think the status will be preferred.

However it is a critical question, since we already have a decomposition() function in MaxMatching. Should it be renamed to status()?

3. What about using matchingWeight() instead of matchingValue() in the two weighted matching classes?

It might be a better name.

Let's use it then.

4. What about moving MaxWeightedMatching and MaxWeightedPerfectMatching to a separate source file max_weighted_matching.h instead of max_matching.h?

What is the advantage of this? I think we should consider also the names of the non-ported bipartite matching files and classes. Could you advice names for those classes and files?

Okay, I'm convinced. Let's use matching.h and bipartite_matching.h (in the future).

[Peter Kovacs]

Replying to alpar:

My suggestion is matching.h for the non-bipartite matching and bipartite_matching.h for the bipartite version.

It seems good.

Alternatively, we can indicate the algorithm names like edmonds.h But than the class names should be something similar like Edmonds and WeightedEdmonds, or EdmondsMaxMatching and EdmondsWeightedMatching.

We use such names for other algorithms, but here three algorithms for three different problems would be indicated with the same author name. Moreover (currently) there is only one implementation for all of the problems. Thus I prefer the current names.

Another question is what to do if we would like to introduce another implementation for a problem for which we have only one solution now, which is called by the name of the problem. I think in these cases we should keep the original class name with unchanged interface as an alias for the (generally) best implementation and use separate names for all algoirthms. Similarly to min. cost flow algorithms, which are called according to the method they use (NetworkSimplex, CostScaling, CapacityScaling etc.) and we have MinCostFlow as an alias for NetworkSimplex.

Maybe an additional question should be considered here. If we will have another algorithm using cost/capacity scaling or a network simplex method for another problem, it would cause problem. We could aviod it using prefixes or suffixes in the algorithm names, e.g. McfCapacityScaling or CapacityScalingMcf. However it would be inconsistent compared to other names and it would be more complicated. What do you think about it?

[Peter Kovacs]

The attached patches solves all these issues. They depend on [b61354458b59] (see #264), which is also contained in the bundle file.

The first changeset [7ac52d6a268e]:

• 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.

The second changeset [d657c71db7db] renames max_matching.h to matching.h.

[Alpar Juttner]

[7ac52d6a268e] and [d657c71db7db] are in the main branch.