Pseudo code for radius_DHV method

radius_DHV.py

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

# Algorithm
while LB < UB:
	# Select vertex with minimum eccentricity lower bound, say u
	# Compute shortest distances from u to other vertices using BFS or Dijkstra
	distances = BFS(G, u) or Dijkstra(G, u)

	UB = min(UB, eccentricity(u))

	if eccentricity(u) == ecc_lower_bound[u]:
		break  # we have found vertex with minimum eccentricity and hence the radius

	# select antipode of u, which is vertex at max distance from u
	# By definition of antipode eccentricity(antipode) >= eccentricity(u)
	antipode_u = vertex at max distance from u

	# Compute shortest distances from antipode_u and use it to update ecc_lower_bound
	distances = BFS(G, antipode_u) or Dijkstra(G, antipode_u)

	for v in vertices:
		ecc_lower_bound[v] = max(ecc_lower_bound[v], distances[v])

	LB = min(ecc_lower_bound)

return UB