Hi, On 12/18/2012 01:10 AM, Daniel Müllner wrote:
Hi all,
in which sense is the algorithm in graph_tool.topology.max_cardinality_matching with the heuristic=True switch a heuristic and not exact? As I understand, it might not return a maximum-cardinality matching even if there is one. But what about the edge weights? Does it always return a minimum-weight matching (respectively maximum-weight with minimize=False)? Or is this not guaranteed?
Indeed this is a bit confusing. If heuristic=False the maximum should be always guaranteed, and the is_maximal return value should also be one. Why is this value then returned? This is explained in the boost documentation: http://www.boost.org/doc/libs/1_52_0/libs/graph/doc/maximum_matching.html Why is a verification algorithm needed? Edmonds' algorithm is fairly complex, and it's nearly impossible for a human without a few days of spare time to figure out if the matching produced by edmonds_matching on a graph with, say, 100 vertices and 500 edges is indeed a maximum cardinality matching. A verification algorithm can do this mechanically, and it's much easier to verify by inspection that the verification algorithm has been implemented correctly than it is to verify by inspection that Edmonds' algorithm has been implemented correctly. The Boost Graph library makes it incredibly simple to perform the subroutines needed by the verifier (such as finding all the connected components of odd cardinality in a graph, or creating the induced graph on all vertices with a certain label) in just a few lines of code. So, in reality, as far as the algorithm is correct, this test is not necessary and could have been omitted. I decided to keep it. Maybe a better option would be to optionally activate it, since in most cases it is not desired. If heuristic=True, a much simpler algorithm is run, which does not guarantee that optimum is found, and also performs no checking.
Note that there are pitfalls to this question: eg. if all edge weights are equal to one, then the optimal min-weight matching is empty if I do not insist on max-cardinality. Can someone enlighten me what the heuristic actually optimizes? Cardinality or weights? Both (in which sense) or none (what's it good for, then)? And does it always find the optimum for one of those two criteria? Best, Daniel
The weighted version optimizes the sum of the weights. Thus, if the weights are one (or simply equal), it reduces to the cardinality. The heuristic _does not_ guarantee that the optimum is found, it only guarantees that it runs really fast in linear time. In fact, in many cases the maximum will _not_ be found. This algorithm is used for the sfdp_layout() algorithm, which needs more to be fast, rather than exact. There are exact algorithms for the weighted version, but I have yet to implement them. I intend to implement them at some point, and thus make the 'weight' parameter effective also when heuristic=False. I hope this clarifies. Cheers, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>