Hi,
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:
Boost Graph Library: Maximum Cardinality Matching - 1.52.0
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