[Graph] Min Cut with float weights

From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2020-04-16 16:45:26

Dear Experts,

I am attempting to use stoer_wagner_min_cut for the first time.

Using float as the edge weight type seems to be problematic for
non-trivial graphs.  I think this is possibly because it adds an
edge weight to the cut weight and then later subtracts the same
value, but doesn't get back to exactly the previous value due
to loss of precision.  The errors accumulate and eventually the
reported cut weight is nonsense.

I am now trying with integer weights but I worry that this could
suffer overflows.  If my edge weights are in the range 0...W,
for a graph with E edges the largest cut weight would be < W*E.
But does the algorithm ever use larger values internally?

Also, I'd be interested if anyone has tried to break a graph
into subgraphs by recursively breaking at the min_cut until
the min_cut weight is below some threshold.  I have a graph
with of the order of 10^4 vertices and 10^6 edges and this
would be tractable if the min_cuts broke the graph into roughly
equal pieces; instead, they tend to remove a small number of
vertices each time, leaving almost as much work for the next
recursion.  So I think I want to find a cut whose weight is
below a threshold and that is in some sense locally minimal
and that leaves two largish subgraphs.  Any ideas?

Cheers, Phil.