ecc_DHV.py

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

# Algorithm
while active:
  # Select vertex with minimum eccentricity 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)
  active.erase(u)
  
  if ecc_u == ecc_lower_bound[u]:
    # Update eccentricity upper bounds.
    for v in active:
      ecc_upper_bound[v] = min(ecc_upper_bound[v], distances[v] + ecc_u)
  else:
    # Use antipode of u, i.e vertex at maximum distance from u to update
    # eccentricity lower bounds
    distances = BFS(G, antipode_u) or Dijkstra(G, antipode_u)
    acitve.erase(antipode_u)

  for v in active:
    if ecc_lower_bound[v] == ecc_upper_bound[v]:
      remove v from active
        
return ecc_upper_bound