#7571: use more dicts in graph.py
----------------------------+-----------------------------------------------
Reporter: ylchapuy | Owner: rlm
Type: enhancement | Status: new
Priority: major | Milestone: sage-4.3
Component: graph theory | Keywords:
Work_issues: | Author: Yann Laigle-Chapuy
Upstream: N/A | Reviewer:
Merged: |
----------------------------+-----------------------------------------------
Comment(by ylchapuy):
for the record:
Before:
{{{
sage: g=graphs.RandomGNP(10000,.00011)
sage: time g.girth()
CPU times: user 8.19 s, sys: 0.02 s, total: 8.20 s
Wall time: 8.21 s
33
sage: time g.connected_components_number()
CPU times: user 2.06 s, sys: 0.00 s, total: 2.07 s
Wall time: 2.09 s
4474
sage: g=g.connected_components_subgraphs()[0]
sage: len(g)
1784
sage: time b=g.blocks_and_cut_vertices()
CPU times: user 0.28 s, sys: 0.00 s, total: 0.28 s
Wall time: 0.28 s
}}}
After:
{{{
sage: g=graphs.RandomGNP(10000,.00011)
sage: time g.girth()
CPU times: user 5.00 s, sys: 0.00 s, total: 5.00 s
Wall time: 5.00 s
33
sage: time g.connected_components_number()
CPU times: user 0.20 s, sys: 0.00 s, total: 0.20 s
Wall time: 0.20 s
4487
sage: g=g.connected_components_subgraphs()[0]
sage: len(g)
2509
sage: time b=g.blocks_and_cut_vertices()
CPU times: user 0.16 s, sys: 0.00 s, total: 0.16 s
Wall time: 0.16 s
}}}
And more importantly:
{{{
sage: g = graphs.KrackhardtKiteGraph()
sage: g.relabel(map(lambda i: 'x'+str(i),range(len(g))))
}}}
before:
{{{
sage: g.blocks_and_cut_vertices()
([[9, 8], [8, 7], [7, 4, 6, 5, 2, 3, 1, 0]], [8, 7])
}}}
after:
{{{
sage: g.blocks_and_cut_vertices()
([['x9', 'x8'],
['x5', 'x4', 'x1', 'x0', 'x2', 'x3', 'x6', 'x7'],
['x7', 'x8']],
['x8', 'x7'])
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7571#comment:1>
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.
