Opened 7 years ago

Closed 7 years ago

#13599 closed defect (fixed)

Bugfix in is_cartesian_product

Reported by: ncohen Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-5.5
Component: graph theory Keywords:
Cc: Merged in: sage-5.5.beta1
Authors: Nathann Cohen Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #13188 Stopgaps:

Description

Helloooooooooo everybody !!!

Georgi Guninski reported by email the following bug :

sage: g = graphs.WagnerGraph()
sage: g.is_cartesian_product()

ValueError: Something weird happened during the algorithm... Please report the bug and give us the graph instance that made it fail !!!

Well, it is not very bad as the is_cartesian_product function is made to return only results that it can check for correction, so an exception is raised when the algorithm sees something wrong.

Anyway. I opened another book which told me what I should add to fix this bug, and the patch that follows fixes it. I'm glad when working on Sage teaches me some graph theory :-)

Nathann

Attachments (1)

trac_13599.patch (10.1 KB) - added by ncohen 7 years ago.

Download all attachments as: .zip

Change History (8)

comment:1 Changed 7 years ago by ncohen

  • Status changed from new to needs_review

comment:2 Changed 7 years ago by dcoudert

  • Reviewers set to David Coudert

The patch is working but you can at least use some {{edge_iterator}} and neighbor_iterator to save some time. I don't know what else could be easily done.

comment:3 Changed 7 years ago by ncohen

Ahahahah. Actually, what I should do is cache the list of edges.. Thanks for the hint ! :-)

g = graphs.RandomGNP(100,.2)
def test(g):
   c = 0
   for u,v in g.edge_iterator(labels = False):
       for uu,vv in g.edge_iterator(labels = False):       
            c += uu+vv+u+v
   return c

def test2(g):
   c = 0
   edges = g.edges(labels = False)
   for i,(u,v) in enumerate(edges):
       for j in range(i+1, len(edges)):
            uu,vv = edges[j]
            c += uu+vv+u+v
   return c

sage: %time test(g)
CPU times: user 4.60 s, sys: 0.00 s, total: 4.60 s
Wall time: 4.60 s
198772752
sage: %time test2(g)
CPU times: user 0.78 s, sys: 0.00 s, total: 0.78 s
Wall time: 0.78 s
99287188

This thing is ..... very ..... slow :-/

Nathann

comment:4 Changed 7 years ago by ncohen

  • Dependencies set to 13188

Btw : this patch now depends on #13188 (a duplicated method is removed), and there is a new keyword "relabeling" to get the final coordinates. This has been requested by email :-P

Nathann

Changed 7 years ago by ncohen

comment:5 Changed 7 years ago by dcoudert

  • Status changed from needs_review to positive_review

The patch is working and is much faster than previous version. Good.

comment:6 Changed 7 years ago by jdemeyer

  • Dependencies changed from 13188 to #13188

comment:7 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.5.beta1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.