import numpy as np
import backward_BFS as Bbfs
from utils import util
class ShortestPath:
def __init__(self):
self.__distances = []
self.__eccentricity = None
self.__idx_farther = None
self.__reachables = 0
self.__min_ecc = np.NINF # minimum possible eccentricity
self.__name = 'SP' # Shortest Path
self.__opposite_path = None
def get_distances(self):
return self.__distances
def get_idx_farther(self):
return self.__idx_farther
def get_eccentricity(self):
return self.__eccentricity
def compare_eccentricity(self, ecc, idx):
if self.__eccentricity > ecc:
return self.__eccentricity, self.__idx_farther
else:
return ecc, idx
def get_min_ecc(self):
return self.__min_ecc
def get_reachables(self):
return self.__reachables
def get_name(self):
return self.__name
def gen_opposite(self, folder, file):
self.__opposite_path = util.opposite_graph_ascend_traversal(folder=folder, file=file)
return self.__opposite_path
def __compute_sp(self, u, v, t, traversal_time, start_node, list_of_sorted_lists):
# print(list_of_sorted_lists)
if u == start_node:
if (0, t) not in list_of_sorted_lists[start_node]:
list_of_sorted_lists[start_node].append((0, t))
if list_of_sorted_lists[u]: # check if list is not empty
for i, elem in enumerate(list_of_sorted_lists[u]):
if elem[1] <= t:
new_d = elem[0] + traversal_time
new_arrival_time = t + traversal_time
inserted_new = False # True if new element is inserted
if not list_of_sorted_lists[v]: # Check if list is empty
list_of_sorted_lists[v].append((new_d, new_arrival_time))
inserted_new = True
else:
same_arrival = False # True if there is another elem. with same arrival time into the list
for j, e in enumerate(list_of_sorted_lists[v]):
if e[1] == new_arrival_time:
if e[0] > new_d:
list_of_sorted_lists[v][j] = (new_d, new_arrival_time)
inserted_new = True
same_arrival = True
if not same_arrival:
# check if new path is dominated
new_is_dominated = False
for pair in list_of_sorted_lists[v]:
if (pair[0] < new_d and pair[1] <= new_arrival_time) or (
pair[0] == new_d and pair[1] < new_arrival_time):
new_is_dominated = True
if not new_is_dominated:
list_of_sorted_lists[v].append((new_d, new_arrival_time))
inserted_new = True
if inserted_new:
# keep only not dominated paths
list_of_sorted_lists[v][:] = [e for e in list_of_sorted_lists[v] if not (
(e[0] > new_d and e[1] >= new_arrival_time) or (
e[0] == new_d and e[1] > new_arrival_time))]
# If the minimum duration changes, update it
if new_d < self.__distances[v]:
self.__distances[v] = new_d
# sort list
list_of_sorted_lists[v].sort(key=lambda tup: tup[0])
break
else:
continue
def compute_distances(self, graph, start_node, min_time=None, max_time=None):
"""
:param graph: temporal graph
:param start_node: node to start from
:param min_time: lower bound time interval
:param max_time: upper bound time interval
:return: numpy array of duration of the fastest path from start_node to every nodes v in V within time interval
"""
if graph.get_latest_node() is not None:
raise Exception('Shortest path does not work with dummy nodes, give me in input weighted graph!')
if min_time is None:
min_time, _ = graph.get_time_interval()
if max_time is None:
_, max_time = graph.get_time_interval()
list_of_sorted_lists = []
for elem in range(graph.get_num_nodes()):
list_of_sorted_lists.append([])
self.__eccentricity = 0
self.__idx_farther = start_node
self.__distances = np.full((graph.get_num_nodes(),), np.inf)
self.__distances[start_node] = 0
for line in graph.graph_reader():
if not line.strip(): # check if line is blank
break
li = line.split()
u = int(li[0])
v = int(li[1])
t = int(li[2])
if len(li) == 4:
traversal_time = int(li[3])
else:
traversal_time = 1
if t >= min_time and t + traversal_time <= max_time:
self.__compute_sp(u=u, v=v, t=t, traversal_time=traversal_time, start_node=start_node,
list_of_sorted_lists=list_of_sorted_lists)
if not graph.get_is_directed():
self.__compute_sp(u=v, v=u, t=t, traversal_time=traversal_time, start_node=start_node,
list_of_sorted_lists=list_of_sorted_lists)
elif t >= max_time:
break
# To handle dummy nodes: discard them from the distances vector
# if graph.get_latest_node() is not None:
# self.__distances = self.__distances[:graph.get_latest_node()]
self.__idx_farther, self.__eccentricity, self.__reachables = util.get_max_ind(self.__distances, np.NINF)
class FastestPathOnePass:
def __init__(self):
self.__distances = []
self.__eccentricity = None
self.__idx_farther = None
self.__min_ecc = np.NINF # minimum possible eccentricity
self.__reachables = 0
self.__name = 'FP' # Fastest Path
self.__opposite_path = None
def get_distances(self):
return self.__distances
def get_idx_farther(self):
return self.__idx_farther
def get_eccentricity(self):
return self.__eccentricity
def compare_eccentricity(self, ecc, idx):
if self.__eccentricity > ecc:
return self.__eccentricity, self.__idx_farther
else:
return ecc, idx
def get_min_ecc(self):
return self.__min_ecc
def get_reachables(self):
return self.__reachables
def get_name(self):
return self.__name
def gen_opposite(self, folder, file):
self.__opposite_path = util.opposite_graph_ascend(folder=folder, file=file)
return self.__opposite_path
def __compute_fp(self, u, v, t, start_node, list_of_queues):
if u == start_node:
if (t, t) not in list_of_queues[start_node]:
list_of_queues[start_node].append((t, t))
if list_of_queues[u]: # check if list is not empty
for i, elem in reversed(list(enumerate(list_of_queues[u]))):
if elem[1] <= t:
list_of_queues[u] = list_of_queues[u][i:]
new_t = elem[0]
new_arrival_time = t + 1 # traversal_time = 1
if not list_of_queues[v]: # Check if list is empty
list_of_queues[v].append((new_t, new_arrival_time))
# If the old path dominates the new (or they are equals), keep only the old
elif (list_of_queues[v][-1][0] >= new_t and
list_of_queues[v][-1][1] <= new_arrival_time):
break
# If new path dominates the old, keep only the new
elif (list_of_queues[v][-1][0] < new_t and
list_of_queues[v][-1][1] >= new_arrival_time) or (list_of_queues[v][-1][0] == new_t and
list_of_queues[v][-1][
1] > new_arrival_time):
list_of_queues[v][-1] = (new_t, new_arrival_time)
# Otherwise keep both (newest is added after the oldest)
else:
list_of_queues[v].append((new_t, new_arrival_time))
# If the minimum duration changes, update it
if list_of_queues[v][-1][1] - list_of_queues[v][-1][0] < self.__distances[v]:
self.__distances[v] = list_of_queues[v][-1][1] - list_of_queues[v][-1][0]
break
else:
continue
def compute_distances(self, graph, start_node, min_time=None, max_time=None):
"""
:param graph: temporal graph
:param start_node: node to start from
:param min_time: lower bound time interval
:param max_time: upper bound time interval
:return: numpy array of duration of the fastest path from start_node to every nodes v in V within time interval
"""
if min_time is None:
min_time, _ = graph.get_time_interval()
if max_time is None:
_, max_time = graph.get_time_interval()
list_of_queues = []
for elem in range(graph.get_num_nodes()):
list_of_queues.append([])
self.__eccentricity = 0
self.__idx_farther = start_node
self.__distances = np.full((graph.get_num_nodes(),), np.inf)
self.__distances[start_node] = 0
for line in graph.graph_reader():
if not line.strip(): # check if line is blank
break
li = line.split()
u = int(li[0])
v = int(li[1])
t = int(li[2])
if t >= min_time and t + 1 <= max_time:
self.__compute_fp(u=u, v=v, t=t, start_node=start_node, list_of_queues=list_of_queues)
if not graph.get_is_directed():
self.__compute_fp(u=v, v=u, t=t, start_node=start_node, list_of_queues=list_of_queues)
elif t >= max_time:
break
# To handle dummy nodes: discard them from the distances vector
if graph.get_latest_node() is not None:
self.__distances = self.__distances[:graph.get_latest_node()]
self.__idx_farther, self.__eccentricity, self.__reachables = util.get_max_ind(self.__distances, np.NINF)
class EarliestArrivalPath:
def __init__(self):
self.__distances = []
self.__eccentricity = None
self.__idx_farther = None
self.__min_ecc = np.NINF # minimum possible eccentricity
self.__name = 'EAT'
def get_distances(self):
return self.__distances
def get_eccentricity(self):
return self.__eccentricity
def get_idx_farther(self):
return self.__idx_farther
def compare_eccentricity(self, ecc, idx):
if self.__eccentricity > ecc:
return self.__eccentricity, self.__idx_farther
else:
return ecc, idx
def get_min_ecc(self):
return self.__min_ecc
def get_name(self):
return self.__name
def compute_distances(self, graph, start_node, min_time=None, max_time=None):
"""
:param graph: temporal graph in its edge stream representation
:param start_node: node to start from
:param min_time: lower bound time interval
:param max_time: upper bound time interval
:return: numpy array of the earliest arrival times from start_node to every nodes v in V within time interval
"""
if min_time is None:
min_time, _ = graph.get_time_interval()
if max_time is None:
_, max_time = graph.get_time_interval()
self.__eccentricity = min_time
self.__idx_farther = start_node
self.__distances = np.full((graph.get_num_nodes(),), np.inf)
self.__distances[start_node] = min_time
traversal_time = 1
for line in graph.graph_reader():
if not line.strip(): # check if line is blank
break
li = line.split()
u = int(li[0])
v = int(li[1])
t = int(li[2])
if len(li) == 4:
traversal_time = int(li[3])
if (t + traversal_time) <= max_time:
if t >= self.__distances[u]:
if (t + traversal_time) < self.__distances[v]:
self.__distances[v] = t + traversal_time
if self.__distances[v] > self.__eccentricity and \
(graph.get_latest_node() is None or v < graph.get_latest_node()): # to handle dummy
self.__eccentricity = self.__distances[v]
self.__idx_farther = v
elif not graph.get_is_directed() and t >= self.__distances[v]: # If graph is undirected
if (t + traversal_time) < self.__distances[u]:
self.__distances[u] = t + traversal_time
if self.__distances[u] > self.__eccentricity and \
(graph.get_latest_node() is None or u < graph.get_latest_node()): # to handle dummy
# nodes
self.__eccentricity = self.__distances[u]
self.__idx_farther = u
elif t >= max_time:
break
else:
continue
# To handle dummy nodes: discard them from the distances vector
if graph.get_latest_node() is not None:
self.__distances = self.__distances[:graph.get_latest_node()]
class LatestDeparturePath: # ( method compute_distances() compute backward LDT)
def __init__(self):
self.__distances = []
self.__eccentricity = None
self.__idx_farther = None
self.__min_ecc = np.inf # minimum possible eccentricity
self.__name = 'LDT'
def get_distances(self):
return self.__distances
def get_eccentricity(self):
return self.__eccentricity
def get_idx_farther(self):
return self.__idx_farther
def compare_eccentricity(self, ecc, idx):
if self.__eccentricity < ecc:
return self.__eccentricity, self.__idx_farther
else:
return ecc, idx
def get_min_ecc(self):
return self.__min_ecc
def get_name(self):
return self.__name
def compute_distances(self, graph, start_node, min_time=None, max_time=None):
"""
:param graph: temporal graph in REVERSE EDGE STREAM representation
:param start_node: destination node
:param min_time: lower bound time interval
:param max_time: upper bound time interval
:return: numpy array of the latest departure times from every vertex v in V to dest_node within time interval
"""
if min_time is None:
min_time, _ = graph.get_time_interval()
if max_time is None:
_, max_time = graph.get_time_interval()
self.__eccentricity = max_time
self.__idx_farther = start_node
self.__distances = np.full((graph.get_num_nodes(),), np.NINF)
self.__distances[start_node] = max_time
traversal_time = 1
for line in graph.graph_reader():
if not line.strip(): # check if line is blank
break
li = line.split()
u = int(li[0])
v = int(li[1])
t = int(li[2])
if len(li) == 4:
traversal_time = int(li[3])
if t >= min_time:
if t + traversal_time <= self.__distances[v]:
if t > self.__distances[u]:
self.__distances[u] = t
# I can compute eccentricity here (online) because the graph is in reverse edge stream
if self.__distances[u] < self.__eccentricity and \
(graph.get_latest_node() is None or u < graph.get_latest_node()):
self.__eccentricity = self.__distances[u]
self.__idx_farther = u
elif not graph.get_is_directed() and t + traversal_time <= self.__distances[u]:
if t > self.__distances[v]:
self.__distances[v] = t
if self.__distances[v] < self.__eccentricity and \
(graph.get_latest_node() is None or v < graph.get_latest_node()):
self.__eccentricity = self.__distances[v]
self.__idx_farther = v
else:
break
# To handle dummy nodes: discard them from the distances vector
if graph.get_latest_node() is not None:
self.__distances = self.__distances[:graph.get_latest_node()]
# self.__idx_farther, self.__eccentricity = util.get_min_ind(self.__distances, np.inf)
def compute_diameter(graph, distance):
"""
:param graph: temporal graph
:param distance: Object distance: FastestPathOnePass, earliestArrivalPath etc...
:return: diameter value
"""
ecc = distance.get_min_ecc()
idx = -1
reachable_pairs = 0
if graph.get_latest_node() is not None:
num_nodes = graph.get_latest_node()
else:
num_nodes = graph.get_num_nodes()
for node in range(num_nodes):
distance.compute_distances(graph=graph, start_node=node)
if distance.get_name() == 'FP' or distance.get_name() == 'SP':
reachable_pairs += distance.get_reachables()
ecc, idx = distance.compare_eccentricity(ecc, idx)
# print(ecc)
if (node + 1) % 1000 == 0:
print('1000 visits done...', flush=True)
if distance.get_name() == 'FP' or distance.get_name() == 'SP':
print('Reachable Pairs ' + graph.get_file_path().rsplit('/', 1)[1] + ': ' + str(reachable_pairs), flush=True)
return ecc
if __name__ == '__main__':
import temporal_graph as tg
sp_distance = ShortestPath()
g = tg.Graph(file_path='./graphs/Weighted/kuopio-weighted-sorted.txt', is_directed=True)
sp_dist = ShortestPath()
diam = compute_diameter(graph=g, distance=sp_distance)
print('diam:')
print(diam)
