#9422: Slightly improving is_forest
----------------------------+-----------------------------------------------
Reporter: ncohen | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-4.5
Component: graph theory | Keywords:
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
----------------------------+-----------------------------------------------
Comment(by ncohen):
Creating a large forest :
{{{
g = graphs.RandomGNP(300,.1)
g = g.subgraph(edges=g.min_spanning_tree())
g.delete_edges([e for e in g.edges() if random()<.5])
sage: g.sparse6_string()
':~?ck_o?gf?mao?_...@_ac?d`g?oe_i@gu?ee?...@gca??gb?[cwqa[bw?ak?wp@aeg...@ge_im_?_a?g?`y@wa_aooacsdhh?qaggc{cwi`aegpds?hw?qcwc_ivocec...@yaw@e_axn?u[_dfoahu?m]?\\fg...@y_??`e?ga_m`o?ggig@`eggy_acobhk?it?ye?i_uagnhwcwric?wgio?yf?a?g?ikeil?]ag...@ir@aloj_yawj_aagak?agf_...@\
k...@kk@jl?qron_a?zx?u?w...@wamg@g...@zf?m{?g_y{oa_q|oo_e~?...@kgbfa_@o...@p??wf_bd?l_re_?pock]?ngocqw?[h?aawe'
}}}
Then using two different versions of is_forest
{{{
sage: %timeit g.is_forest()
125 loops, best of 3: 5.06 ms per loop
sage: %timeit g.is_forest()
5 loops, best of 3: 43.8 ms per loop
}}}
Short and useful... All I love ! :-)
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/9422#comment:2>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
