#18938: Refactor shortest paths
-------------------------------------+-------------------------------------
Reporter: borassi | Owner:
Type: defect | Status: new
Priority: major | Milestone: sage-6.8
Component: graph theory | Resolution:
Keywords: Shortest path, | Merged in:
eccentricity, Dijkstra | Reviewers:
Authors: Michele Borassi | Work issues:
Report Upstream: N/A | Commit:
Branch: | a8d22178cff80ffe9da8d0b46c15ec30fe2d3a87
u/borassi/refactor_shortest_paths | Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by borassi):
Hi!
I tried to address your remarks, and I will upload the new version in a
few moments. I have also started working on the other methods: still, the
code is not clean, so I think you should only review the methods
`shortest_paths` and `check_weight_function` (even if the whole code
should be correct, because all tests are passed).
One question: since most of the arguments are the same for several
routines, is there a way to avoid copy-paste in the documentation?
Thank you very much! Good evening,
Michele
> What's the proposed behavior when by_weight==False?
Added to the documentation
> There is a bidirectional_dijkstra method in
src/sage/graphs/base/c_graph.pyx.
Yes, but there is no "standard" Dijkstra... Maybe, if I have time before
the end of the project, I will add one.
> - !``by_weight!`` - if !``True!``, the graph is considered weighted.
Could you be more specific by saying that the *edges* are considered to be
weighted?
Done
> - Documentation of `algorithm`: could you document the default value and
its
> behaviour?
Done
> - This sounds like a dangerous behaviour:
> {{{``weight_function`` (function) - used only if ``by_weight==True``;}}}
> If somebody calls `g.shortest_paths(v,weight_function=my_function)`, we
know
> for sure that (s)he wants the edges to be considered. Why shouldn't we
define
> `by_weight` to `True` when `weight_function is not None`?
Done
> - Documentation of `weight_function`: here is an attempt at making the
following
> paragraph a bit shorter.
> {{{
> #!diff
> -a function that inputs an edge e and outputs its weight. An edge
> -has the form (u,v,l), where u and v are vertices, l is
> -a label (that can be of any kind). The weight_function can be used
> -to transform the label into a weight. In particular:
> +a function that takes a labelled edge `(u,v,l)` as input and returns
> +its weight. If set to `None` when `by_weight=True`, the label `l` is
> +used as the edge's weight.
> }}}
I have modified heavily the paragraph, taking inspiration from your
proposal.
> The `is_weighted` flag is not used much in Sage, and I believe that it
should
> be removed in the long term:
> - You never know if it is about edge/vertex weights
> - Setting a graph to be "weighted" does not check anything about the
vality of
> weights
> - You may want one function to consider the graph as weighted and not
another
> one. Changing an attribute in between is not pratical, and is actually
> impossible for immutable graphs.
I removed all references to is_weighted: now I just check that the weight
function outputs numbers
> - I do not think necessary to document which exceptions are raised when
the
> input is bad, e.g. conversion to float. Do what you want.
Done!
> - You add many arguments to this function: they should be tested in the
> function's doctest.
Added some doctests.
--
Ticket URL: <http://trac.sagemath.org/ticket/18938#comment:8>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
