pgr_maxCardinalityMatch problems
Maintainers usually reply within 3 days
Nobody has claimed this yet.
Assessment
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Newbie friendliness
- 55/100
Research direction
The issue is about the pgr_maxCardinalityMatch function in pgRouting. The algorithm currently incorrectly accepts directed graphs, but should only work on undirected graphs. Check the function implementation in the C++ code, likely in files related to matching algorithms. The changes involve modifying the SQL signature and internal handling of cost/reverse_cost columns. Review the linked pull requests #2342 and #2343 for context on what has been done. Testing involves running the matching example and ensuring directed graphs are rejected.
Written by the indexing model from the issue text.
Description
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
seqis not needed as the results unique identifier can be edge- And because the graph is undirected,
sourceandtargetare 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)-> returnsedge - 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
costandreverse_costas columns on the inner query
On V4
- Do not accept
going&coming - Cleanup code
TODO
- #2342
- #2343
- Dominant language
- C++
- Stars
- 1.4k
- Forks
- 397
- Avg merge
- 2d 16h
- Merged PRs (30d)
- 8
Getting set up
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from pgRouting/pgrouting
-
Difficulty 2/5 1-3 hours Newbie friendliness 72/100
Maintainers usually reply within 3 days
-
Difficulty 2/5 1-3 hours Newbie friendliness 82/100
Maintainers usually reply within 3 days
-
Administrative Enhancement
Difficulty 1/5 Under an hour Newbie friendliness 80/100
Maintainers usually reply within 3 days
-
points_input Developers docPossibly taken @withaman69 claimed this 101 days ago. OpenC/C++ Developers Doc. good first issue
Difficulty 2/5 1-3 hours Newbie friendliness 70/100
pgRouting/pgrouting#973 · 10 comments ·
Maintainers usually reply within 3 days
-
get_check_data developers docPossibly taken @withaman69 claimed this 102 days ago. OpenC/C++ Developers Doc. good first issue
Difficulty 2/5 1-3 hours Newbie friendliness 70/100
pgRouting/pgrouting#972 · 7 comments ·
Maintainers usually reply within 3 days
All issues in pgRouting/pgrouting
Similar issues
-
std::fdim drops partial derivative w.r.t second argument in forward and reverse modePossibly taken @ADITYASINGH1206 claimed this today. Open
Difficulty 1/5 Under an hour Newbie friendliness 85/100
vgvassilev/clad#2534 ·
Maintainers usually reply within 1 day
-
Difficulty 2/5 1-3 hours Newbie friendliness 70/100
Maintainers usually reply within 1 day
-
HAP.cpp fixOpen
Difficulty 2/5 1-3 hours Newbie friendliness 68/100
-
Difficulty 2/5 1-3 hours Newbie friendliness 70/100
KLayout/klayout#2554 · 1 comment ·
Maintainers usually reply within 1 day
-
Difficulty 2/5 1-3 hours Newbie friendliness 72/100
Maintainers usually reply within 1 day