Opened 6 years ago

Closed 6 years ago

#13961 closed enhancement (fixed)

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

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

Description (last modified by 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 !!



Attachments (3)

trac_13961-move_stuff_around.patch (17.5 KB) - added by ncohen 6 years ago.
trac_13961-update_is_line_graph.patch (6.0 KB) - added by ncohen 6 years ago.
trac_13961-new_module.patch (16.0 KB) - added by ncohen 6 years ago.

Download all attachments as: .zip

Change History (19)

comment:1 Changed 6 years ago by ncohen

  • Status changed from new to needs_review

comment:2 Changed 6 years ago by ncohen

  • Dependencies set to #13787

comment:3 Changed 6 years ago by ncohen

Last edited 6 years ago by ncohen (previous) (diff)

comment:4 Changed 6 years ago by ncohen

  • Description modified (diff)

Changed 6 years ago by ncohen

comment:5 Changed 6 years ago by ncohen

Last edited 6 years ago by ncohen (previous) (diff)

comment:6 Changed 6 years ago by ncohen

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

comment:7 Changed 6 years ago by chapoton


There are a few typos of this kind:

This methods
This modules

Changed 6 years ago by ncohen

comment:8 Changed 6 years ago by ncohen

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


comment:9 Changed 6 years ago by 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] )
sage: H = root_graph(G4)
.... segfault

comment:10 Changed 6 years ago by 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)


comment:11 Changed 6 years ago by 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"

comment:12 Changed 6 years ago by ncohen

I updated the patch !


Changed 6 years ago by ncohen

comment:13 Changed 6 years ago by 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?


comment:14 Changed 6 years ago by ncohen

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


comment:15 Changed 6 years ago by dcoudert

  • Reviewers set to David Coudert
  • Status changed from needs_review to positive_review

For me this patch is working properly.

The segfault is reported in patch #14501.

comment:16 Changed 6 years ago by jdemeyer

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