#18931: Boost shortest paths
-------------------------------------+-------------------------------------
Reporter: borassi | Owner:
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-6.9
Component: graph theory | Resolution:
Keywords: Boost, shortest | Merged in:
paths, Bellman-Ford, Johnson | Reviewers:
Authors: Michele Borassi | Work issues:
Report Upstream: N/A | Commit:
Branch: | 4897c8e27daa7c7939827524bec312ff8f39b3b7
u/borassi/boost_shortest_paths | Stopgaps:
Dependencies: #18910, #18938 |
-------------------------------------+-------------------------------------
Comment (by borassi):
Hello!
Thank you very much for your comments. I think we should discuss some
issues, and I would like to hear also Nathann's opinion, because I think
shortest paths are very important.
In the following, I tried to support the choices I made in the version of
the code that will soon be uploaded: feel free to disagree!
Best,
Michele
Replying to [comment:5 dcoudert]:
> Hello,
>
> the output of the method is correct and already faster than networkx on
small graphs. Excellent!
:)
> do you also plan to add `G.shortest_path()` ?
Ups, you are right. I am quite sure that the bidirectional Dijkstra that
is already implemented is better than Boost Dijkstra algorithm (hence, I
did not include it), but I did not think that we may add an algorithm that
works with negative weights.
Now I have done it! However, I still have doubts on what happens if we run
Dijkstra with negative weights. Before this patch, the result was
completely unreliable:
{{{
sage: G = DiGraph([(0,1,1),(1,2,1),(0,3,1000),(3,4,-3000), (4,2,1000)])
sage: G.shortest_path_length(0, 2, by_weight=True, algorithm='Bellman-
Ford_Boost')
-1000
sage: G.shortest_path_length(0, 2, by_weight=True)
2
}}}
However, reading all edges to check if there are negative weights may
increase drastically the running-time, since the algorithm is sublinear.
Hence, I just added a note and two examples to show the issue. Moreover,
now, if Dijkstra algorithm finds an edge with negative weight, an error is
raised (however, if the error is not raised, it doesn't mean that the path
is correct, as shown by the previous example). Do you think it is a good
solution?
> For all pairs shortest paths:
> - we don't have predecessors with `Johnson_Boost`
Yes, it is documented in the OUTPUT section of the documentation.
Unfortunately Boost does not have this feature, and recomputing
predecessors from distances is too time-consuming. For this reason, I
still use Floyd-Warshall algorithm as default, and I use the faster
Johnson algorithm only if paths are not needed (for instance, when
computing eccentricities).
> - distance to unreacheable vertices should be set to +Infinity to be
consistent with other methods.
I think we should discuss a bit more this point. My proposal is to do the
converse, that is, to remove from dictionaries all unreachable vertices:
this is what I have done in this commit. I have some reasons to support
this solution: please, let me know if you think they are sufficient!
First of all, this task is memory-consuming, and saving memory for graphs
which are not connected might be a good choice. Also the running-time is
decreased, and the code is simplified. Furthermore, before, the
predecessor of the starting vertex (None) was the same as the predecessor
of unreachable vertices. This might be unwanted, if the user writes
something like:
{{{
distance_v_w = 0
while pred[w] is not None:
distance_v_w = distance_v_w + 1
w = pred[w]
}}}
With this code, the distance from an unreachable vertex is 0 (while I
think we should distinguish between "I have already reached the starting
vertex" and "I cannot reach the starting vertex").
Moreover, the `shortest_paths` and `shortest_path_lengths` routines
already follow this policy: adapting the `shortest_path_all_pairs` routine
is good for consistency, to simplify the code and to reduce the running-
time when `shortest_path_all_pairs` calls `shortest_paths`. Finally, one
might easily imitate the other behavior by writing `d[v].get(w,Infinity)`
instead of `d[v][w]`.
--
Ticket URL: <http://trac.sagemath.org/ticket/18931#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.
