Opened 6 years ago
Closed 6 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)
Change History (8)
comment:1 Changed 6 years ago by
- Status changed from new to needs_review
comment:2 Changed 6 years ago by
- Reviewers set to David Coudert
comment:3 Changed 6 years ago by
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 6 years ago by
- 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 6 years ago by
comment:5 Changed 6 years ago by
- Status changed from needs_review to positive_review
The patch is working and is much faster than previous version. Good.
comment:6 Changed 6 years ago by
- Dependencies changed from 13188 to #13188
comment:7 Changed 6 years ago by
- Merged in set to sage-5.5.beta1
- Resolution set to fixed
- Status changed from positive_review to closed
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.