[Networkit] All pairs shortest path

Christian Staudt christian.staudt at kit.edu
Tue Jan 3 14:13:53 CET 2017


Hi all,
I’ve moved the APSP class from the “graph” to the “distance” module, I think it’s more intuitive to find it there. Thanks for making APSP ready to use.

Chris



> On 14 Dec 2016, at 19:57, Christian Staudt <christian.staudt at kit.edu> wrote:
> 
> 
>> On 13 Dec 2016, at 15:04, Elisabetta Bergamini <elisabetta.bergamini at kit.edu <mailto:elisabetta.bergamini at kit.edu>> wrote:
>> 
>> what are your running time requirements?
>> I tried to generate a random weighted graph with 1000 nodes and about 500K edges and APSP took seconds on my laptop.
>> Would that work for you?
> 
> Great, then the case is probably solved if the graph stays so small. Thanks for testing Elisabetta.
> 
> I think APSP needs to be imported into the distance module. I can do this later, then it looks presentable to my client.
> 
> Question: APSP.getDistances() documentation says: "Returns a vector of vectors of weighted distances from the source node, i.e. the
>  	 	length of the shortest path from the source node to any other node.”
> 
> What is the source node? Does this make sense?
> 
>> However, a very simple one could be to just select a set L of central nodes (e.g. node with highest degree or high approx. betweenness), compute a SSSP from each of them and approximate the distance between any two nodes (u, v) as min_{l in L} d(u, l) + d(l, v).
>> Best,
>> 
>> Elisabetta
> 
> 
> 
>> Yes, this can be a good heuristic. There’s a paper by Edith Cohen et al. at COSN’14 (IIRC) to compute approximate closeness centrality that exploits a similar idea: they actually chose the nodes uniformly at random and then have the concept of a pivot p(v) for each node v (p(v) is the sampled node closest to v) that they use for better estimation.
>> 
>> Matteo
> 
> Thanks for the ideas. Let me check if the problem size will actually grow, then we can think further in this direction.
> 
> Chris
> 
> 
> 
> _______________________________________________
> NetworKit mailing list
> NetworKit at ira.uni-karlsruhe.de
> https://lists.ira.uni-karlsruhe.de/mailman/listinfo/networkit

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.ira.uni-karlsruhe.de/pipermail/networkit/attachments/20170103/36dcf072/attachment.html>
-------------- 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/20170103/36dcf072/attachment.sig>


More information about the NetworKit mailing list