backward_BFS.py
import numpy as np
from utils import util
class TemporalBackwardBFS:
def __init__(self, graph, start_node):
"""
Temporal Backward BFS on graph "graph", it must be in reverse edge stream representation
N.B. If you use TemporalBackwardBFS to compute fw LDT you must change the sign of distances and eccentricity
"""
self.__n_nodes = graph.get_num_nodes()
self.__graph = graph
# self.__file_path = graph.get_file_path()
self.__is_directed = graph.get_is_directed()
self.__s = start_node
self.__min_time, self.__max_time = graph.get_time_interval()
self.__node_interval = []
self.__eat = []
self.__dur = []
self.__eccentricity_eat = None
self.__idx_farther_eat = None
self.__reachables = 0
def get_eat(self):
if len(self.__eat) == 0:
self.bfs()
return self.__eat
def get_dur(self):
if len(self.__dur) == 0:
self.bfs()
return self.__dur
def get_eccentricity_eat(self):
if self.__eccentricity_eat is None:
self.bfs()
return self.__eccentricity_eat
def get_idx_farther_eat(self):
"""
Return the index of node with highest eccentricity
"""
if self.__idx_farther_eat is None:
self.bfs()
return self.__idx_farther_eat
def get_graph_iter(self):
return self.__graph.graph_reader()
def get_reachables(self):
return self.__reachables
def bfs(self):
"""
We assume constant traversal times
"""
self.__eat = np.full((self.__n_nodes,), np.inf)
self.__dur = np.full((self.__n_nodes,), np.inf)
self.__eat[self.__s] = self.__min_time
self.__dur[self.__s] = 0
self.__eccentricity_eat = self.__min_time
self.__idx_farther_eat = self.__s
# self.node_interval = np.full((self.n_nodes,), Interval(np.inf, np.inf, np.inf, np.inf, np.inf))
for i in range(self.__n_nodes):
self.__node_interval.append(Interval(np.inf, np.inf, np.inf, np.inf, np.inf))
last_t = self.__min_time - 1
# with open(self.__file_path) as f:
for line in self.get_graph_iter():
if not line.strip(): # check if line is blank
break
li = line.split()
# if len(li) != 3:
# raise Exception('Line ' + line + ' not have correct number of fields')
u = int(li[0])
v = int(li[1])
t = int(li[2])
if self.__min_time <= t <= self.__max_time:
if last_t != t:
self.__node_interval[self.__s].set(t + 1, t, t + 1, t, t + 1)
last_t = t
lsu = self.__node_interval[u].min_s()
lsv = self.__node_interval[v].min_s()
prev_lsv = self.__node_interval[v].max_s()
prev_lsu = self.__node_interval[u].max_s()
if lsu[1] > t and lsv[1] > t:
if not self.__is_directed and lsu[0] < lsv[0]:
self.__node_interval[v].set_max(lsu[0], lsv[0], t)
self.__eat[v] = lsu[0] + 1
self.__dur[v] = lsu[0] - t + 1
elif lsu[0] > lsv[0]:
self.__node_interval[u].set_max(lsv[0], lsu[0], t)
self.__eat[u] = lsv[0] + 1
self.__dur[u] = lsv[0] - t + 1
elif lsu[1] > t and lsv[1] == t:
if not self.__is_directed and lsu[0] < lsv[0]:
self.__node_interval[v].set_min(lsu[0])
self.__eat[v] = lsu[0] + 1
self.__dur[v] = lsu[0] - t + 1
elif lsu[0] > prev_lsv[0]:
self.__node_interval[u].set_max(prev_lsv[0], lsu[0], t)
self.__eat[u] = prev_lsv[0] + 1
self.__dur[u] = prev_lsv[0] - t + 1
elif lsu[1] == t and lsv[1] > t:
if lsv[0] < lsu[0]:
self.__node_interval[u].set_min(lsv[0])
self.__eat[u] = lsv[0] + 1
self.__dur[u] = lsv[0] - t + 1
elif not self.__is_directed and lsv[0] > prev_lsu[0]:
self.__node_interval[v].set_max(prev_lsu[0], lsv[0], t)
self.__eat[v] = prev_lsu[0] + 1
self.__dur[v] = prev_lsu[0] - t + 1
elif lsu[1] == t and lsv[1] == t:
if prev_lsv[0] < lsu[0]:
self.__node_interval[u].set_min(prev_lsv[0])
self.__eat[u] = prev_lsv[0] + 1
self.__dur[u] = prev_lsv[0] - t + 1
elif not self.__is_directed and prev_lsu[0] < lsv[0]:
self.__node_interval[v].set_min(prev_lsu[0])
self.__eat[v] = prev_lsu[0] + 1
self.__dur[v] = prev_lsu[0] - t + 1
if self.__graph.get_latest_node() is not None:
self.__eat = self.__eat[:self.__graph.get_latest_node()]
self.__idx_farther_eat, self.__eccentricity_eat, self.__reachables = util.get_max_ind(self.__eat, np.NINF)
class Interval:
def __init__(self, r, l1, s1, l2, s2):
self.__r = r
self.__l1 = l1
self.__s1 = s1
self.__l2 = l2
self.__s2 = s2
def set(self, r, l1, s1, l2, s2):
self.__r = r
self.__l1 = l1
self.__s1 = s1
self.__l2 = l2
self.__s2 = s2
def max_s(self): # Get previous triple (oldest)
r = [self.__l1, self.__s1]
if self.__s2 > self.__s1:
r[0] = self.__l2
r[1] = self.__s2
return r
def min_s(self): # Get most recent triple (last inserted)
r = [self.__l1, self.__s1]
if self.__s2 < self.__s1:
r[0] = self.__l2
r[1] = self.__s2
return r
def set_max(self, li, r, t): # Update oldest triple
self.__r = r
if self.__s1 > self.__s2:
self.__l1 = li
self.__s1 = t
else:
self.__l2 = li
self.__s2 = t
def set_min(self, li): # Extend (update) most recent triple (with smaller t)
if self.__s1 < self.__s2:
self.__l1 = li
else:
self.__l2 = li