[Networkit] Bachelor-Project about generic semiring operators

Peter Eisenmann pe44 at gmx.de
Tue Jun 28 02:30:29 CEST 2016


Hi,
I am no expert, but wouldn't it be better to keep the API for SSSP as it is
and instead create a class GenericSSSP (with templates), of which SSSP then
would be an instance?
Or maybe there is a way of default instantiation for templates, but I could
not find anything (only
http://stackoverflow.com/questions/15373823/template-default-arguments,
which says otherwise)
Best,
Peter

On Mon, 27 Jun 2016 at 17:10 Thomas Schmidt <
thomas.3.schmidt at uni-konstanz.de> wrote:

> 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
> _______________________________________________
> NetworKit mailing list
> NetworKit at ira.uni-karlsruhe.de
> https://lists.ira.uni-karlsruhe.de/mailman/listinfo/networkit
>
-------------- n�chster Teil --------------
Ein Dateianhang mit HTML-Daten wurde abgetrennt...
URL: <http://lists.ira.uni-karlsruhe.de/pipermail/networkit/attachments/20160628/9af9384e/attachment-0001.html>


More information about the NetworKit mailing list