pgr_maxCardinalityMatch problems

Đang mở
  • Có gì không ổn?
#2,341 0 bình luận 0 reaction 0 người được giao Xem trên GitHub

Maintainer thường phản hồi trong vòng 3 ngày

Chưa có ai nhận issue này.

Đánh giá

Độ khó
3/5
Thời gian dự kiến
1-2 ngày
Mức phù hợp với người mới
55/100
Loại issue
Lỗi
Độ rõ ràng
Đặc tả rõ ràng
Mức độ hoạt động
Đình trệ
Công nghệ
cpp, postgresql
Lĩnh vực
backend, databases

Hướng nghiên cứu

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.

Do mô hình lập chỉ mục viết ra từ nội dung của issue.

Mô tả

Bug Report Flow

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

  • #2342
  • #2343
Ngôn ngữ chính
C++
Star
1.4k
Fork
397
Merge trung bình
2 ngày 23 giờ
Pull request đã merge (30 ngày)
7

Chuẩn bị môi trường

Bắt đầu từ đâu

  1. Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
  2. Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
  3. Fork repository và làm thay đổi trên một nhánh.
  4. Mở pull request có tham chiếu số hiệu của issue.

Issue khác của pgRouting/pgrouting

Tất cả issue của pgRouting/pgrouting

Issue tương tự

Thêm issue về C++

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.