Algorithm - Finding the number of pairs with diameter distance in a tree?

Question

I have a non-rooted bidirectional unweighted non-binary tree. I know how to find the diameter of the tree, the greatest distance between any pair of points in the tree, but I'm interested in finding the number of pairs with that max distance. Is there an algorithm to find the number of pairs with diameter distance in better than O(V^2) time, where V is the number of nodes?

Thank you!

Answer 1

Yes there is an algorithm with O(V+E) time.It is simply a modified version of finding the diameter.

As we know we can find the diameter using two calls of BFS by first making first call on any node and then remembering the last node discovered u and running a second call BFS(u),and remembering the last node discovered ,say v.The distance between u and v gives us the diameter.

Coming to number of pairs with that max distance.

1.Before invoking the first BFS,initialize an array distance of length |V| and distance[s]=0.s is the starting vertex for first BFS call on any node.

2.In the BFS,modify the while loop as:

while(Q is not empty)
 {
  e=deque(Q);
    for all vertices w adjacent to e
     {
       if(w is not visited)
        {
         enque(w)
         mark w as visited
         distance[w]=distance[e]+1
         parent[w]=e
        }
     }
 }

3.Like I said,remembering the last node visited,say u is that node. Now counting the number of vertices that are at the same level as vertex u. mark is an array of length n,which has all its value initialized to 0,0 implies that vertex not counted initially.

n1=0
for i = 1 to number of vertices
 {
  if(distance[i]==distance[u]&&mark[i]==0)
   {
    n1++
    mark[i]=1/*vertex counted*/
   }
 }  

n1 gives the number of vertices,that are at the same level as vertex u,now for all vertices that have mark[i] = 1 ,are marked and they will not be counted again.

4.Similarly before performing second BFS on u,initialize another array distance2 of length |V| and distance2[u]=0.

5.Run BFS(u) and again get the last node discovered say v

6.Repeat 3rd step,this time on distance2 array and taking a different variable say n2=0 and the condition being

if(distance2[i]==distance2[v]&&mark[i]==0)
 n2++
else if(distance2[i]==distance2[v]&&mark[i]==1)
 set_common=1

7.set_common is a global variable that is set when there are a set of vertices such that between any two vertices the path is that of a diameter and the first bfs did not mark all those vertices but did mark at least one of those that is why mark[i]==1.

Suppose that first bfs did mark all such vertices in first call then n2 would be = 0 and set_common would not be set and there is no need also.But this situation is same as above

In any case the number of pairs giving diameter are:=

(n+n2)combination2 - X=(n1+n2)!/((2!)((n1+n2-2)!)) - X

I will elaborate on what X is.Else the number of pairs are = n1*n2,which is the case when 2 disjoint set of vertices are giving the diameter

So the Condition used is

  if(n2==0||set_common==1)
    number_of_pairs=(n1+n2)C2-X
  else n1*n2

Now talking about X.It can occur that the vertices that are marked may have common parent.In that case we must not count there combinations.So before using the above condition it is advised to run the following algorithm

  X=0/*Initialize*/
 for(i = 1 to number of vertices)
  {
   s = 0,p = -1
   if(mark[i]==0)
    continue
   else
   {
    s++
    if(p==-1)
     p=parent[i]
    while((i+1)<=number_of_vertices&& p==parent[i+1])
     {s++;i++}
   }
   if(s>1)
    X=X+sC2
 }

Proof of correctness

It is very easy.Since BFS traverses a tree level by level,n1 will give you the number of vertices at the level of u and n2 gives you the number of vertices at the level of v and since the distance between u and v = diameter.Therefore, distance between any vertex on level of u and any vertex on level of v will be equal to diameter.

The time taken is 2(|V|) + 2*time_of_DFS=O(V+E).

Answer 2

Yes, there's a linear-time algorithm that operates bottom-up and resembles the algorithm for just finding the diameter. Here's the signature in Java-ish pseudocode; I'll leave the algorithm itself as an exercise.

class Node {
    Collection<Node> children;
}

class Result {
    int height;  // height of the tree
    int num_deep_nodes;  // number of nodes whose depth equals the height
    int diameter;  // length of the longest path inside the tree
    int num_long_paths;  // number of pairs of nodes at distance |diameter|
}

Result computeNumberOfLongPaths(Node root);  // recursive