#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: Nathann Cohen
Authors: David Coudert | Merged in:
Dependencies: | Stopgaps:
-----------------------------------------+----------------------------------
Comment (by ncohen):
Hello !!!
> Well, for vertex-disjoint paths the current implementation is valid. So
we have to fix the edge-disjoint case. I'm able to fix it for the
suurballe_tarjan method, but the behavior of the edge_disjoint_paths
method is different (multiple edges not taken into account I suppose).
Indeed.
{{{
sage: g.vertices()
[0, 1]
sage: g.edges()
[(0, 1, None), (0, 1, None)]
sage: g.edge_disjoint_paths(0,1)
[[0, 1]]
}}}
Honestly I would sleep much better if those functions return raised an
exception on graphs with multiple edges. Dealing with those is a waste of
computations on the usual cases, and it will add scores of stupid "if" in
the code. I hate this `-_-`
> Well, it depends on the situation. Sometimes you have several labels per
edge stored in a dictionary, or you have only one numerical value. We need
at least 2 ways to store edge data.
> Now I agree that I was a bit extreme in the options offered to the user
(but strings were useful for Kautz :-P ).
>
> I can certainly reduce, but which are the options to keep ?
Well.. All other graphs methods just accept as input a edge whose label is
a weight.. Why would we need anything else ?
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13380#comment:6>
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.
