Maxflow hangs on large values and infinity

[GomezGab]

@dperry17 I am trying to wire a super source and super sink in a max flow problem. To do this, I tried to set the capacity of the edges from the super nodes to double infinity and even 2^63. Both of these values caused max flow to hang.

I suspect that any graph with capacity ranges spanning several orders of magnitude will cause this hang (especially if you have some sort of termination condition that relies on assuming that a != a -b.

[DrTimothyAldenDavis]

I think the issue is that the "infinite" flow at the source/dest swamps the weights of the graph. The algorithm has to add flows and preflows, and if the preflow is 2^63, and an edge weight is 1, then the edge weight gets dropped. This is not a bug that can be fixed, but a feature of the push/relabel method.

It would be better to set "infinite" flow to something smaller, like 2^32.