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!!!!!
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.
