This is a way to do it if you already have an integral flow-solver. I know there was some work on that during sagedays-16, which is a while ago, so I imagine this is in Sage now, though perhaps not.
1) Of the two nodes that we want to find independent paths between, let one be the sink and one be the source. 2) Give every edge a capacity of 1. 3) Replace every vertex, except the source and sink, with two vertices a and b and an edge going from a to b with a capacity of 1. Let in- coming edges go to a, and let out-going edges start at b. 4) Compute an integral flow f. 5) The set of edges carrying non-zero flow will now be a maximal set of vertex-disjoint paths from the source to the sink. I don't know of a way to do this faster using linear programming, other than that flow can be solved using linear programming, but I don't think that is the best way to do it. Is there a faster linear programming way? Cheers Bjarke On 27 Aug., 14:21, Nathann Cohen <nathann.co...@gmail.com> wrote: > Sadly, it is not included in Sage already... There's a patch for > max_flow, vertex_cut, and edge_cut though : > > http://trac.sagemath.org/sage_trac/ticket/6680 > > The thing is that I am desperately looking for someone to review that > patch, so if you feel like giving it a try, don't hesitate :-D > > ( If you just want to use it, though, you will find the instructions > on this web page to use it... I hope you will like it ! ) > > I assure you I will write the function you need as soon as these > patches will be merged into Sage.. They all require Linear Programming > which is itself still waiting to be merged ! I have been postponing so > many functions because of that... > > Oh, and by the way, there's another ticket waiting for review that may > be of interest for you (if you want to use it, or review it) : > > http://trac.sagemath.org/sage_trac/ticket/6679 > > Nathann > > On Aug 27, 1:57 pm, "alexandre.blondin.ma...@gmail.com" > > <alexandre.blondin.ma...@gmail.com> wrote: > > Hi, everybody, > > I'm currently working on algorithms of graph theory and I need one to > > compute a maximum set of independent paths between two vertices, i.e. > > paths using distinct internal vertices. For those who know about this > > theory, it is linked to Menger's Theorem, which is a particular case > > of the Min cut-Max flow Theorem. > > Maybe I didn't look correctly, but it seems that there is nothing > > about that in the Graph library of Sage. Or it is also possible that > > the name is different, since the terminology of graph theory is not > > uniform. Do any of you could tell me about it ? > > Thank you ! > > Alexandre Blondin Massé --~--~---------~--~----~------------~-------~--~----~ To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
