diameter_DHV.py

Input : Sage Graph object G
Initializing LB = 0, UB = INFINITY, ecc_lower_bound = [0 for i in range(vertices)], 
             ecc_upper_bound = [Infinity for i in range(vertices)], active = list(G)

# Algorithm
while LB < UB and active:
  # Select vertex with maximum eccentricity upper bound in active, say u.
	# Compute shortest distances from u to other vertices using BFS or Dijkstra
  # Remove u from active vertices
	distances = BFS(G, u) or Dijkstra(G, u)
  acitve.erase(u)

	LB = max(LB, eccentricity(u))
 
  # Update eccentricity lower bound of vertices in active as follows:
  for v in active:
    ecc_lower_bound[v] = max(ecc_lower_bound[v], distances[v])

  # Select x such that distances(u, x) + ecc[x] == ecc[u].
  # Since we don't know ecc[x], we select x with minimum eccentricity
  # lower bound.  If ecc[x] == ecc_lb[x], we are done. Otherwise, we
  # update eccentricity lower bounds and repeat
  while active:
    # Select vertex with minimum eccentricity lower bound in active, say x
    # Compute shortest distances from x to other vertices using BFS or Dijkstra
    # Remove x from active
  	distances = BFS(G, x) or Dijkstra(G, x)
    acitve.erase(x)
    LB = max(LB, ecc_x)
    
    if ecc_x == ecc_lower_bound[x]:
      # update eccentricity upper bound as follows:
      for v in active:
        ecc_upper_bound[v] = min(ecc_upper_bound[v], distances[v] + ecc_x)
      break
    else:
      # Use antipode of x, i.e vertex at maximum distance from x to update
      # eccentricity lower bounds
      distances = BFS(G, antipode_x) or Dijkstra(G, antipode_x)
      acitve.erase(antipode_x)
      LB = max(LB, ecc_x)

      for v in active:
        ecc_lower_bound[v] = max(ecc_lower_bound[v], distances[v])
        
return LB