[Networkit] RmatGenerator crashes

Maximilian Vogel maximilian.vogel at student.kit.edu
Wed Oct 28 10:11:18 CET 2015



On 27.10.2015 23:27, Christian Staudt wrote:
> True, I didn’t pay attention to that parameter. The generator works 
> with more realistic inputs. What was strange is that high numbers 
> crashed the interpreter immediately. I assume Graph G(n, true); fails 
> with a segfault when n = 2^100 because a vector of this size cannot be 
> allocated?
NetworKit::node,count,index have 64 bits and the number of nodes is 
computed with n = 1 << scale, therefore the constructor ends up 
allocating a vector for 2^36 elements.

> But shouldn’t that raise an exception?
You will get an std::bad_alloc, but only if the OS can't satisfy the 
memory request. This doesn't seem to be the case for 2^36.
>> and a quick look at the code suggest that there's something wrong the 
>> node ids of the drawn edges. I'll look into it.
> Where do you see it?
There is no check whether the nodes of the drawn edge exists and thus 
you'll end up in a segmentation fault as soon as a node with an id 
greater than 2^36 is sampled. I suggest to check the parameter scale in 
the constructor and throw an exception when it's greater than 63.


>
>
> On 27 Oct 2015, at 16:41, Maximilian Vogel 
> <maximilian.vogel at student.kit.edu 
> <mailto:maximilian.vogel at student.kit.edu>> wrote:
>
>> Hi,
>> You try to create a graph 2^100 nodes. That's quite a number. Still 
>> it shouldn't kill the kernel, but instead throw an exception or 
>> something. You might want to try a smaller number, then it should work.
>>
>> The stack trace
>> >>> generators.RmatGenerator(100, 3, 0.25, 0.25, 0.25, 0.25).generate()
>> Program received signal SIGSEGV, Segmentation fault.
>> 0x00007ffff58e4ca2 in std::vector<unsigned long, 
>> std::allocator<unsigned long> >::size (this=0x6bbdca0c771b9090) at 
>> /usr/include/c++/5.2.0/bits/stl_vector.h:655
>> 655          { return size_type(this->_M_impl._M_finish - 
>> this->_M_impl._M_start); }
>> (gdb) bt
>> #0  0x00007ffff58e4ca2 in std::vector<unsigned long, 
>> std::allocator<unsigned long> >::size (this=0x6bbdca0c771b9090) at 
>> /usr/include/c++/5.2.0/bits/stl_vector.h:655
>> #1  0x00007ffff590aae6 in NetworKit::Graph::indexInOutEdgeArray 
>> (this=0x7fffffffe010, u=8009626009359660960, v=11002897751786542239) 
>> at networkit/cpp/graph/Graph.cpp:187
>> #2  0x00007ffff590e57a in NetworKit::Graph::increaseWeight 
>> (this=0x7fffffffe010, u=8009626009359660960, v=11002897751786542239, 
>> ew=1) at networkit/cpp/graph/Graph.cpp:820
>> #3  0x00007ffff597f9d6 in NetworKit::RmatGenerator::generate 
>> (this=0x1c0c510) at networkit/cpp/generators/RmatGenerator.cpp:64
>> #4  0x00007ffff58a3648 in 
>> __pyx_pf_10_NetworKit_13RmatGenerator_4generate 
>> (__pyx_v_self=<optimized out>) at networkit/_NetworKit.cpp:22097
>>
>> and a quick look at the code suggest that there's something wrong the 
>> node ids of the drawn edges. I'll look into it.
>>
>> Best,
>> Max
>>
>> On 27.10.2015 20:28, Christian Staudt wrote:
>>> Hi all,
>>> every time I tried to use the RmatGenerator it crashed, for example:
>>>
>>> 	generators.RmatGenerator(100, 3, 0.25, 0.25, 0.25, 0.25).generate()
>>>
>>> This kills the Python kernel for me. Any ideas why?
>>>
>>> Chris
>>>
>>>
>>> _______________________________________________
>>> NetworKit mailing list
>>> NetworKit at ira.uni-karlsruhe.de
>>> https://lists.ira.uni-karlsruhe.de/mailman/listinfo/networkit
>>
>> _______________________________________________
>> NetworKit mailing list
>> NetworKit at ira.uni-karlsruhe.de <mailto:NetworKit at ira.uni-karlsruhe.de>
>> https://lists.ira.uni-karlsruhe.de/mailman/listinfo/networkit
>
>
>
> _______________________________________________
> NetworKit mailing list
> NetworKit at ira.uni-karlsruhe.de
> https://lists.ira.uni-karlsruhe.de/mailman/listinfo/networkit

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20151028/b4cdb62a/attachment-0001.html>


More information about the NetworKit mailing list