#13380: Suurballe-Tarjan algorithm for pair of disjoint st-paths
-----------------------------------------+----------------------------------
Reporter: dcoudert | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_info
Priority: major | Milestone: sage-5.6
Component: graph theory | Resolution:
Keywords: graph, disjoint paths | Work issues:
Report Upstream: N/A | Reviewers:
Authors: David Coudert | Merged in:
Dependencies: | Stopgaps:
-----------------------------------------+----------------------------------
Changes (by ncohen):
* status: needs_review => needs_info
Comment:
Helloooooo David !!!
* > This method is designed for simple (Di)Graph. If the input (Di)Graph
has multiple edges, this method uses only the edge of minimum weight.
This is not a good solution, for maybe the two paths giving the shortest
length need both edges. If this cannot be fixed, it is safer to refuse
graphs with multiple edges.
* A big block of the code is dedicated to the many ways input may be
formatted. I think that it's really going too far, especially when it's
only done in this function and no other. Perhaps we should try to define a
general way to deal with this in the graphs methods, but honestly when
input is just "a numerical value per edge", what is wrong with asking the
user to put those values on the edges ? If the user cannot convert strings
to integers before giving his graph to a flow function, he does not
deserve to solve a flow problem `:-P`
* You added a call to _suurballe_tarjan in many functions, among other
disjoint_routed_paths. It breaks things : in particular,
`[self.subgraph(p1), self.subgraph(p2)] if p1 and p2 else [] ` return the
two graphs induced by the vertices of the irst path, and the vertices of
the second paths. There is no reason why these graphs should be induced
paths, and the user would not know what to make of the output unless each
graph is a path. Actually, the first graph is a shortest path, so this one
at least would be induced.... Unless the graph is weighted. Anyway, the
proper behaviour is to call vertex_disjoint_paths (which will call your
algorithm later).
{{{
show(graphs.PetersenGraph().disjoint_routed_paths([(0,1)]*2))
}}}
* You added in edge_disjoint_paths and vertex_disjoint_paths a parameter
`k` indicating "the maximum number of paths to return". Considering how it
is implemented (Sage actually solves the max flow problem without taking k
into account), I don't really see the point as it's more or less the same
amount of work that Sage has to do whether k is defined or not. If it made
sense somehow, what about setting k to be *the (exact) number of paths to
return* ? I can think of many cases when I would need to get k paths
between two vertices, but much fewer where I would need to have "anything
between 0 and k". And I would prefer to have them all if there is no
difference in the running time anyway.
* By the way, it is nice to advertise your algorithm but let's write
something clean : you test whether you can solve the problem with your new
input parameter k=2, and if it does not work just run the former
algorithm. Well, if it does not work it means that the graphs is not
2-connected, so you can immediately return a shortest path or say that the
graph is disconnected. ou alrady obtained an information that can be put
to good use. But then it depends on what k is in the end : the "maximum"
number of disjoint paths, or the exact number.
* There is a problem with `vertex_disjoint_path` which I just noticed, but
it existed before your patch. Actually, your patch slightly improved it,
for it was an infinite loop which became "an incoherent result"
{{{
sage: graphs.PetersenGraph().vertex_disjoint_paths(0,1)
[[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1],
[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1]]
}}}
The attached patch fixes some of the above, and other details too..
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13380#comment:3>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
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-trac?hl=en.
