[Networkit] possible bug

Michael Hamann michael.hamann at kit.edu
Mon Apr 4 14:35:42 CEST 2016


Hi,

I don't know why it crashes but I can explain the problem with the 
infinite diameter (which is btw. inconsistent with the behavior for 
unweighted graphs) - the algorithm simply didn't consider deleted nodes. 
As algohub is down I've attached a patch from my local git clone that 
should fix the error.

Michael

On 04.04.2016 14:15, Maximilian Vogel wrote:
> The IPython shell doesn't crash for me, this is the result I get on my
> laptop:
> In [4]: distance.Diameter(C).run().getDiameter()
> ---------------------------------------------------------------------------
> RuntimeError                              Traceback (most recent call last)
> <ipython-input-4-b2e027030502> in <module>()
> ----> 1 distance.Diameter(C).run().getDiameter()
>
> /home/mv/workspace/hiwi/NetworKit/networkit/_NetworKit.pyx in
> _NetworKit.Algorithm.run (networkit/_NetworKit.cpp:6459)()
>      114                         raise RuntimeError("Error, object not
> properly initialized")
>      115                 with nogil:
> --> 116                         self._this.run()
>      117                 return self
>      118
>
> RuntimeError: Graph not connected - diameter is infinite
>
> The error message is somewhat surprising as in your workflow, the
> largest component is extracted and thus, the graph should be connected.
> Running components.ConnectedComponents(C) yields one connected
> component. Since the same algorithm is used in
> workflows.extractLargestComponent(g), I've run a BFS from a random node
> of C which visits 2042 nodes. Therefore, I assume the error to be in the
> Diameter implementation.
>
>
> On 04.04.2016 13:59, Christian Staudt wrote:
>> The following leads to a crash. Either
>> workflows.extractLargestComponent or distance.Diameter have a problem.
>>  Graph is attached.
>>
>> In [*5*]: G = readGraph("/Users/cls/Desktop/G-2.metis.graph",
>> Format.METIS)
>>
>> In [*6*]: components.ConnectedComponents(G).run().numberOfComponents()
>> Out[*6*]: 7
>>
>> In [*7*]: C = workflows.extractLargestComponent(G)
>> INFO:root:extracting component 0 containing 2042 nodes
>>
>> In [*8*]: distance.Diameter(C).run().getDiameter()
>> Python(26919,0x7fff72b8d000) malloc: *** error for object
>> 0x7fb97393c028: pointer being freed was not allocated
>> *** set a breakpoint in malloc_error_break to debug
>>
>>
>>
>>
>> _______________________________________________
>> 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
> https://lists.ira.uni-karlsruhe.de/mailman/listinfo/networkit
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: diameter.patch
Type: text/x-patch
Size: 902 bytes
Desc: not available
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20160404/4df5f83d/attachment.bin>


More information about the NetworKit mailing list