Problems

Algorithm works for undirected graph only

From boost

Both edmonds_maximum_cardinality_matching and checked_edmonds_maximum_cardinality_matching find the maximum cardinality matching in any undirected graph.

I tried the example with directed graph.

$ g++ match_example.cpp 
$ ./a.out
a.out: match_example.cpp:74: int main(): Assertion `success' failed.
Aborted (core dumped)

No one else problems detected yet, but it should not be allowed to run on a directed graph. Eventually a problem will happen and the current results with directed graph are invalid for the problem definition.

About results

• seq is not needed as the results unique identifier can be edge
• And because the graph is undirected, source and target are also not needed.
  • Those are values that can be found by joining the result with the edges table on the database.

About the inner query

SELECT id, source, target, cost AS going, reverse_cost AS coming FROM edge_table

Following the general form on the inner query, it should be

SELECT id, source, target, cost, reverse_cost FROM edge_table

Changes

SQL

On V3

• Create function pgr_maxCardinalityMatch(Edges SQL) -> returns edge
• Deprecate function pgr_maxCardinalityMatch(Edges SQL, [directed]) -> returns (seq, edge, source, target) On V4
• Remove function pgr_maxCardinalityMatch(Edges SQL, [directed])

code

On V3

• Ignore the flag
• Accept cost and reverse_cost as columns on the inner query On V4

• Do not accept going & coming
• Cleanup code

TODO

• [x] #2342
• [x] #2343