[Networkit] Bachelor-Project about generic semiring operators

Thomas Schmidt thomas.3.schmidt at uni-konstanz.de
Thu Aug 4 13:19:02 CEST 2016

Hi Chris,
I was busy with exams the past few weeks, sorry, but I've finally gotten
around to implement most parts.
It didn't really work the way I thought, especially, passing the relax
functions of the algorithms as arguments was way harder as I thought, so
I weren't able to implement that.

Other than that, I created APP, a base class of
SSSP, and of SemiringDijkstra. I didn't find a way to implement a
generic version of Dijkstra, without disrupting the use of the existing
Dijkstra implementation, so I had to create the extra class.
Further, I created APAPP, a base class of APSP, and of FloydWarshall.
Then, I created three semiring classes, ShortestPathSemiring,
SafestPathSemiring, and TimeVaryingSemiring, as examples, and an
(draft of) SemiringTest to show how it would be used.
What is the best way to show you the changes? Since I don't have rights
on the repo I can't push them, so a diff is appended. Or is there a
better way?

Now, how do would you think can this be translated to Python?

Kind regards,

> Hi Thomas,
> sounds good. At this point my recommendation is that you go ahead with
> implementation and tests, then show us code and test results. And I’m
> not just saying that because I don’t have much time (last week at KIT…).
> I think your design ideas are basically sound. Have some more trust in
> them and try them out. Then iterative improvements are possible.
> Chris
> On 28 Jun 2016, at 16:25, Thomas Schmidt
> <thomas.3.schmidt at uni-konstanz.de> wrote:
> Hi Chris,
> > Have you thought about how this new functionality will be available on
> > the Python layer? It should, but it doesn’t have to be a 1:1 mapping
> > of the underlying C++. We can help with the mapping.
> I think the best way would be for the Python layer to, just like on the
> C++ layer, add the relax function as a parameter. I am not really sure
> how to map a template class, though. But since, in python, addition and
> multiplication can be defined for arbitrary classes as well, I think it
> would be best, if one could just define such a class, assign objects of
> it as the edgeweights, and then just call Dijkstra on it.
> Regarding that, something just came to my mind: How should the
> edgeweights be added? Should there be an extra function for it? So far,
> I just created a vector and handed it over to the Dijkstra constructor.
> But anyways, if Python's duck typing could be utilized this way, it
> would be great. Do you know if this is possible?
> Thomas
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.ira.uni-karlsruhe.de/pipermail/networkit/attachments/20160804/f31276ee/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: generic_indirect_relations.diff
Type: application/octet-stream
Size: 36498 bytes
Desc: not available
URL: <http://lists.ira.uni-karlsruhe.de/pipermail/networkit/attachments/20160804/f31276ee/attachment-0001.obj>

More information about the NetworKit mailing list