Hacktoberfest 2026：メンテナが10月に向けて印を付けた、オープンで初心者向けの issue。 Hacktoberfest の issue を見る

pgtap/mincut/compare.test.sql test data is flawed

オープン
  • 何か問題がありますか？
#2,583 コメント 3 件 リアクション 1 件 担当者 0 名 GitHub で見る

メンテナーはふだん 2 日以内に返信

まだ誰も着手していません。

  • #3104 @prashsti29 による — マージされずにクローズ

評価

難易度
3/5
見積もり時間
1〜2日
初心者へのやさしさ
65/100
issue の種類
バグ
明瞭さ
明確に書かれている
活発さ
静か
技術スタック
cpp, postgresql, sql
領域
databases, testing

調査の方向性

The issue is in the test file pgtap/mincut/compare.test.sql. First, examine the flawed test data for tests 5 and 6, understanding the graph structure and the Stoer-Wagner algorithm requirements. Review the pgr_stoerWagner function's implementation and the Boost library version impact. Create a valid test graph with non-negative costs and undirected edges, then update the test SQL with correct expected results. Run the TAP tests to verify the fix.

索引モデルが issue の本文から書いたものです。

説明

bug mincut pgtap

Problem
The two functionality tests in pgtap/mincut/compare.test.sql use graphs that are either vacuous or invalid, and the expected return values are not guaranteed.

This test case would benefit from being rewritten to use a graph designed for min-cut testing, but I am raising this issue because changes to Boost can cause it to fail.

To Reproduce
Compiling the test against Boost 1.80 or later (which uses a different implementation of Stoer-Wagner than earlier versions) causes failures.

Test 5

The graph for unit test "5: Mincut of edge 17" uses a graph with two nodes and one edge. Evaluating the inner query of the PREPARE stoerWagner6 statement (the one being passed to pgr_stoerWagner()) gives the following:

 id | source | target | cost | reverse_cost 
----+--------+--------+------+--------------
 17 |     14 |     15 |    1 |            1
(1 row)

Obviously this is the exact same graph as generated by the simpler stoerWagner5 subquery; in both cases the mincut is trivially to cut the only existing edge, so the comparison of stoerWagner5 and stoerWagner6 tests only that pgr_stoerWagner generates the same output given the same input, which was probably not what was intended.

Test 6

The subquery being passed to pgr_stoerWagner7 for the test "6: Compare the mincut of subgraph with actual result" results in the following graph:

 id | source | target | cost | reverse_cost 
----+--------+--------+------+--------------
  1 |      1 |      2 |    1 |            1
  2 |      2 |      3 |   -1 |            1
  3 |      3 |      4 |   -1 |            1
  4 |      2 |      5 |    1 |            1
  5 |      3 |      6 |    1 |           -1
  6 |      7 |      8 |    1 |            1
  7 |      8 |      5 |    1 |            1
  8 |      5 |      6 |    1 |            1
  9 |      6 |      9 |    1 |            1
 10 |      5 |     10 |    1 |            1
 11 |      6 |     11 |    1 |           -1
 12 |     10 |     11 |    1 |           -1
 13 |     11 |     12 |    1 |           -1
 14 |     10 |     13 |    1 |            1
 15 |      9 |     12 |    1 |            1
 16 |      4 |      9 |    1 |            1
(16 rows)

And expects that the mincut result is to cut the single edge with id 1.

There are three flaws with this test:

  1. The Stoer-Wagner algorithm requires all edges have non-negative costs, but edges 2 and 3 violate this.
  2. The Stoer-Wagner algorithm requires an undirected graph, but edges 2, 3, 5, 11, 12, and 13 have different costs in different directions.
  3. There are four distinct edges of equal weight that, each on its own, can be removed to partition the graph: edges 1, 6, 7, and 14. (Notice that nodes 1, 7, and 13 only have a single connection to the graph, and node 8 lies between node 7 and the rest of the graph.)

The test query for 6 asserts that the algorithm will select edge 1, but 6, 7, and 14 are valid (and edge 14 is selected when built against more modern versions of Boost).

主要言語
C++
スター
1.4k
フォーク
397
平均マージ
2日 2時間
マージ済み PR（30日）
4

環境構築

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

pgRouting/pgrouting のほかの issue

pgRouting/pgrouting の issue をすべて見る

似ている issue

C++ の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。