[Networkit] Bachelor-Project about generic semiring operators

Thomas Schmidt thomas.3.schmidt at uni-konstanz.de
Mon Jun 27 16:00:33 CEST 2016


Hi,
I am currently working on a Bachelor Project where I have to implement
generic semiring operators in networkit. That is, instead of calculating
the shortest path on a graph, for example we calculate the safest path
(i.e. the edge weights represent probabilities), but the type of the
edgeweight should not be limited to doubles, it should be able to
operate on any object on which the addition and multiplication operators
are defined (and fulfill the properties of a semiring).

Regarding this, I alrady talked to Christian Staudt, about how it
probably would be realized the best. What we came up with was using the
edge indices to be able to store arbitrary types as edgeweights. And to
hand over the appropriate relax function as an argument to the SSSP
algorithm.

I started tying to work it out and found that we would still need to
use a template to handle those arbitrary edge weights. My proposal would
be to turn SSSP into a template class SSSP<T>, where we replace the
occurences of the type edgeweight with T, if it makes sense. This way,
SSSP<double> would be the single source shortest path class as it is
now (maybe a rename of SSSP<T> would be needed then?).
Further, I would change the Dijkstra class' constructor to also take the
list of edge weights, as well as the relax function as a parameter.

In a similar fashion, I would then also implement the Bellman-Ford
algorithm.

Any thoughts on that matter? I am not very experienced with C++, so any
input would be very appreciated.

Moreover, I want to implement the Floyd-Warshall algorithm, an all pair
shortest path algorithm, as well. I see that as of now, APSP is just
Dijkstra used on all nodes. Should I changge APSP to a superclass,
similar to SSSP here?

That would be all for now, please be sure to tell me any open
questions/ambiguities.

Kind regards,
Thomas
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.ira.uni-karlsruhe.de/pipermail/networkit/attachments/20160627/00e39eda/attachment-0001.html>


More information about the NetworKit mailing list