#18931: Boost shortest paths
-------------------------------------+-------------------------------------
Reporter: borassi | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.8
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 |
-------------------------------------+-------------------------------------
Changes (by borassi):
* status: new => needs_review
* cc: ncohen, dcoudert (added)
* dependencies: #18910 => #18910, #18938
* commit: => 4897c8e27daa7c7939827524bec312ff8f39b3b7
Old description:
> Use Boost algorithms to compute shortest paths in graphs with negative
> weights. To compute all shortest paths from a given vertex v, we use
> Bellman-Ford algorithm, while to compute the shortest path between each
> pair of vertices we use Johnson algorithm.
>
> The complexity of both algorithms is quadratic (apart from logarithmic
> factors): hence, the graph conversion overhead is negligible.
New description:
Use Boost algorithms to compute shortest paths in weighted graphs. If all
weights are positive, we use Dijkstra algorithm, while if there are
negative weights, we use Bellman-Ford if the starting vertex is fixed,
Johnson otherwise.
The complexity of Bellman-Ford and Johnson algorithms is quadratic (apart
from logarithmic factors): hence, the graph conversion overhead is
negligible. The Dijkstra algorithm is still more efficient than the
NetworkX implementation, even if the graph conversion overhead is not
negligible.
--
Comment:
Hello!
This is my first attempt to include Boost shortest paths. Some benchmark:
{{{
sage: def random_weighted_graph(n, m, lower_weight = 1, upper_weight =
100):
import random
g = graphs.RandomGNM(n,m)
weights = [random.randint(lower_weight, upper_weight) for r in
xrange(m)]
uw_edges = g.edges()
w_edges = [(uw_edges[i][0], uw_edges[i][1], weights[i]) for i in
xrange(m)]
return Graph(w_edges, weighted = True)
....:
sage: g = random_weighted_graph(30000,120000)
sage: %timeit g.shortest_paths(0, by_weight=True,
algorithm='Dijkstra_Boost', check_weight=False)
1 loops, best of 3: 304 ms per loop
sage: %timeit g.shortest_paths(0, by_weight=True,
algorithm='Dijkstra_NetworkX', check_weight=False)
1 loops, best of 3: 792 ms per loop
sage: g = random_weighted_graph(10000,300000)
sage: %timeit g.shortest_paths(0, by_weight=True,
algorithm='Dijkstra_Boost', check_weight=False)
1 loops, best of 3: 333 ms per loop
sage: %timeit g.shortest_paths(0, by_weight=True,
algorithm='Dijkstra_NetworkX', check_weight=False)
1 loops, best of 3: 1.36 s per loop
sage: %timeit g.shortest_path_all_pairs(by_weight=True,
algorithm='Johnson_Boost')
10 loops, best of 3: 21.6 ms per loop
sage: %timeit g.shortest_path_all_pairs(by_weight=True, algorithm='Floyd-
Warshall-Python')
1 loops, best of 3: 5.46 s per loop
}}}
We have a slight improvement with Dijkstra (2-3x), and we have an enormous
improvement in computing the all-pairs-shortest-path.
Let me know if you like it!
Thank you very much,
Michele
--
Ticket URL: <http://trac.sagemath.org/ticket/18931#comment:4>
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.
