ifub_ldt.py
import temporal_distances as td
import temporal_graph as tg
from utils import util
import backward_BFS as Bbfs
import numpy as np
def count_pairs_reachable(graph, landmarks, is_inB, is_inA):
pairs_number = 0
num_landmarks = len(landmarks)
if graph.get_latest_node() is not None:
num_nodes = graph.get_latest_node()
else:
num_nodes = graph.get_num_nodes()
# num_landmarks, num_nodes = np.shape(is_inA)
for j in range(num_nodes):
reachables_nodes = np.full(num_nodes, False)
for i in range(num_landmarks):
if is_inA[i, j]:
reachables_nodes = np.logical_or(is_inB[i], reachables_nodes)
count = np.count_nonzero(reachables_nodes)
pairs_number += count
# Number of distinct element in A and in B (min(distinct(A), distinct(B))= num BFS classic diameter on landmark
distinct_A = np.full(num_nodes, False)
distinct_B = np.full(num_nodes, False)
for i in range(num_landmarks):
distinct_A = np.logical_or(is_inA[i], distinct_A)
distinct_B = np.logical_or(is_inB[i], distinct_B)
num_distinct_A = np.count_nonzero(distinct_A)
num_distinct_B = np.count_nonzero(distinct_B)
return pairs_number, num_distinct_A, num_distinct_B
def eccentricity_reachable(distances, is_inA_B):
if len(distances) != len(is_inA_B):
raise Exception("Distances array has an incorrect length!")
index = -1
count = 0
t = np.NINF
for elem in distances:
if elem > t and is_inA_B[count]:
t = elem
index = count
count += 1
return index, t
def sort_remove_unreachable(distances_fw, distances_bw):
# Sort EAT distances in descending order and store associated nodes to each distance in ind_eat_node array
ind_eat = np.argsort(-distances_fw)
dist_eat = distances_fw[ind_eat]
# Discard unreachable nodes from arrays
if len(np.where(dist_eat == np.inf)[0]) > 0:
inf_indices = np.where(dist_eat == np.inf)[0][-1] + 1
dist_eat = dist_eat[inf_indices:]
ind_eat = ind_eat[inf_indices:]
# Sort LDT distances in ascending order and store associated nodes to each distance in ind_ldt_node array
ind_ldt = np.argsort(distances_bw)
dist_ldt = distances_bw[ind_ldt]
# Discard unreachable nodes from arrays
if len(np.where(dist_ldt == np.NINF)[0]) > 0:
inf_indices = np.where(dist_ldt == np.NINF)[0][-1] + 1
dist_ldt = dist_ldt[inf_indices:]
ind_ldt = ind_ldt[inf_indices:]
return dist_eat, ind_eat, dist_ldt, ind_ldt
def who_is_reachable_with_landmarks(graph, landmarks=None):
"""
:param graph: Graph
:param landmarks: array of tuples where for each tuple, first elements is landmark nodes and second element is time
"""
num_visits = 0
# Create reverse graph to compute LDT (bw) paths distances from central_node
g_path_rev = util.reverse_ef(folder=graph.get_file_path().rsplit('/', 1)[0] + '/',
file=graph.get_file_path().rsplit('/', 1)[1])
g_rev = tg.Graph(file_path=g_path_rev, is_directed=graph.get_is_directed(), latest_node=graph.get_latest_node())
ldt_dist = td.LatestDeparturePath()
eat_dist = td.EarliestArrivalPath()
if graph.get_latest_node() is not None:
num_nodes = graph.get_latest_node()
else:
num_nodes = graph.get_num_nodes()
# Compute distances forward/backward from/to landmarks nodes
distances_fw = np.full((len(landmarks), num_nodes), 0, dtype=float)
distances_bw = np.full((len(landmarks), num_nodes), 0, dtype=float)
for i in range(len(landmarks)):
middle_t = landmarks[i][1]
eat_dist.compute_distances(graph=graph, start_node=int(landmarks[i][0]), min_time=middle_t)
num_visits += 1
dist_fw = eat_dist.get_distances()
ldt_dist.compute_distances(graph=g_rev, start_node=int(landmarks[i][0]), max_time=middle_t)
num_visits += 1
dist_bw = ldt_dist.get_distances()
distances_fw[i] = dist_fw
distances_bw[i] = dist_bw
is_inA = np.full((len(landmarks), num_nodes), False)
is_inB = np.full((len(landmarks), num_nodes), False)
distances_eat = []
ind_eat_node = []
distances_ldt = []
ind_ldt_node = []
for j in range(len(landmarks)):
for i in range(num_nodes):
if distances_fw[j, i] != np.inf:
is_inB[j, i] = True
if distances_bw[j, i] != np.NINF: # N.B. not reachable nodes have -inf distance in LDT
is_inA[j, i] = True
dist_eat, ind_eat, dist_ldt, ind_ldt = sort_remove_unreachable(distances_fw[j], distances_bw[j])
distances_eat.append(dist_eat)
ind_eat_node.append(ind_eat)
distances_ldt.append(dist_ldt)
ind_ldt_node.append(ind_ldt)
return is_inB, is_inA, distances_eat, ind_eat_node, distances_ldt, ind_ldt_node, num_visits
def ifub_on_landmarks(graph, landmarks=None):
"""
:param graph: Graph
:param landmarks: array of tuples where for each tuple, first element is landmark nodes and second element is time
"""
graph_name = graph.get_file_path().rsplit('/', 1)[1]
print("Computing iFUB Diameter of Graph " + graph_name + "...")
if landmarks is None:
# Give me most central node
_, landmarks = graph.get_max_deg_out()
if np.isscalar(landmarks):
min_t, max_t = graph.get_time_interval()
middle_t = round(((max_t - min_t) / 2) + min_t)
l_tuple = [(landmarks, middle_t)]
landmarks = np.empty(len(l_tuple), dtype=object)
landmarks[:] = l_tuple
num_landmark = len(landmarks)
is_inB, is_inA, distances_eat, ind_eat_node, distances_ldt, ind_ldt_node, num_visits = \
who_is_reachable_with_landmarks(graph=graph, landmarks=landmarks)
pairs_number, num_distinct_A, num_distinct_B = count_pairs_reachable(graph=graph, landmarks=landmarks,
is_inB=is_inB, is_inA=is_inA)
# print('Pairs reachables with landmarks Graph ' + graph_name + ': ' + str(pairs_number), flush=True)
# Arrays of indices for locate next node to process relative to each landmark
indices_bw = np.full(num_landmark, 0)
if graph.get_latest_node() is not None:
num_nodes = graph.get_latest_node()
else:
num_nodes = graph.get_num_nodes()
# Into the arrays to_be_considered, if one item is False, that node has already been considered in another BFS
to_be_considered_bw = np.full(num_nodes, True)
# Create opposite graph to compute forward LDT distances
g_path_op = util.opposite_graph(folder=graph.get_file_path().rsplit('/', 1)[0] + '/',
file=graph.get_file_path().rsplit('/', 1)[1])
g_op = tg.Graph(file_path=g_path_op, is_directed=graph.get_is_directed(), latest_node=graph.get_latest_node())
# Get smallest distance bw (LDT) to landmarks
# Choose the upper bound like the higher upper bound from all landmark's upper bounds (smallest LDT distance)
ub = np.inf
idx_landmark = -1
for i in range(num_landmark):
if distances_ldt[i][0] < ub:
ub = distances_ldt[i][0]
idx_landmark = i
lb = np.inf
while ub < lb:
index_node_bw = ind_ldt_node[idx_landmark][indices_bw[idx_landmark]]
back_bfs = Bbfs.TemporalBackwardBFS(graph=g_op, start_node=index_node_bw)
back_bfs.bfs()
num_visits += 1
reachables_nodes = is_inB[idx_landmark]
for i in range(num_landmark):
if is_inA[i, index_node_bw]:
reachables_nodes = np.logical_or(reachables_nodes, is_inB[i])
_, ecc_fw = eccentricity_reachable(back_bfs.get_eat(), is_inA_B=reachables_nodes)
ecc_fw = -ecc_fw
indices_bw[idx_landmark] += 1
to_be_considered_bw[index_node_bw] = False
lb = min(lb, ecc_fw)
if lb < (ub + 1):
return lb, num_visits, num_distinct_A, num_distinct_B, pairs_number
max_distance = np.inf
for i in range(num_landmark):
while indices_bw[i] < len(distances_ldt[i]) and not to_be_considered_bw[ind_ldt_node[i][indices_bw[i]]]:
indices_bw[i] += 1
if indices_bw[i] < len(distances_ldt[i]):
if (distances_ldt[i][indices_bw[i]]) < max_distance:
max_distance = distances_ldt[i][indices_bw[i]]
idx_landmark = i
if max_distance == np.inf: # All nodes have been examined
return lb, num_visits, num_distinct_A, num_distinct_B, pairs_number
ub = max_distance
return lb, num_visits, num_distinct_A, num_distinct_B, pairs_number
if __name__ == '__main__':
# g = tg.Graph(file_path='graphs/transportation2/belfast_temporal_day.txt.sor', is_directed=True)
g = tg.Graph(file_path='./graphs/Dummy/transportation/kuopio-sa-sorted.txt', is_directed=True, latest_node=549)
# Create array of tuples [(landmark_node_1, time_1)...(landmark_node_k, time_k)]
_, nodes = g.get_max_deg_out(n=9)
number_landmarks = len(nodes)
a, b = g.get_time_interval()
mid_t = round(((b - a) / 2) + a)
mid_t1 = round(((b - a) / 4) + a)
# mid_t2 = a
lmarks = np.empty(number_landmarks * 2, dtype=object)
k = 0
# print(nodes)
for eleme in nodes:
lmarks[k] = (eleme, mid_t)
lmarks[k + 1] = (eleme, mid_t1)
k += 2
print('Landmarks: ' + str(lmarks))
print('\n')
# Call ifub_on_landmarks() on graph and landmarks
diam, num_visits_ifub, num_dist_A, num_dist_B, pairs_reach = ifub_on_landmarks(graph=g, landmarks=lmarks)
print('Diameter: ' + str(diam))
print('Number of visits: ' + str(num_visits_ifub))