Possible error in calculation - unaccounted for capacity increases with FlowNetwork.

[skaurus]

Hello!

I was toying with visualgo.net to create some test cases, and I found this example which per visualgo should have maxflow of 28 from node 0 to 7, and your library calculates it as 29:

8 15
0 1 10 
0 2 5 
0 3 15 
1 2 4 
1 4 9 
1 5 15 
2 3 4 
2 5 8 
3 6 16 
4 5 15 
4 7 10 
5 6 15 
5 7 10 
6 2 6 
6 7 10

This text can be pasted in Edit graph -> Input graph, in the lower left corner. Note that you should choose 0-based indexing there. Also, be aware that graph editing is quite buggy there, what I mean is that visualgo will often complain that the 0 node is not the leftmost one, and 7 node is not a rightmost one. Although it is drawn the graph itself. Just repeat pressing Input graph -> paste -> Submit few times, until it will draw them the way it wants.

And then from the same corner you can start one of the three algorithms. All three give 28.

[skaurus]

Here is a playground link: https://go.dev/play/p/6eMOdx6Quqd May there be an error in how I use your library? With at least 4 other examples from visualgo there wasn't a mismatch though.

[kalexmills]

As far as I have seen, there is no error in how you're inputting the edge weights -- at least based on the data in your main method.

VisuAlgo is very clearly coming up with the right answer -- the s-t cut they compute is smaller than 29, so it's not clear why this is happening at the moment.

It's possible that something strange is happening with the remapping that you are performing in your example, but I haven't looked closely enough to be able to tell.

[kalexmills]

Strange -- somehow after running Outflow the edge from 0 -> 1 is getting remapped to a capacity of 28? That... almost certainly shouldn't be happening....

what's very weird is that the capacity being mapped to is precisely the... right answer?

Play link here: https://go.dev/play/p/42RS-yqvTdN

    edge 4 -> 5:  flow = 0 / 15
    edge 4 -> 7:  flow = 9 / 10
    edge 5 -> 6:  flow = 10 / 15
    edge 5 -> 7:  flow = 10 / 10
    edge 6 -> 7:  flow = 10 / 10
    edge 6 -> 2:  flow = 0 / 6
    edge 0 -> 1:  flow = 25 / 28
    edge 0 -> 2:  flow = 4 / 12
    edge 0 -> 3:  flow = 0 / 16
    edge 1 -> 2:  flow = 4 / 4
    edge 1 -> 4:  flow = 9 / 9
    edge 1 -> 5:  flow = 12 / 15
    edge 2 -> 3:  flow = 0 / 4
    edge 2 -> 5:  flow = 8 / 8
    edge 3 -> 6:  flow = 0 / 16
{6 [7 6 5 4 3 2] [map[4:{} 5:{} 6:{}] map[] map[1:{} 3:{}] map[1:{} 4:{}] map[2:{} 6:{}] map[2:{} 4:{} 7:{}] map[3:{}] map[1:{} 2:{}]] [[4 5 6] [2 3 7] [1 3 4 5 7] [1 2 4 6] [0 2 3 5 6] [0 2 4 7] [0 3 4] [1 2 5]] map[{0 4}:12 {0 5}:28 {0 6}:16 {2 1}:10 {2 3}:15 {3 1}:10 {3 4}:6 {4 2}:8 {4 6}:4 {5 2}:15 {5 4}:4 {5 7}:9 {6 3}:16 {7 1}:10 {7 2}:15] map[{0 4}:4 {0 5}:25 {0 6}:0 {2 1}:10 {2 3}:10 {3 1}:10 {4 2}:8 {4 6}:0 {5 2}:12 {5 4}:4 {5 7}:9 {7 1}:9] [-29 29 0 0 0 0 0 0] [8 0 9 10 9 9 10 1] [0 0 3 1 0 0 2 0] true true} <nil>

Program exited.

EDIT: prior to running Outflow here are the capacities reported:

    edge 0 -> 2:  flow = 0 / 5
    edge 0 -> 3:  flow = 0 / 15
    edge 0 -> 1:  flow = 0 / 10
    edge 1 -> 4:  flow = 0 / 9
    edge 1 -> 5:  flow = 0 / 15
    edge 1 -> 2:  flow = 0 / 4
    edge 2 -> 3:  flow = 0 / 4
    edge 2 -> 5:  flow = 0 / 8
    edge 3 -> 6:  flow = 0 / 16
    edge 4 -> 5:  flow = 0 / 15
    edge 4 -> 7:  flow = 0 / 10
    edge 5 -> 6:  flow = 0 / 15
    edge 5 -> 7:  flow = 0 / 10
    edge 6 -> 2:  flow = 0 / 6
    edge 6 -> 7:  flow = 0 / 10

So something is 100% wrong.

[skaurus]

Few more remarks about the visualgo:

• it seems to be required to recreate graph between runs of different algorithms
• turns out you can set Preferred output graph = Flow, and it will create graph as it needs to from the first try!

Also, here is a simplified getMaxFlow: https://go.dev/play/p/6eMOdx6Quqd

[skaurus]

Also, for the simplest graph source -> sink with edge capacity 1 the library gives answer 0 🤔 If I ask it to calculate the flow other way around, from sink to source, it will report it as 1. I'm not sure, but intuitively it seems wrong?

[kalexmills]

Also, for the simplest graph source -> sink with edge capacity 1 the library gives answer 0 🤔 If I ask it to calculate the flow other way around, from sink to source, it will report it as 1. I'm not sure, but intuitively it seems wrong?

Awesome!! All of these can go into some of the unit test cases.