[Networkit] spanning forest algorithms

Michael Hamann michael.hamann at kit.edu
Thu Apr 7 10:35:20 CEST 2016


I wrote parts of the algorithms (like RandomMaximumSpanningForest) as I 
needed them and iirc I fixed SpanningForest some time ago (but should be 
tested if it is really fixed). Some time ago I created a task in our 
issue tracker exactly about this: 
There I summarized the features of the different algorithms (which still 
had different names back then).


On 06.04.2016 14:29, Henning Meyerhenke wrote:
> Christian,
> I remember that we talked about SpanningForest::generate() some time
> ago. It is apparently your code which needs to be fixed since it does
> not generate a spanning tree / forest properly and fails a unit test.
> Please fix it.
> I believe I once authored KruskalMSF, simplifying or correcting existing
> code. I don't know about RandomMaximumSpanningForest. Who wrote it?
> What I can say is that spanning tree algorithms will play a more
> important role for us over the next months. In that course one could
> revise what is already there. So far there was no need for pythonizing
> for me.
> Thanks,
> Henning
> Am 06.04.16 um 13:46 schrieb Christian Staudt:
>> Does anyone feel responsible for maintaining the various spanning
>> tree algorithms we have in NetworKit? I’ve had trouble making sense
>> of this: On the Python level, some algorithms are pythonized, others
>> are not. There is a class hierarchy on the C++ level but it is not
>> mapped to the Python level. There is a class
>> RandomMaximumSpanningForest that says "Computes a random
>> maximum-weight spanning forest using Kruskal's algorithm by
>> randomizing the order of edges of the same weight.”, and then there
>> is KruskalMSF, only in C++. In SpanningForest::generate() there is a
>> note that says "please fixme!” but it doesn’t say what is to be
>> fixed.
>> 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
> https://lists.ira.uni-karlsruhe.de/mailman/listinfo/networkit

More information about the NetworKit mailing list