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.

_______________________________________________

Unsubscribe & other changes:

http://lists.boost.org/mailman/listinfo.cgi/boost