[Networkit] possible bug

Christian Staudt christian.staudt at kit.edu
Tue Apr 5 08:52:07 CEST 2016


algohub is up again - could you please push that into the repo?

> On 04 Apr 2016, at 14:35, Michael Hamann <michael.hamann at kit.edu> wrote:
> 
> 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
>> 
> <diameter.patch>_______________________________________________
> 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: signature.asc
Type: application/pgp-signature
Size: 495 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20160405/36756e9d/attachment.sig>


More information about the NetworKit mailing list