Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

improve has_multiple_edges #7547

Closed
sagetrac-ylchapuy mannequin opened this issue Nov 28, 2009 · 9 comments
Closed

improve has_multiple_edges #7547

sagetrac-ylchapuy mannequin opened this issue Nov 28, 2009 · 9 comments
Assignees
@rlmill
Labels
c: graph theory p: major / 3 t: enhancement
Milestone
sage-4.3

Comments

@sagetrac-ylchapuy
Copy link
Mannequin

sagetrac-ylchapuy mannequin commented Nov 28, 2009

This patch cuts down by 30% the time for sage -t graph.py on my machine... (and doctests of course still pass)

CC: @nathanncohen

Component: graph theory

Author: Yann Laigle-Chapuy

Reviewer: Robert Miller

Merged: sage-4.3.alpha1

Issue created by migration from https://trac.sagemath.org/ticket/7547
@sagetrac-ylchapuy sagetrac-ylchapuy mannequin added this to the sage-4.3 milestone Nov 28, 2009
@sagetrac-ylchapuy

This comment has been minimized.

Sign in to view
@sagetrac-ylchapuy
Copy link
Mannequin Author

sagetrac-ylchapuy mannequin commented Nov 28, 2009

comment:1

For the record:

sage: P = graphs.PetersenGraph()
sage: D = graphs.DodecahedralGraph()
sage: L = D.lexicographic_product(P) 
sage: L.allow_multiple_edges(True)
sage: time L.has_multiple_edges()

Before: Wall time: 39.56 s

After: Wall time: 19.32 s

I hope I did no mistake, it's 4 a.m here...

@rlmill
Copy link
Mannequin

rlmill mannequin commented Nov 28, 2009

comment:2

Nice work!

@nathanncohen
Copy link
Mannequin

nathanncohen mannequin commented Nov 28, 2009

comment:3

Well done !! :-)

Nathann

@sagetrac-ylchapuy
Copy link
Mannequin Author

sagetrac-ylchapuy mannequin commented Nov 28, 2009

comment:4

Sorry to give myself a "needs work" but my ideas are much clearer this morning.
New patch to come in a few minutes!

@sagetrac-ylchapuy
Copy link
Mannequin Author

sagetrac-ylchapuy mannequin commented Nov 28, 2009

based on 4.3.alpha0

@sagetrac-ylchapuy
Copy link
Mannequin Author

sagetrac-ylchapuy mannequin commented Nov 28, 2009

comment:5

Attachment: trac_7547-has_multiple_edges.patch.gz

New timing for the same test: 1.22s. It's useful to sleep!

@mwhansen
Copy link
Contributor

Merged: sage-4.3.alpha1

@mwhansen
Copy link
Contributor

Reviewer: Robert Miller

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@rlmill rlmill

Labels
c: graph theory p: major / 3 t: enhancement
Projects
None yet
Milestone
sage-4.3
Development

No branches or pull requests
1 participant
@mwhansen