#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 |
-------------------------------------+-------------------------------------
Changes (by dcoudert):
* status: needs_review => needs_work
* milestone: sage-6.8 => sage-6.9
Comment:
Hello,
the output of the method is correct and already faster than networkx on
small graphs. Excellent!
{{{
sage: G = graphs.PetersenGraph()
sage: for u,v,_ in G.edges():
G.set_edge_label(u,v,1)
....:
sage: G.weighted(True)
sage: G.add_vertex(10)
sage: G.shortest_paths(0, by_weight=True, algorithm='Dijkstra_Boost',
check_weight=False)
{0: [0],
1: [0, 1],
2: [0, 1, 2],
3: [0, 4, 3],
4: [0, 4],
5: [0, 5],
6: [0, 1, 6],
7: [0, 5, 7],
8: [0, 5, 8],
9: [0, 4, 9]}
sage: %timeit G.shortest_paths(0, by_weight=True,
algorithm='Dijkstra_Boost', check_weight=False)
10000 loops, best of 3: 74 µs per loop
sage: %timeit G.shortest_paths(0, by_weight=True,
algorithm='Dijkstra_NetworkX', check_weight=False)
The slowest run took 1387.62 times longer than the fastest. This could
mean that an intermediate result is being cached
1 loops, best of 3: 146 µs per loop
sage: %timeit G.shortest_paths(0, by_weight=True,
algorithm='Dijkstra_NetworkX', check_weight=False)
10000 loops, best of 3: 86.7 µs per loop
}}}
do you also plan to add `G.shortest_path()` ?
For all pairs shortest paths:
- we don't have predecessors with `Johnson_Boost`
- distance to unreacheable vertices should be set to +Infinity to be
consistent with other methods.
{{{
sage: dist,pred = G.shortest_path_all_pairs(by_weight=True,
algorithm='Johnson_Boost')
sage: print dist
{0: {0: 0, 1: 1, 2: 2, 3: 2, 4: 1, 5: 1, 6: 2, 7: 2, 8: 2, 9: 2}, 1: {0:
1, 1: 0, 2: 1, 3: 2, 4: 2, 5: 2, 6: 1, 7: 2, 8: 2, 9: 2}, 2: {0: 2, 1: 1,
2: 0, 3: 1, 4: 2, 5: 2, 6: 2, 7: 1, 8: 2, 9: 2}, 3: {0: 2, 1: 2, 2: 1, 3:
0, 4: 1, 5: 2, 6: 2, 7: 2, 8: 1, 9: 2}, 4: {0: 1, 1: 2, 2: 2, 3: 1, 4: 0,
5: 2, 6: 2, 7: 2, 8: 2, 9: 1}, 5: {0: 1, 1: 2, 2: 2, 3: 2, 4: 2, 5: 0, 6:
2, 7: 1, 8: 1, 9: 2}, 6: {0: 2, 1: 1, 2: 2, 3: 2, 4: 2, 5: 2, 6: 0, 7: 2,
8: 1, 9: 1}, 7: {0: 2, 1: 2, 2: 1, 3: 2, 4: 2, 5: 1, 6: 2, 7: 0, 8: 2, 9:
1}, 8: {0: 2, 1: 2, 2: 2, 3: 1, 4: 2, 5: 1, 6: 1, 7: 2, 8: 0, 9: 2}, 9:
{0: 2, 1: 2, 2: 2, 3: 2, 4: 1, 5: 2, 6: 1, 7: 1, 8: 2, 9: 0}, 10: {10: 0}}
sage: print pred
None
sage: dist,pred = G.shortest_path_all_pairs(by_weight=True, algorithm
='Floyd-Warshall-Python')
sage: print dist
{0: {0: 0, 1: 1, 2: 2, 3: 2, 4: 1, 5: 1, 6: 2, 7: 2, 8: 2, 9: 2, 10:
+Infinity}, 1: {0: 1, 1: 0, 2: 1, 3: 2, 4: 2, 5: 2, 6: 1, 7: 2, 8: 2, 9:
2, 10: +Infinity}, 2: {0: 2, 1: 1, 2: 0, 3: 1, 4: 2, 5: 2, 6: 2, 7: 1, 8:
2, 9: 2, 10: +Infinity}, 3: {0: 2, 1: 2, 2: 1, 3: 0, 4: 1, 5: 2, 6: 2, 7:
2, 8: 1, 9: 2, 10: +Infinity}, 4: {0: 1, 1: 2, 2: 2, 3: 1, 4: 0, 5: 2, 6:
2, 7: 2, 8: 2, 9: 1, 10: +Infinity}, 5: {0: 1, 1: 2, 2: 2, 3: 2, 4: 2, 5:
0, 6: 2, 7: 1, 8: 1, 9: 2, 10: +Infinity}, 6: {0: 2, 1: 1, 2: 2, 3: 2, 4:
2, 5: 2, 6: 0, 7: 2, 8: 1, 9: 1, 10: +Infinity}, 7: {0: 2, 1: 2, 2: 1, 3:
2, 4: 2, 5: 1, 6: 2, 7: 0, 8: 2, 9: 1, 10: +Infinity}, 8: {0: 2, 1: 2, 2:
2, 3: 1, 4: 2, 5: 1, 6: 1, 7: 2, 8: 0, 9: 2, 10: +Infinity}, 9: {0: 2, 1:
2, 2: 2, 3: 2, 4: 1, 5: 2, 6: 1, 7: 1, 8: 2, 9: 0, 10: +Infinity}, 10: {0:
+Infinity, 1: +Infinity, 2: +Infinity, 3: +Infinity, 4: +Infinity, 5:
+Infinity, 6: +Infinity, 7: +Infinity, 8: +Infinity, 9: +Infinity, 10: 0}}
sage: print pred
{0: {0: None, 1: 0, 2: 1, 3: 4, 4: 0, 5: 0, 6: 1, 7: 5, 8: 5, 9: 4, 10:
None}, 1: {0: 1, 1: None, 2: 1, 3: 2, 4: 0, 5: 0, 6: 1, 7: 2, 8: 6, 9: 6,
10: None}, 2: {0: 1, 1: 2, 2: None, 3: 2, 4: 3, 5: 7, 6: 1, 7: 2, 8: 3, 9:
7, 10: None}, 3: {0: 4, 1: 2, 2: 3, 3: None, 4: 3, 5: 8, 6: 8, 7: 2, 8: 3,
9: 4, 10: None}, 4: {0: 4, 1: 0, 2: 3, 3: 4, 4: None, 5: 0, 6: 9, 7: 9, 8:
3, 9: 4, 10: None}, 5: {0: 5, 1: 0, 2: 7, 3: 8, 4: 0, 5: None, 6: 8, 7: 5,
8: 5, 9: 7, 10: None}, 6: {0: 1, 1: 6, 2: 1, 3: 8, 4: 9, 5: 8, 6: None, 7:
9, 8: 6, 9: 6, 10: None}, 7: {0: 5, 1: 2, 2: 7, 3: 2, 4: 9, 5: 7, 6: 9, 7:
None, 8: 5, 9: 7, 10: None}, 8: {0: 5, 1: 6, 2: 3, 3: 8, 4: 3, 5: 8, 6: 8,
7: 5, 8: None, 9: 6, 10: None}, 9: {0: 4, 1: 6, 2: 7, 3: 4, 4: 9, 5: 7, 6:
9, 7: 9, 8: 6, 9: None, 10: None}, 10: {0: None, 1: None, 2: None, 3:
None, 4: None, 5: None, 6: None, 7: None, 8: None, 9: None, 10: None}}
sage: dist,pred = G.shortest_path_all_pairs()
sage: print dist
{0: {0: 0, 1: 1, 2: 2, 3: 2, 4: 1, 5: 1, 6: 2, 7: 2, 8: 2, 9: 2, 10:
+Infinity}, 1: {0: 1, 1: 0, 2: 1, 3: 2, 4: 2, 5: 2, 6: 1, 7: 2, 8: 2, 9:
2, 10: +Infinity}, 2: {0: 2, 1: 1, 2: 0, 3: 1, 4: 2, 5: 2, 6: 2, 7: 1, 8:
2, 9: 2, 10: +Infinity}, 3: {0: 2, 1: 2, 2: 1, 3: 0, 4: 1, 5: 2, 6: 2, 7:
2, 8: 1, 9: 2, 10: +Infinity}, 4: {0: 1, 1: 2, 2: 2, 3: 1, 4: 0, 5: 2, 6:
2, 7: 2, 8: 2, 9: 1, 10: +Infinity}, 5: {0: 1, 1: 2, 2: 2, 3: 2, 4: 2, 5:
0, 6: 2, 7: 1, 8: 1, 9: 2, 10: +Infinity}, 6: {0: 2, 1: 1, 2: 2, 3: 2, 4:
2, 5: 2, 6: 0, 7: 2, 8: 1, 9: 1, 10: +Infinity}, 7: {0: 2, 1: 2, 2: 1, 3:
2, 4: 2, 5: 1, 6: 2, 7: 0, 8: 2, 9: 1, 10: +Infinity}, 8: {0: 2, 1: 2, 2:
2, 3: 1, 4: 2, 5: 1, 6: 1, 7: 2, 8: 0, 9: 2, 10: +Infinity}, 9: {0: 2, 1:
2, 2: 2, 3: 2, 4: 1, 5: 2, 6: 1, 7: 1, 8: 2, 9: 0, 10: +Infinity}, 10: {0:
+Infinity, 1: +Infinity, 2: +Infinity, 3: +Infinity, 4: +Infinity, 5:
+Infinity, 6: +Infinity, 7: +Infinity, 8: +Infinity, 9: +Infinity, 10: 0}}
sage: print pred
{0: {0: None, 1: 0, 2: 1, 3: 4, 4: 0, 5: 0, 6: 1, 7: 5, 8: 5, 9: 4, 10:
None}, 1: {0: 1, 1: None, 2: 1, 3: 2, 4: 0, 5: 0, 6: 1, 7: 2, 8: 6, 9: 6,
10: None}, 2: {0: 1, 1: 2, 2: None, 3: 2, 4: 3, 5: 7, 6: 1, 7: 2, 8: 3, 9:
7, 10: None}, 3: {0: 4, 1: 2, 2: 3, 3: None, 4: 3, 5: 8, 6: 8, 7: 2, 8: 3,
9: 4, 10: None}, 4: {0: 4, 1: 0, 2: 3, 3: 4, 4: None, 5: 0, 6: 9, 7: 9, 8:
3, 9: 4, 10: None}, 5: {0: 5, 1: 0, 2: 7, 3: 8, 4: 0, 5: None, 6: 8, 7: 5,
8: 5, 9: 7, 10: None}, 6: {0: 1, 1: 6, 2: 1, 3: 8, 4: 9, 5: 8, 6: None, 7:
9, 8: 6, 9: 6, 10: None}, 7: {0: 5, 1: 2, 2: 7, 3: 2, 4: 9, 5: 7, 6: 9, 7:
None, 8: 5, 9: 7, 10: None}, 8: {0: 5, 1: 6, 2: 3, 3: 8, 4: 3, 5: 8, 6: 8,
7: 5, 8: None, 9: 6, 10: None}, 9: {0: 4, 1: 6, 2: 7, 3: 4, 4: 9, 5: 7, 6:
9, 7: 9, 8: 6, 9: None, 10: None}, 10: {0: None, 1: None, 2: None, 3:
None, 4: None, 5: None, 6: None, 7: None, 8: None, 9: None, 10: None}}
}}}
Best,
David.
--
Ticket URL: <http://trac.sagemath.org/ticket/18931#comment:5>
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.
