Opened 13 years ago

Closed 13 years ago

#7547 closed enhancement (fixed)

improve has_multiple_edges

Reported by: ylchapuy Owned by: rlm
Priority: major Milestone: sage-4.3
Component: graph theory Keywords:
Cc: ncohen Merged in: sage-4.3.alpha1
Authors: Yann Laigle-Chapuy Reviewers: Robert Miller
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by ylchapuy)

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

Attachments (1)

trac_7547-has_multiple_edges.patch (2.3 KB) - added by ylchapuy 13 years ago.
based on 4.3.alpha0

Download all attachments as: .zip

Change History (8)

comment:1 Changed 13 years ago by ylchapuy

  • Cc ncohen added
  • Description modified (diff)
  • Status changed from new to needs_review

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...

comment:2 Changed 13 years ago by rlm

  • Status changed from needs_review to positive_review

Nice work!

comment:3 Changed 13 years ago by ncohen

Well done !! :-)

Nathann

comment:4 Changed 13 years ago by ylchapuy

  • Status changed from positive_review to needs_work

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

Changed 13 years ago by ylchapuy

based on 4.3.alpha0

comment:5 Changed 13 years ago by ylchapuy

  • Status changed from needs_work to needs_review

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

comment:6 Changed 13 years ago by rlm

  • Status changed from needs_review to positive_review

comment:7 Changed 13 years ago by mhansen

  • Merged in set to sage-4.3.alpha1
  • Resolution set to fixed
  • Reviewers set to Robert Miller
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.