Bugfix in is_cartesian_product

[ncohen]

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

[dcoudert]

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.

[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

[ncohen]

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

[dcoudert]

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