5
$\begingroup$

Bugs(the fourth and fifth behavior) is present in V10.4.1


I'm at a loss to understand the behavior of the FindMinimumCostFlow function. Here are a few cases I find confusing.

First Behavior

g = Graph[
      {1, 2, 3, 4}, {1 -> 2, 1 -> 3, 2 -> 3, 3 -> 2, 3 -> 4, 2 -> 4}, 
      {VertexLabels -> {Placed["Name", Center]}, 
      VertexSize -> {0.3}, VertexStyle -> {GrayLevel[1]}}
    ]

f = FindMinimumCostFlow[g, {10, 0, 0, -10}, "OptimumFlowData"];
f["CostValue"]
f["FlowGraph"]

How to understand the $20$? I think the cost value should be 2 as the documentation on Details and Options.

With the default setting EdgeCost->Automatic, the cost per unit flow on an edge is taken to be the EdgeCost in the graph g if available, otherwise 1.

Second Behavior

FindMinimumCostFlow[g, 1, 4, 1.5]

3.

How to understand this 3? I think it should be 4, because the flow goes through four edges.

Third Behavior

This is an example from the documentation. The original cost value reported in the saved docs is 2. When you run the code, it will return $0.6$.

I think the original value is right, because the Edgecost is Automatic

But I am not sure which result should be given.


Updating for other two cases

As the Wjx's answer,the behavior from first to third seem to no problem.But I found other strange behaviors.

Fourth Behavior

I can sure this is a bug attribution--"FlowValue",The screenshoot from documentation

Fifth Behavior

From that comment I gave

g = Graph[{1, 2, 3, 4}, {1 <-> 2, 2 <-> 3, 3 <-> 1, 3 <-> 4}, 
  EdgeCapacity -> {0.4, 0.6, 0.9, 0.7}, 
  VertexLabels -> "Name"]; SetProperty[g, 
 EdgeLabels -> 
  MapThread[Rule, {EdgeList[g], PropertyValue[g, EdgeCapacity]}]]
FindMinimumCostFlow[g, 1, 3]
FindMinimumCostFlow[g, 1, 3, "FlowGraph"]

The $1.7$ is expected but $1.4$.

$\endgroup$
6
+50
$\begingroup$

This IS NOT A BUG but do IS A BUG as well.

This is not a BUG at first, but I found a serious BUG while trying to persuade @yode it's not a BUG.

I think I've got an explanation for this problem:

First thing first, Let's first check our documentation:

It said that when setting EdgeCost to Automatic cost per unit flow on an edge is taken to be 1. Thus we can know that the calculation of Cost is given by multiplying EdgeCost with EdgeFlow and finally sum them up!!!

Thus for the first situation, as there're 10 units of flow to deliver while each unit will go through 2 edges so the final cost shall be 20, not 2.

The second problem can be solved the same way: as there're 1.5 units of flow to deliver while each unit will go through 2 edges so the final cost shall be 3, not 4.

The third is a bit intriguing: it seems that in order to get a maximum flow, it shall flow through the upper part with 0.3 intensity while flow through the 0.9 edge with 0.9 intensity. So the total should be 0.3*2+0.9=1.5 instead of 0.6 which we get. How?

First let's show the FullForm of that Graph, the useful part is shown below:

Graph[List[1, 2, 3, 4], 
 List[DirectedEdge[1, 2], DirectedEdge[2, 3], DirectedEdge[3, 1], 
  DirectedEdge[3, 4]], 
 Rule[EdgeCapacity, List[0.3`, 0.6`, 0.9`, 0.7`]]]

It's actually an Directed Graph!!!!!

this is the true graph

So the flow can only go through the upper part thus the result should be 0.3*2=0.6 Great! So the result is correct, but the reference's stored result, maybe because of some early versions' bug, is left wrong.

Problem solved~

Hope this explanation can help you~~


Edit1

I think I've found something wrongly stated in reference.

It said that when setting EdgeCapacity to Automatic, it means Infinity. But how can a graph with infinity flow get a not infinity cost? In real situations, I think it will automatically set them to 1 Instead. Why not check the reference out~ The first example it gives shows this: The FullForm of this graph is without any specification on EdgeCapacity While the result is 9 and the flow will go in a way that ensures every edge's flowcount is 1, which means the edges are probably with EdgeCapacity of 1.

But for the fourth example @yode gives, I really have no idea what's going on......


Edit2

Now I'm totally confused about the fourth and the fifth situation:

Check this two graphs out:

g1=Graph[{1, 2, 3, 4}, {1 <-> 2, 2 <-> 3, 3 <-> 1, 3 <-> 4}, 
 EdgeCapacity -> {.6, .6, .6, .7}]
g2=Graph[{1, 2, 3, 4}, {1 <-> 2, 2 <-> 3, 3 <-> 1, 3 <-> 4}, 
 EdgeCapacity -> {.6, .6, .9, .7}]

FindMinimumCostFlow[g1, 1, 3]
FindMinimumCostFlow[g2, 1, 3]

(*1.8*)
(*1.8*)

How is that possible for us to change one edge's capacity, while the edge is the shortest connection between source and the end, without influencing the cost?

Still more mysterious:

g = Graph[{1, 2, 3, 4}, {1 <-> 2, 2 <-> 3, 1 <-> 3, 3 <-> 4}, 
  EdgeCapacity -> {.6, .6, .0, .7}, VertexLabels -> "Name"]

f = FindMinimumCostFlow[g, 1, 4, "OptimumFlowData"];
f["FlowGraph"]
f["CostValue"]
f["FlowValue"]

It actually find a solution that flow through an edge with 0 Capacity!!!!!

That must be a bug......


Edit3

The "FlowValue" is really a HUGE bug I suppose, It kept 0 in thousands of trials with random graphs.

Quiet@DeleteCases[
  Table[FindMinimumCostFlow[RandomGraph[RandomInteger[50, 2]], 1, 2, 
    "FlowValue"], 1000], Except[_Integer]]

This program returns only 0. I have nothing to say about that......


Edit4 This edit is probably the most IMPORTANT edit

----An explanation for problem 5

"...A whole set of relationship errors, which, when I started digging into them, it looks almost like a checklist for a sex therapist or a couples counselor. You sort of get down there to the bottom and things get really dicey."------From a TED Talk

When I found this bug, I'm extremely frustrated.

FindMinimumCostFlow[
 Graph[{1, 2, 3}, {1 <-> 2, 1 <-> 3, 2 <-> 3}, 
  EdgeCapacity -> {1, 0, .5}, 
  VertexLabels -> "Name"], 1, 3, "FlowGraph"]

This code runs quite well, the result, 2, is quite reasonable if you have read my previous explanation.

Then, the second code runs out quite well too, seemingly reasonable:

FindMinimumCostFlow[
 Graph[{1, 2, 3}, {1 <-> 2, 3 <-> 1, 2 <-> 3}, 
  EdgeCapacity -> {1, 0, .5}, 
  VertexLabels -> "Name"], 1, 3, "FlowGraph"]

after all, 1<->3 is the same thing as 3<->1

but it's not quite pleasant when the third code generate the same result:

FindMinimumCostFlow[
 Graph[{1, 2, 3}, {1 <-> 2, 2 <-> 3, 1 <-> 3}, 
  EdgeCapacity -> {1, 0, .5}, 
  VertexLabels -> "Name"], 1, 3, "FlowGraph"]

I've already changed the position of edges, so if we want to get a proper result, we'll have to change EdgeCapacity accordingly. but without changing it, we get an IDENTICAL RESULT!!!!!! That's not normal, indicating that while assigning EdgeCapacity, the Graph automatically changed the vertex's order, some sort of Sort it. and that's the reason, I suppose, why it generates the wrong result!!!

Also, after changing the order of EdgeCapacity rules, it generates the correct result!!

FindMinimumCostFlow[
 Graph[{1, 2, 3}, {1 <-> 2, 2 <-> 3, 1 <-> 3}, 
  EdgeCapacity -> {1, .5, 0}, 
  VertexLabels -> "Name"], 1, 3, "FlowGraph"]

Maybe this bug will exist in other functions related to this as well, let's sort them out.


SO here's the final solution for question 5, simply change the order of EdgeCapacity will make the result correct......

g = Graph[{1, 2, 3, 4}, {1 <-> 2, 2 <-> 3, 3 <-> 1, 3 <-> 4}, 
  EdgeCapacity -> {0.4, 0, 0.6, 0.7}, 
  VertexLabels -> "Name"]; SetProperty[g, 
 EdgeLabels -> 
  MapThread[Rule, {EdgeList[g], PropertyValue[g, EdgeCapacity]}]]
FindMinimumCostFlow[g, 1, 3]
FindMinimumCostFlow[g, 1, 3, "FlowGraph"]

This will generate the correct result of .8 and a correct flowgraph as well, while using the normal order won't.

It seems that it's sorting in a rather odd way, maybe someone can comeout and explain it a bit further, with @yode's graph, here's what the result seems to tell us:

{{1 <-> 2, 2 <-> 3, 1 <-> 3, 3 <-> 4} -> 
  0.8, {1 <-> 2, 2 <-> 3, 3 <-> 4, 1 <-> 3} -> 
  0.8, {1 <-> 2, 1 <-> 3, 2 <-> 3, 3 <-> 4} -> 
  0.8, {1 <-> 2, 1 <-> 3, 3 <-> 4, 2 <-> 3} -> 
  0.8, {1 <-> 2, 3 <-> 4, 2 <-> 3, 1 <-> 3} -> 
  0.8, {1 <-> 2, 3 <-> 4, 1 <-> 3, 2 <-> 3} -> 
  0.8, {2 <-> 3, 1 <-> 2, 1 <-> 3, 3 <-> 4} -> 
  0.8, {2 <-> 3, 1 <-> 2, 3 <-> 4, 1 <-> 3} -> 
  0.8, {2 <-> 3, 1 <-> 3, 1 <-> 2, 3 <-> 4} -> 
  0.4, {2 <-> 3, 1 <-> 3, 3 <-> 4, 1 <-> 2} -> 
  0.4, {2 <-> 3, 3 <-> 4, 1 <-> 2, 1 <-> 3} -> 
  0.8, {2 <-> 3, 3 <-> 4, 1 <-> 3, 1 <-> 2} -> 
  0.4, {1 <-> 3, 1 <-> 2, 2 <-> 3, 3 <-> 4} -> 
  0.4, {1 <-> 3, 1 <-> 2, 3 <-> 4, 2 <-> 3} -> 
  0.4, {1 <-> 3, 2 <-> 3, 1 <-> 2, 3 <-> 4} -> 
  0.4, {1 <-> 3, 2 <-> 3, 3 <-> 4, 1 <-> 2} -> 
  0.4, {1 <-> 3, 3 <-> 4, 1 <-> 2, 2 <-> 3} -> 
  0.4, {1 <-> 3, 3 <-> 4, 2 <-> 3, 1 <-> 2} -> 
  0.4, {3 <-> 4, 1 <-> 2, 2 <-> 3, 1 <-> 3} -> 
  0.8, {3 <-> 4, 1 <-> 2, 1 <-> 3, 2 <-> 3} -> 
  0.8, {3 <-> 4, 2 <-> 3, 1 <-> 2, 1 <-> 3} -> 
  0.8, {3 <-> 4, 2 <-> 3, 1 <-> 3, 1 <-> 2} -> 
  0.4, {3 <-> 4, 1 <-> 3, 1 <-> 2, 2 <-> 3} -> 
  0.4, {3 <-> 4, 1 <-> 3, 2 <-> 3, 1 <-> 2} -> 0.4}

I hope the bug lists can end here...... I really don't like to see a swarm of bug flying in those bottom level functions, these make me really uncomfortable.

$\endgroup$
  • $\begingroup$ Upvote for your very resonable analysis $\endgroup$ – yode Jun 26 '16 at 15:24
  • $\begingroup$ But how to understand the $1.4$ if we change it into Undirected Graph?g = Graph[{1, 2, 3, 4}, {1 <-> 2, 2 <-> 3, 3 <-> 1, 3 <-> 4}, EdgeCapacity -> {0.4, 0.6, 0.9, 0.7}, VertexLabels -> "Name"]; SetProperty[g, EdgeLabels -> MapThread[Rule, {EdgeList[g], PropertyValue[g, EdgeCapacity]}]]; FindMinimumCostFlow[g, 1, 3] $\endgroup$ – yode Jun 26 '16 at 15:44
  • $\begingroup$ For this problem, I still have no idea what's going on at this point...... $\endgroup$ – Wjx Jun 27 '16 at 1:10
  • 1
    $\begingroup$ 2018, Version 11,3. "FlowValue" still wrong. $\endgroup$ – Slepecky Mamut May 30 '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.