1
$\begingroup$

I am not 100% sure if this is the right stackexchange to ask. I have a max-flow algorithm and I am also computing the min-cut from that algorithm.

I want to test the correctness and speed of it and I am trying to find if there are some datasets against which I can test my algorithm. The dataset should preferably have the max-flow value and the set of edges belonging to min-cut.

$\endgroup$
2
$\begingroup$

To test correctness: the set of edges belonging to a min-cut is not unique in general, so a dataset like you ask would not really be helpful, apart from checking that the value of the cut is the right one. However, it is easy to check correctness yourself by using the output of your algorithm if you compute both the max-flow and the min-cut; just check that the first is a valid flow, the second is a valid cut, and that their value is the same. By the max-flow/min-cut theorem, they must then both be optimal.

To test speed: it's pretty old (1990-91), but you may want to have a look at the archive of the DIMACS implementation challenge on the Maximum Flow problem. It includes many generators and several other codes. For a more modern dataset (1998-2013), here is a collection of Maximum Flow problems arising in computer vision. Also, Andrew V. Goldberg has a page on network optimization software with several useful links (although the Min Cut one seems to be dead).

$\endgroup$
  • $\begingroup$ Thanks! I tried searching for Goldberg's mincut forever but it seems to have disappeared. $\endgroup$ – Morpheus Dec 21 '18 at 7:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.