#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 ncohen):
Hellooooooooooooooo Michele,
Several remarks on your branch:
- {{{``by_weight`` - if ``True``, the graph is considered weighted.}}}
Could you
be more specific by saying that the *edges* are considered to be
weighted?
- Documentation of {{{algorithm}}}: could you document the default value
and its
behaviour?
- 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`?
- 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.
}}}
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 do not think necessary to document which exceptions are raised when
the
input is bad, e.g. conversion to float. Do what you want.
- You add many arguments to this function: they should be tested in the
function's doctest.
Good evening,
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/18938#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 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.
