[Networkit] All pairs shortest path

Christian Staudt christian.staudt at kit.edu
Tue Dec 13 06:14:13 CET 2016


Hi NetworKit community,

it so happens that I have a client who wants to solve an all-pairs shortest path problem on dense weighted graphs, and the question is whether I can recommend NetworKit. Here are a couple of issues I had:

- The FloydWarshall algorithm does not exist on the Python layer
-  What is the intended class hierarchy for APSP algorithms? class APSP inherits from APAPP<edgeweight> - but what is APAPP and where is APAPP.h ?
- I would have expected these algorithms in the networkit/distance module. Instead they are in the networkit/graph folder (which reminds me a bit of a PhD student’s desk on the day before the deadline*).

Because FloydWarshall will not scale, and no exact algorithm would, do you know any methods to get an estimate of the distances for this scenario (weighted, dense graph)? Has any work in this direction been done within NetworKit?



Best regards
Chris



* ps. I recently had a discussion with the CEO of a company that trains software developers in agile methods. His claim was that especially projects in C++ tend to accumulate technical debt (unfixed bugs, architecture problems etc.) until the project grinds to a halt. He said that’s because the language is challenging and tool support for refactoring is bad (both is true). I defended C++ with the example of NetworKit, which has not gone bankrupt in this respect, but had to concede that it was lots of manual work to keep the technical debt in check. In the end we agreed that C++ projects can evolve nicely, but it requires very good programmers and someone always pushing for refactoring. So yeah, a bit of technical debt here.


-------------- 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: <http://lists.ira.uni-karlsruhe.de/pipermail/networkit/attachments/20161213/3dd9939e/attachment.sig>


More information about the NetworKit mailing list