> 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
--
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-support
URL: http://www.sagemath.org
