Opened 8 years ago
Closed 8 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 )
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
andline_graph
to this new module, and imports them intogeneric_graph
andgraph
- another one modifies
is_line_graph
so that it can also return root graphs.
YeahhhhhhhhhhhhhhhhhhhhhHHH !!
Nathann
Apply:
Attachments (3)
Change History (19)
comment:1 Changed 8 years ago by
- Status changed from new to needs_review
comment:2 Changed 8 years ago by
- Dependencies set to #13787
comment:3 Changed 8 years ago by
comment:4 Changed 8 years ago by
- Description modified (diff)
Changed 8 years ago by
comment:5 Changed 8 years ago by
comment:6 Changed 8 years ago by
Apply trac_13961-new_module.patch, trac_13961-move_stuff_around.patch, trac_13961-update_is_line_graph.patch
comment:7 Changed 8 years ago by
Hello,
There are a few typos of this kind:
This methods This modules
Changed 8 years ago by
comment:8 Changed 8 years ago by
Right, right. I just updated those two, and another docstring which was not sufficiently detailed :-)
Nathann
comment:9 Changed 8 years ago by
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
comment:10 Changed 8 years ago by
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
comment:11 Changed 8 years ago by
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
andSC.gen_is_id.bits[limbs-1] = 0
- a call to the
SC_dealloc
in which we test ifSC.generators
is not NULL to dealloc bothSC.generators
ANDSC.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 8 years ago by
I updated the patch !
Nathann
Changed 8 years ago by
comment:13 Changed 8 years ago by
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.
comment:14 Changed 8 years ago by
Yep ! It would be nice if you had a reproducible example of the bug too.
Nathann
comment:15 Changed 8 years ago by
- 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 8 years ago by
- Merged in set to sage-5.10.beta1
- Resolution set to fixed
- Status changed from positive_review to closed
Apply trac_13961-new_module.patch, trac_13961-move_stuff_around.patch, trac_13961-update_is_line_graph.patch