10
$\begingroup$

Bug introduced in 10.0 and persisting through 12.1


Try the following program:

FindMaximumFlow[
  Graph[{a, b, c, d, e, f}, {d <-> a, b <-> a, a <-> c, d <-> f, 
    f <-> c}, VertexCapacity -> {5, 10, 7, 11, 8, 12}], {d, b}, {c, 
   a}]

You may find that it gives you a "seemingly proper" result, but does it?

Try to run this program several times, you'll find that it gives different results! Furthermore, if you can draw out this graph and calculate this manually, you can find the real result should be 12.

It seems that this is not a single case, after changing this code in several ways, I can still find similar problem:

Table[FindMaximumFlow[
  Graph[{a, b, c, d, f}, {d <-> a, b <-> a, a <-> c, d <-> f, 
    f <-> c}, VertexCapacity -> {5, 10, 7, 11, 12}], {d, b}, {c}], 10]

Table[FindMaximumFlow[
  Graph[{a, b, c, d, f}, {d <-> a, b <-> a, a <-> c, d <-> f, 
    f <-> c}, VertexCapacity -> {5, 10, 7, 11, 12}], {d, b}, {c}], 10]

Did I do anything wrong dealing with this case or it's just a bug?


My system information:

Mathematica 10.2,10.3,10.4,10.4.1(This problem exists in all these versions)

CPU: i7-4800mq, i7-6560U

RAM: 8G

$\endgroup$
  • $\begingroup$ Well, I certainly get different results too. 1-3 on Debian. $\endgroup$ – Feyre Jun 10 '16 at 11:01
  • $\begingroup$ d-b isn't a vertex though? $\endgroup$ – Feyre Jun 10 '16 at 11:13
  • $\begingroup$ Both d and b are vertices. Check usage 3 of FindMaximumFlow at reference.wolfram.com/language/ref/… $\endgroup$ – Wjx Jun 10 '16 at 11:26
  • $\begingroup$ You're right, it does seem like reversing and putting {c, a}, {d, b} actually gives 3 as a consistent answer. $\endgroup$ – Feyre Jun 10 '16 at 11:34
  • 3
    $\begingroup$ I reported the problem a long time ago to Wolfram support and was told it had been passed on to the technical team. I was disappointed to see that the problem still persists even in the newest version of Mathematica (v11 Mac OS X latest version) despite the long standing bug. $\endgroup$ – Mac Aug 15 '16 at 12:14

Your Answer

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

Browse other questions tagged or ask your own question.