[Networkit] Bachelor-Project about generic semiring operators

Henning Meyerhenke henning.meyerhenke at kit.edu
Mon Jun 27 17:10:31 CEST 2016


Dear Thomas,

Our Hiwi Michael Wegner is currently working on similar things in the
context of GraphBLAS. I suggest to get in touch with him as well. He
already implemented a generic Bellman-Ford, for example.

Best,
Henning


Am 27.06.16 um 16:00 schrieb Thomas Schmidt:
> 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
> 

-- 

==========================================================
Karlsruhe Institute of Technology (KIT)
Institute of Theoretical Informatics (ITI)

Prof. Dr. Henning Meyerhenke
Theoret. Informatics / Parallel Computing

Phone: +49-721-608-41876
Web: http://parco.iti.kit.edu/henningm/

KIT - The Research University in the Helmholtz Association
==========================================================

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 5399 bytes
Desc: S/MIME Cryptographic Signature
URL: <http://lists.ira.uni-karlsruhe.de/pipermail/networkit/attachments/20160627/4283330b/attachment.p7s>


More information about the NetworKit mailing list