Graphs and flows

[ma...@mendelu.cz]

Dear sage support

trying to learn how to use Sage in graph theory. I do not know the
terminology in this area of mathematics. Is the flow and the edge_cut
the two quantities which are equal by ford fulkerson theorem
http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem ?

I consider the following graph. The flow is 30 (which is correct) and
the edge_cut is 31.

Many thanks

Robert



sage: g=DiGraph({0:{1:12,2:19},1:{2:9,3:8},2:{3:2,4:24},3:
{4:10,5:14,6:8},4:{1:12,6:20,7:5},5:{8:19},6:{5:8,7:7},7:{8:15}})

sage: g.flow(0,8) # maximal flow
30.0

sage: g.flow(0,8,value_only=False)[1].edges() # edges with flow
[(0, 1, 12), (0, 2, 18.0), (1, 2, 4.0), (1, 3, 8), (2, 3, 2), (2, 4,
20), (3, 5, 10), (4, 6, 15), (4, 7, 5), (5, 8, 18.0), (6, 5, 8), (6,
7, 7), (7, 8, 12)]

sage: g.edges() # original edges
[(0, 1, 12), (0, 2, 19), (1, 2, 9), (1, 3, 8), (2, 3, 2), (2, 4, 24),
(3, 4, 10), (3, 5, 14), (3, 6, 8), (4, 1, 12), (4, 6, 20), (4, 7, 5),
(5, 8, 19), (6, 5, 8), (6, 7, 7), (7, 8, 15)]

sage: g.edge_cut(0,8,use_edge_labels=True,value_only=False,
vertices=True)
(31.0, [(4, 7), (5, 8), (6, 7)], [[0, 1, 2, 3, 4, 5, 6], [7, 8]])

[ma...@mendelu.cz]

On 3 zář, 15:54, "ma...@mendelu.cz" <ma...@mendelu.cz> wrote:
> Dear sage support
>
> trying to learn how to use Sage in graph theory. I do not know the
> terminology in this area of mathematics. Is the flow and the edge_cut
> the two quantities which are equal by ford fulkerson theoremhttp://en.wikipedia.org/wiki/Max-flow_min-cut_theorem?
>
> I consider the following graph. The flow is 30 (which is correct) and
> the edge_cut is 31.

Btw, I observed that converting to undirected graph gives the same
edge_cut, 31. Does edge_cut assume implicitly that the graph is
undirected?

Robert

[Nathann Cohen]

> Btw, I observed that converting to undirected graph gives the same
> edge_cut, 31. Does edge_cut assume implicitly that the graph is
> undirected?

No, it has two behaviours depending on the type of Graph.

I am trying to find out where it comes from, but for the moment I am a
bit stuck O_o

What I can tell you though, is that I wrote some time ago a patch
implementing a Ford Fulkerson algorithm in Sage ( Flow problems are
solved through LP at the moment ), which also redefines methods for
edge_cut. With this patch applied [1], you can do :

sage: sage: g=DiGraph({0:{1:12,2:19},1:{2:9,3:8},2:{3:2,4:24},3:
....: {4:10,5:14,6:8},4:{1:12,6:20,7:5},5:{8:19},6:{5:8,7:7},7:

{8:15}})
sage: g.flow(0,8)

30
sage: g.edge_cut(0,8,use_edge_labels=True)
30
sage: g.edge_cut(0,8,use_edge_labels=True, value_only = False,
vertices = True)
[30, [(1, 3, 8), (2, 3, 2), (4, 7, 5), (6, 5, 8), (6, 7, 7)], [[0, 1,
2, 4, 6], [8, 3, 5, 7]]]

But when you force it to use LP, what you get is :

sage: g.edge_cut(0,8,use_edge_labels=True, method="LP")
31.0

Definitely something that needs to be fixed.

I'll post a followup to this thread when I will have found the
cause :-)

Nathann

[1] http://trac.sagemath.org/sage_trac/ticket/9350

[Nathann Cohen]

> I'll post a followup to this thread when I will have found the
> cause :-)

I re-read thirty times the code and even tried to debug the LP solver
themselves. It went easier when I had the smart idea to read what was
written and not what I intended to write. The line :

p.add_constraint(v[x] + b[x][y] - v[y], min=0, max=0)

Should be :

p.add_constraint(v[x] + b[x][y] - v[y], min=0)

I'm posting a patch for this : http://trac.sagemath.org/sage_trac/ticket/9852

In the meantime, you can use the patch I mentionned previously to get
accurate answers. It will also be faster.

Thank you very much for reporting this bug ! :-)

Nathann