Compute the root graph of a graph (inverse of Graph.line_graph)

[ncohen]

I've been willing to write this for aaaaaaaaaaaaaages !!!

Three patches :

• one creates a new module with a lot of doc, and a root_graph function.
• another one moves is_line_graph and line_graph to this new module, and imports them into generic_graph and graph
• another one modifies is_line_graph so that it can also return root graphs.

YeahhhhhhhhhhhhhhhhhhhhhHHH !!

Nathann

Apply:

• trac_13961-new_module.patch​
• trac_13961-move_stuff_around.patch​
• trac_13961-update_is_line_graph.patch​

[ncohen]

Apply trac_13961-new_module.patch, trac_13961-move_stuff_around.patch, trac_13961-update_is_line_graph.patch

[ncohen]

Apply trac_13961-new_module.patch, trac_13961-move_stuff_around.patch, trac_13961-update_is_line_graph.patch

[chapoton]

Hello,

There are a few typos of this kind:

This methods
This modules

[ncohen]

Right, right. I just updated those two, and another docstring which was not sufficiently detailed :-)

Nathann

[dcoudert]

I tried with sage 5.9-beta5 and got a segfault. I will forward you by mail the log message (in case it could be useful).

sage: G = graphs.CompleteGraph(10)
sage: G2 = G.line_graph()
sage: G3 = G2.line_graph()
sage: G4 = G3.line_graph()
sage: G;G2;G3;G4
Complete graph: Graph on 10 vertices
Graph on 45 vertices
Graph on 360 vertices
Graph on 5400 vertices
sage: G.is_isomorphic( root_graph( root_graph( G3 )[0] )[0] )
True
sage: H = root_graph(G4)
.... segfault

[ncohen]

Well, this patch does not contain a line of Cython so it is quite unlikely that it could produce a segfault by itself. The problem most probably comes from subgraph_search, which occasionnally segfaults (it happens to me sometimes when I interrupt it during a computation).

This being said I was not able to reproduce it on my computer.

sage: H = root_graph(G4)
sage:

Nathann

[dcoudert]

The segfault happens in the isomorphism test at the end. I tried to track it back.

Inside the isomorphic function (file sage/groups/perm_gps/partn_ref/refinement_graphs.pyx), it happens during the call to

cdef bint isomorphic = double_coset(<void *>GS1, <void *>GS2, part, ordering, n, &all_children_are_equivalent, &refine_by_degree, &compare_graphs, NULL, NULL, output)

Inside sage/groups/perm_gps/partn_ref/double_coset.pyx:

work_space = allocate_dc_work_space(n)

and inside the SC_new function in sage/groups/perm_gps/partn_ref/data_structures_pyx.pxi, we have:

• an assignment before a NULL test: SC.gen_used.bits[limbs-1] = 0 and SC.gen_is_id.bits[limbs-1] = 0
• a call to the SC_dealloc in which we test if SC.generators is not NULL to dealloc both SC.generators AND SC.gen_inverses. Quite unsafe, no?

At this point I'm no longer able to understand what's going on, but there is a pointer allocation problem somewhere. The call to sage_free(SC.generators[i]) with i=0 fails but that pointer is apparently not NULL. O_o

---

In your code, you should change this:

• "The this is that this implementation" -> "the problem is that this implementation"

[ncohen]

I updated the patch !

Nathann

[dcoudert]

OK, but concerning the problems I have raised, how should I proceed? should I open a new patch with proposed corrections (those I have found) even if it is not sufficient to fix the segfault?

D.

[ncohen]

Yep ! It would be nice if you had a reproducible example of the bug too.

Nathann

[dcoudert]

For me this patch is working properly.

The segfault is reported in patch #14501.