[Jung-support] Incorrect calculation of the average distances for undirected unweighted graphs

[Hussain Al M. <hus...@gm...>]

Greetings;

I came across DistanceStatistics class which is part of the jung algorithms library and found that the static method averageDistances(v) does not provide accurate measure.

Here are the steps to reproduce the problem:


	UndirectedSparseGraph<String, String> graph = new UndirectedSparseGraph<String, String>();
	graph.addVertex("1");
	graph.addVertex("2");
	graph.addVertex("3");
	graph.addVertex("4");
	graph.addEdge("1->2", "1","2");
	graph.addEdge("2->3", "2","3");
	graph.addEdge("2->4", "2","4");

	/*
	 * the above graph is composed of 4 vertices and 3 edges, 
	 * the shortest simple paths are:
	 * [(1,2)] , [(2,3)] , [(2,4)] , [(1,2),(2,3)] , [(1,2),(2,4)] , [(3,2),(2,4)]
	 * the lengths are 1,1,1,2,2,2 and the sum equals to 9
	 * the average shortest path length considering number of vertices would be 9/4 = 2.25
	 * the average distances with respect to each vertex should be the following:
	 * 
	 * avgDist("1") = (1+2+2)/3 = 5/3 = 1.667
	 * avgDist("2") = (1+1+1)/3 = 3/3 = 1.000
	 * avgDist("3") = (1+2+2)/3 = 5/3 = 1.667
	 * avgDist("4") = (1+2+2)/3 = 5/3 = 1.667
	 */

	Distance<String> distance = new DijkstraShortestPath<String, String>(graph);
	Transformer<String, Double> transformer = DistanceStatistics.averageDistances(graph, distance);
		
	double sum = 0.0;
	for(String vertex : graph.getVertices()){
		double avgDist = transformer.transform(vertex);
		sum = sum + avgDist;
		System.out.printf("avgDist('%s') = %4.3f\n", vertex, avgDist);
	}

	System.out.println("----------------------");
	System.out.printf("graph average shortest path length is %4.3\n" , (sum/4));


// The output of the above script is the following:

avgDist('1') = 0.600
avgDist('2') = 1.000
avgDist('3') = 0.600
avgDist('4') = 0.600
----------------------
graph average shortest path length is 0.700

which is not what is expected. Even when considering paths twice, because the graph is undirected, the results are still not the same.