[Networkit] Refactoring Diameter to the standard interface

Maximilian Vogel maximilian.vogel at student.kit.edu
Fri Jan 29 12:30:26 CET 2016



On 29.01.2016 12:04, Christian Staudt wrote:
> As far as I remember, the current exact diameter algorithm is fast 
> enough for all typical inputs, right? Getting a lower and upper bound 
> was important when we did not yet have a good algorithm like that, and 
> is now somewhat obsolete, I think.
The current exact algorithm just calls Michael's implementation of the 
sumsweep algorithm with error=0, referred to as 
DiameterAlgo::estimatedRange and from the resulting tuple it just 
ignores the upper bound. For weighted graphs, the exact algorithm uses a 
Dijkstra instance for each node.

>
> Doesn’t work for me either:
>
> In [*4*]: distance.Diameter(G, 
> distance.DiameterAlgo.Exact).run().getDistance()
> ---------------------------------------------------------------------------
> AttributeError       Traceback (most recent call last)
> <ipython-input-4-4fedc44e4eed>in <module>()
> ----> 1distance.Diameter(G, 
> distance.DiameterAlgo.Exact).run().getDistance()
>
> AttributeError: '_NetworKit.Diameter' object has no attribute 
> 'getDistance'
>
> This works, but the result looks weird:
>
> In [*5*]: distance.Diameter(G, 
> distance.DiameterAlgo.Exact).run().getDiameter()
> Out[*5*]: (9, 0)
>
> Anyway, Diameter(G).run().get... should also just work and yield one 
> number as a result.
Well, getDistance() was a typo. I meant getDiameter(). For algorithms 
computing a lower and upper bound, one number won't do it.

> Let us know if you were able to figure out what went wrong.
I was able to fix it, see: 
https://algohub.iti.kit.edu/parco/NetworKit/NetworKit/changeset/3feae7d76146753a0717dbaa403c82207f6f54b5
The constructor now works for the default case and is more verbose if 
the correct parameter is not provided.



>> On 29 Jan 2016, at 11:49, Maximilian Vogel 
>> <maximilian.vogel at student.kit.edu 
>> <mailto:maximilian.vogel at student.kit.edu>> wrote:
>>
>> I can confirm this, but I don't exactly know, why this happens. The 
>> behaviour of the constructor should be discussed anyways.
>> You can use the entries in the class distance.DiameterAlgo to choose 
>> one of the existing algorithms. Currently, 
>> distance.DiameterAlgo.Automatic produces the exception. The other 
>> options work fine for me. Note that for the option 
>> distance.DiameterAlgo.estimatedRange one should supply the additional 
>> parameter error (e.g. 0) and for 
>> distance.DiameterAlgo.estimatedSamples the desired number of samples 
>> (called nSamples).
>> One example call could be: distance.Diameter(G, 
>> distance.DiameterAlgo.Exact).run().getDistance()
>>
>> On 29.01.2016 11:36, Christian Staudt wrote:
>>> For me it doesn’t yet work fine:
>>>
>>> In [*5*]: dia = distance.Diameter(G)
>>>
>>> In [*6*]: dia.run()
>>> ---------------------------------------------------------------------------
>>> RuntimeError                             Traceback (most recent call 
>>> last)
>>> <ipython-input-6-50e09f02bdc6>in <module>()
>>> ----> 1dia.run()
>>>
>>> /Users/cls/workspace/NetworKit/networkit/_NetworKit.pyxin 
>>> _NetworKit.Algorithm.run (networkit/_NetworKit.cpp:6403)()
>>> *    114*raiseRuntimeError("Error, object not properly initialized")
>>> *    115* with nogil:
>>> --> 116 self._this.run()
>>> *    117* return self
>>> *    118*
>>>
>>> RuntimeError: should never reach this code as the algorithm should 
>>> be set correctly in the constructor or fail there
>>>
>>> What am I doing wrong?
>>>
>>>
>>>> On 28 Jan 2016, at 16:10, Maximilian Vogel 
>>>> <maximilian.vogel at student.kit.edu> wrote:
>>>>
>>>> I refactored the Diameter class. Although it works fine so far, I 
>>>> still consider it work in progress (documentation, behaviour of the 
>>>> constructor, proper toString-method, ...). I think it's a good 
>>>> opportunity for a code review and suggestions.
>>>>
>>>> Changes can be seen here:
>>>> - 
>>>> https://algohub.iti.kit.edu/parco/NetworKit/NetworKit/changeset/ad852b116919caf156b0a9a01dc22991638e0147
>>>> - 
>>>> https://algohub.iti.kit.edu/parco/NetworKit/NetworKit/changeset/5880040659cc84b05dff0e1b6ea1507cc2efb422
>>>>
>>>> Best
>>>> Max
>>>>
>>>> On 27.01.2016 08:35, Henning Meyerhenke wrote:
>>>>> Christian's suggestion would also be my preference.
>>>>>
>>>>> HM
>>>>>
>>>>>
>>>>> Am 26.01.16 um 21:26 schrieb Christian Staudt:
>>>>>> I recommend to move towards “one class - one measure”, the network
>>>>>> analysts perspective (rather than “one class - one algorithm”, the
>>>>>> algorithm engineer’s perspective). So probably Diameter should be one
>>>>>> class and the computation that .run() performs should be selected in the
>>>>>> constructor.
>>>>>>
>>>>>>
>>>>>>> On 26 Jan 2016, at 11:36, Maximilian Vogel
>>>>>>> <maximilian.vogel at student.kit.edu
>>>>>>> <mailto:maximilian.vogel at student.kit.edu>> wrote:
>>>>>>>
>>>>>>> This is just a little brainstorming:
>>>>>>>
>>>>>>>    * Refactor the different implementations into private methods.
>>>>>>>      Implement some logic deciding which algorithm to use in the
>>>>>>>      constructor. The run()-method then calls the right private method.
>>>>>>>      Retrieve the result with a getter method (always!) returning a pair.
>>>>>>>    * Expanding on the previous idea: Move the different implementations
>>>>>>>      into seperate classes and implement a wrapper class for convenient
>>>>>>>      usage.
>>>>>>>
>>>>>>> Those are the two raw designs that came to my mind. The second one
>>>>>>> seems cleaner, but probably means more work.
>>>>>>>
>>>>>>> Any fundamentally different designs? What do you think?
>>>>>>>
>>>>>>> Best
>>>>>>> Max
>>>>>>>
>>>>>>>
>>>>>>> On 25.01.2016 17:58, Christian Staudt wrote:
>>>>>>>> I have a situation in which it is very inconvenient that the Diameter class does not follow the standard pattern for our analytics algorithms, with parameter initialization in the constructor and a parameter-less run method.
>>>>>>>> Since several other people either depend or work on Diameter, I’d like to discuss proposals on how to refactor. To be honest I’d also be happy if someone would volunteer to implement the refactoring.
>>>>>>>>
>>>>>>>> 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
>>
>> _______________________________________________
>> 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/20160129/e1252585/attachment-0001.html>


More information about the NetworKit mailing list