Opened 8 years ago

Closed 8 years ago

# Bugfix in is_cartesian_product

Reported by: Owned by: ncohen jason, ncohen, rlm major sage-5.5 graph theory sage-5.5.beta1 Nathann Cohen David Coudert N/A #13188

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

### comment:1 Changed 8 years ago by ncohen

• Status changed from new to needs_review

### comment:2 Changed 8 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 8 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 8 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

### comment:5 Changed 8 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 8 years ago by jdemeyer

• Dependencies changed from 13188 to #13188

### comment:7 Changed 8 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.