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

Subject: Re: [boost] [Graph] component_index crash on big graph
From: Sandeep Gupta (gupta.sandeep_at_[hidden])
Date: 2009-07-07 11:04:34

On Tue, Jul 7, 2009 at 7:27 AM, Jeremiah Willcock <jewillco_at_[hidden]>wrote:

> 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.
>

   Yes the parent map access is what causing the segfault. As you suggested
I did switch to iterator_property_map but unfortunately it still segfaults
at the previous location.  Not sure if I am declaring Components_t at line
58 correctly.
The modified code can be found at http://codepad.org/1GAHpitK

Thanks for taking a look, Jeremiah.

-sandeep