#13906: Segmentation fault in subgraph_search
----------------------------------+-----------------------------------------
Reporter: azi | Owner: jason, ncohen, rlm
Type: defect | Status: positive_review
Priority: critical | Milestone: sage-5.7
Component: graph theory | Resolution:
Keywords: | Work issues:
Report Upstream: N/A | Reviewers: Nathann Cohen
Authors: Jernej Azarija | Merged in:
Dependencies: | Stopgaps:
----------------------------------+-----------------------------------------
Changes (by jdemeyer):
* milestone: sage-5.6 => sage-5.7
Old description:
> A very weird thing happens when you start searching for the obvious. If
> one uses subgraph_search on a single vertex, the function (oddly???)
> works at times and segfaults at others. The segfault happens arbitrarily.
>
> {{{
> sage: G = graphs.RandomBarabasiAlbert(100,2)
> sage: G.subgraph_search(graphs.CompleteGraph(1))
> Subgraph of (): Graph on 1 vertex
> sage: G.subgraph_search(graphs.CompleteGraph(1))
> ---------------------------------------------------------------------------
> RuntimeError Traceback (most recent call
> last)
>
> /home/azi/moreMoore/<ipython console> in <module>()
>
> /home/azi/sage-5.5.rc0/local/lib/python2.7/site-
> packages/sage/graphs/generic_graph.pyc in subgraph_search(self, G,
> induced)
> 10245 S = SubgraphSearch(self, G, induced = induced)
> 10246
> > 10247 for g in S:
> 10248 if induced:
> 10249 return self.subgraph(g)
>
> /home/azi/sage-5.5.rc0/local/lib/python2.7/site-
> packages/sage/graphs/generic_graph_pyx.so in
> sage.graphs.generic_graph_pyx.SubgraphSearch.__next__
> (sage/graphs/generic_graph_pyx.c:5897)()
>
> RuntimeError: Segmentation fault
> sage: G.subgraph_search(graphs.CompleteGraph(1))
> ---------------------------------------------------------------------------
> RuntimeError Traceback (most recent call
> last)
>
> /home/azi/moreMoore/<ipython console> in <module>()
>
> /home/azi/sage-5.5.rc0/local/lib/python2.7/site-
> packages/sage/graphs/generic_graph.pyc in subgraph_search(self, G,
> induced)
> 10245 S = SubgraphSearch(self, G, induced = induced)
> 10246
> > 10247 for g in S:
> 10248 if induced:
> 10249 return self.subgraph(g)
>
> /home/azi/sage-5.5.rc0/local/lib/python2.7/site-
> packages/sage/graphs/generic_graph_pyx.so in
> sage.graphs.generic_graph_pyx.SubgraphSearch.__next__
> (sage/graphs/generic_graph_pyx.c:5897)()
>
> RuntimeError: Segmentation fault
> sage: G.subgraph_search(graphs.CompleteGraph(1))
> Subgraph of (): Graph on 1 vertex
> sage: G.subgraph_search(graphs.CompleteGraph(1))
> Subgraph of (): Graph on 1 vertex
> sage: G.subgraph_search(graphs.CompleteGraph(1))
> ---------------------------------------------------------------------------
> RuntimeError Traceback (most recent call
> last)
>
> /home/azi/moreMoore/<ipython console> in <module>()
>
> /home/azi/sage-5.5.rc0/local/lib/python2.7/site-
> packages/sage/graphs/generic_graph.pyc in subgraph_search(self, G,
> induced)
> 10245 S = SubgraphSearch(self, G, induced = induced)
> 10246
> > 10247 for g in S:
> 10248 if induced:
> 10249 return self.subgraph(g)
>
> /home/azi/sage-5.5.rc0/local/lib/python2.7/site-
> packages/sage/graphs/generic_graph_pyx.so in
> sage.graphs.generic_graph_pyx.SubgraphSearch.__next__
> (sage/graphs/generic_graph_pyx.c:5897)()
>
> RuntimeError: Segmentation fault
> }}}
New description:
A very weird thing happens when you start searching for the obvious. If
one uses subgraph_search on a single vertex, the function (oddly???) works
at times and segfaults at others. The segfault happens arbitrarily.
{{{
sage: G = graphs.RandomBarabasiAlbert(100,2)
sage: G.subgraph_search(graphs.CompleteGraph(1))
Subgraph of (): Graph on 1 vertex
sage: G.subgraph_search(graphs.CompleteGraph(1))
---------------------------------------------------------------------------
RuntimeError Traceback (most recent call
last)
/home/azi/moreMoore/<ipython console> in <module>()
/home/azi/sage-5.5.rc0/local/lib/python2.7/site-
packages/sage/graphs/generic_graph.pyc in subgraph_search(self, G,
induced)
10245 S = SubgraphSearch(self, G, induced = induced)
10246
> 10247 for g in S:
10248 if induced:
10249 return self.subgraph(g)
/home/azi/sage-5.5.rc0/local/lib/python2.7/site-
packages/sage/graphs/generic_graph_pyx.so in
sage.graphs.generic_graph_pyx.SubgraphSearch.__next__
(sage/graphs/generic_graph_pyx.c:5897)()
RuntimeError: Segmentation fault
sage: G.subgraph_search(graphs.CompleteGraph(1))
---------------------------------------------------------------------------
RuntimeError Traceback (most recent call
last)
/home/azi/moreMoore/<ipython console> in <module>()
/home/azi/sage-5.5.rc0/local/lib/python2.7/site-
packages/sage/graphs/generic_graph.pyc in subgraph_search(self, G,
induced)
10245 S = SubgraphSearch(self, G, induced = induced)
10246
> 10247 for g in S:
10248 if induced:
10249 return self.subgraph(g)
/home/azi/sage-5.5.rc0/local/lib/python2.7/site-
packages/sage/graphs/generic_graph_pyx.so in
sage.graphs.generic_graph_pyx.SubgraphSearch.__next__
(sage/graphs/generic_graph_pyx.c:5897)()
RuntimeError: Segmentation fault
sage: G.subgraph_search(graphs.CompleteGraph(1))
Subgraph of (): Graph on 1 vertex
sage: G.subgraph_search(graphs.CompleteGraph(1))
Subgraph of (): Graph on 1 vertex
sage: G.subgraph_search(graphs.CompleteGraph(1))
---------------------------------------------------------------------------
RuntimeError Traceback (most recent call
last)
/home/azi/moreMoore/<ipython console> in <module>()
/home/azi/sage-5.5.rc0/local/lib/python2.7/site-
packages/sage/graphs/generic_graph.pyc in subgraph_search(self, G,
induced)
10245 S = SubgraphSearch(self, G, induced = induced)
10246
> 10247 for g in S:
10248 if induced:
10249 return self.subgraph(g)
/home/azi/sage-5.5.rc0/local/lib/python2.7/site-
packages/sage/graphs/generic_graph_pyx.so in
sage.graphs.generic_graph_pyx.SubgraphSearch.__next__
(sage/graphs/generic_graph_pyx.c:5897)()
RuntimeError: Segmentation fault
}}}
'''Apply''' [attachment:trac_13906_subgraph_search_K1.patch],
[attachment:trac_13906-rev.patch]
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13906#comment:22>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
