Statistics about shortest path

30 views
Skip to first unread message

oj

unread,
Dec 9, 2015, 1:33:06 AM12/9/15
to Sparksee
Hi,

I'm running a singlePairShortestPathBFS very similar to what is given in the example code with maxhops set to 5. 
I test this with random source, destination vertex pairs and time it. 

For some pairs of vertices it finds that no paths(cost=0) very quickly. while for other pairs finding there are no paths(cost=0)  takes a longer time. Same is the case for path costs>0. 
I need some statistic that will explain this time difference, as cost is not the suitable one. 

Is there any other statistic I can get from after running the algorithm? Maybe the number of different paths explored to find shortest path etc..? 

Thanks!


c3po.ac

unread,
Dec 9, 2015, 8:58:15 AM12/9/15
to Sparksee
Hi,

The Sparksee algorithms package provided are aimed to give a simple solution to solve common problems hence they don't generate statistics about it's performance.

We believe that the reason why certain pairs take longer must be that the degree of the nodes explored at each level is bigger than for other pairs. You could calculate the number of neighbors at 5 hops from the start node to get an idea of the algorithm cost for certain pair of nodes. But the cost of this operation may be similar to the cost of the shortestpath algorithm.

Hope this helped.

Best regards,

El dimecres, 9 desembre de 2015 7:33:06 UTC+1, oj va escriure:

oj

unread,
Dec 9, 2015, 6:49:34 PM12/9/15
to spar...@googlegroups.com
Hi,

Thank you, that's exactly the kind of statistic I was looking for!

1) so the fastest way to get the statistic(neighbours at depth-x) is to perform g.neighbors operations x times and counting the number of objects in the final Objects variable right? 
2) if I run the same test without setting the maxhops. What happens then? Does it look for all possible options?

c3po.ac

unread,
Dec 10, 2015, 5:40:47 AM12/10/15
to Sparksee
Hi,

Great! About your questions:

1) I think your approach is the one to go, but you may want to intersect each result with the already visited nodes.
2) Yes indeed, when you don't limit the number of hops all the possible paths are explored.


Best Regards

El dijous, 10 desembre de 2015 0:49:34 UTC+1, oj va escriure:
Reply all
Reply to author
Forward
0 new messages