#18910: Boost minimum spanning tree
-------------------------------------+-------------------------------------
Reporter: borassi | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-6.8
Component: graph theory | Resolution:
Keywords: Boost, minimum | Merged in:
spanning tree | Reviewers:
Authors: Michele Borassi | Work issues:
Report Upstream: N/A | Commit:
Branch: | 8278b0bf8b3b4c86bdc5b543f5ca57c8b682f83a
u/borassi/boost_minimum_spanning_tree| Stopgaps:
Dependencies: #18876, #18906 |
-------------------------------------+-------------------------------------
Changes (by borassi):
* commit: => 8278b0bf8b3b4c86bdc5b543f5ca57c8b682f83a
Comment:
Hello!
This is the first version of Boost minimum spanning tree. With this code,
I'm inserting in Sage the code to interface with Boost weighted graphs.
The improvement on this specific algorithm is not striking (about 2x over
the old algorithm), but I still set the Boost algorithm as default.
Some benchmark:
{{{
sage: sage: def random_weighted_graph(n, m, lower_weight = 1, upper_weight
= 100):
import random
g = graphs.RandomGNM(n,m)
m = g.num_edges()
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(20000,200000)
sage: %timeit(g.min_spanning_tree(algorithm="Prim_Boost"))
1 loops, best of 3: 279 ms per loop
sage: %timeit(g.min_spanning_tree(algorithm="Kruskal_Boost"))
1 loops, best of 3: 361 ms per loop
sage: %timeit(g.min_spanning_tree(algorithm="Kruskal"))
1 loops, best of 3: 492 ms per loop
sage: %timeit(g.min_spanning_tree(algorithm="NetworkX"))
1 loops, best of 3: 1.92 s per loop
sage: %timeit(g.min_spanning_tree(algorithm="Prim_edge"))
1 loops, best of 3: 17.3 s per loop
sage: %timeit(g.min_spanning_tree(algorithm="Prim_fringe"))
1 loops, best of 3: 36.1 s per loop
}}}
Hope you like it!
Michele
--
Ticket URL: <http://trac.sagemath.org/ticket/18910#comment:3>
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.
