Re: [boost] [Graph] component_index crash on big graph

Subject: Re: [boost] [Graph] component_index crash on big graph
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2009-07-07 10:27:08

On Tue, 7 Jul 2009, Sandeep Gupta wrote:

> On Tue, Jul 7, 2009 at 4:40 AM, Andrew Sutton <andrew.n.sutton_at_[hidden]>wrote:
>
>>>
>>>  I am using the incremental connected component + component_index to find
>>> connected components in an undirected graph. However the program works
>> fine
>>> on small small dataset but segfaults on large input. I tried to do some
>>> debugging and the best I could come up was that it fails  on
>>> array_push_front cal at the
>>> boost/graph/detail/incremental_component.hpp:78.
>>>
>>
>> It doesn't appear as though you have allocated any vertices for the graph.
>> I'm pretty sure that add_edge does not allocate new vertices.
>>
>> I would guess that every time you call add_vertex, you are referencing data
>> that doesn't actually exist. The successful run may be attributed to a)
>> that
>> the default constructor for the graph (or vector) pre-allocates a small
>> number of elements, or b) pure luck.
>>
>>   Thanks Andrew, I got confused with add_vertex and add_edge allocation
> properties. I have modified the code create numEdges. However the problem
> occurs while building component_index which does not access graph data
> structure but rather only the parent map. Attached is the modified file
> (also at http://codepad.org/5dZM6YBo).
>
> P.S. The command to run on ManyEdges would now be ./a.out ManyEdges.txt
> 21174

You appear to be mixing up the vector used as the data for the parent map 
with the disjoint_set structure.  Try using an iterator property map 
created on the vector (or a shared_array_property_map in newer versions of 
Boost) as the parent map for the disjoint set structure.

-- Jeremiah Willcock