I have a collection of lists that each represent a path on a graph:
list1 = [1,2,3,6] # directed edge from 1->2, 2->3, 3->6
list2 = [8,3,5,6]
list3 = [9,1,3,4]
list4 = [7,8,1,4]
I also have the adjacency matrix of the graph.
At each time step I am given an edge:
e.g. time step 0: [1,2]
, time step 1: [3,6]
, and at each time step I have to find the most similar list, taking into account previous time steps. Meaning, the list that is the most complete.
What is an efficient way to do it?
I tried to use a naive approach, of comparing the incoming edges to every edge in every list, but considering I have a large number of lists, each with a large number of edges, this is too slow.
Update: writing an example input and output at each time step.
time step 0: input [1,2]
, output: list1
time step 1: input [8,3]
, output: list1, list2 #equally complete
time step 2: input [3,6]
, output: list1
Update 2: Thanks to @Nuclearman I coded (maybe naively?) the solution
list1 = [1,2,3,6] # directed edge from 1->2, 2->3, 3->6
list2 = [8,3,5,6]
list3 = [9,1,3,4]
list4 = [7,8,1,4]
lists_dict = {
'list1' : list1,
'list2' : list2,
'list3' : list3,
'list4' : list4
}
edges = {
'list1' : len(list1) - 1,
'list2' : len(list2) - 1,
'list3' : len(list3) - 1,
'list4' : len(list4) - 1
}
covered_edges = {
'list1' : 0,
'list2' : 0,
'list3' : 0,
'list4' : 0
}
completeness = {
'list1' : covered_edges['list1']/edges['list1'],
'list2' : covered_edges['list2']/edges['list2'],
'list3' : covered_edges['list3']/edges['list3'],
'list4' : covered_edges['list4']/edges['list4']
}
graph = {}
for list_name in lists_dict.keys():
idx = 0
while idx < len(lists_dict[list_name])-1:
node1 = lists_dict[list_name][idx]
node2 = lists_dict[list_name][idx+1]
if node1 in graph.keys(): #if exist
graph[node1][node2] = list_name
else: #if doesnt exist
graph[node1] = {node2: list_name}
idx+=1
times= [[1,2],[3,5],[5,6],[8,1],[7,8]]
for time in times:
edge_in_list = graph[time[0]][time[1]] #list name
covered_edges[edge_in_list] +=1
print(covered_edges)
completeness = {
'list1' : covered_edges['list1']/edges['list1'],
'list2' : covered_edges['list2']/edges['list2'],
'list3' : covered_edges['list3']/edges['list3'],
'list4' : covered_edges['list4']/edges['list4']
}
mx = max(completeness.values())
max_list = [k for k, v in completeness.items() if v == mx]
print(max_list)
print('')