difub.py

Input : Sage DiGraph object G

# Obtain Lower bound on the diameter and vertex m with low eccentricity
# Using 2Dsweep method
LB, s, m, d = 2Dsweep(G)

# Compute forward distances from m to all vertices in G
distances_1 = forward_BFS(G, m) or forward_Dijkstra(G, m)

# Compute backward distances from m to all vertices in G
distances_2 = backward_BFS(G, m) or backward_Dijkstra(G, m)

# Update LB
LB = max(LB, forward_ecc_m, backward_ecc_m)

# order the vertices for further computation.
order_1 = [vertices in order of decreasing forward distances from m]
order_2 = [vertices in order of decreasing backward distances from m]

intialize i = 0 and UB = 0
UB = max(2 * distances_1[order_1[i]] , 2 * distances_2[order_2[i]] )

# Algorithm
while LB < UB:
  u = order_1[i]
  v = order_2[i]
  
  # Compute backward distances from u
  distances_u = backward_BFS(G, u) or backward_Dijkstra(G, u)
  # Compute forward distances from v
  distances_v = forward_BFS(G, v) or forward_Dijkstra(G, v)
  
  # Update LB, i, UB
  LB = max(LB, backward_ecc_u, forward_ecc_v)
  i += 1
  UB = max(2 * distances_1[order_1[i]] , 2 * distances_2[order_2[i]] )
 
return LB