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

[vslashg]

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).

[muqeetqazi]

Sir ,I understand the problem you want to address the issues with two functionality tests related to min-cut testing in a SQL file using Boost. The problems you've identified involve the graphs being either vacuous or invalid, and the expected return values not being guaranteed.
To address the issues you've raised, you might consider the following steps:

Graph Design: Redesign the graphs used in the tests to ensure they are suitable for min-cut testing. Make sure the graphs are not vacuous, adhere to the requirements of the SW algorithm (non-negative costs, undirected edges), and have well-defined expected results.

Boost Version Compatibility: If the tests fail with Boost 1.80 or later due to changes in the implementation of Wagner algo, you may need to update the tests to be compatible with the newer Boost versions. This might involve understanding the changes in Boost and adapting the test cases accordingly.

Flawed Test Cases: Address the specific flaws you've identified in Test 5 and Test 6. Ensure that the graphs used in these tests adhere to the requirements of the Wagner algorithm and that the expected results are correctly defined.

Documentation: Update the documentation for the test cases to provide clarity on the purpose of each test, the expected behavior, and any assumptions made in designing the tests.

Here's a general outline of what you might need to do:
-- Test 5: Mincut of edge 17
-- Redesign the graph to ensure it is not vacuous and has a well-defined min-cut.
-- Update the expected results accordingly.

-- Test 6: Compare the mincut of subgraph with actual result
-- Redesign the graph to adhere to Stoer-Wagner algorithm requirements.
-- Address the flaws in the test case and ensure the expected results are accurate.
-- Consider using a directed graph for directed edges.

-- Update documentation for both tests to explain the changes made and the rationale behind them.