在列表中发现最少相关的/类似的列表

Question

我有一个nx.shortest_simple_paths(g,s,d)从nx.shortest_simple_paths(g,s,d)获取的路径列表，这些路径是：

[[T1, E1B, E2B, ACD6B, DE6, T3],
 [T1, E1B, ACD3B, ACD6B, DE6, T3],
 [T1, E1B, ACD3B, DE2, DE4, DE6, T3],
 [T1, E1B, E2B, ACD6B, ACD3B, DE2, DE4, DE6, T3]]

我想要做的是找到两条彼此最不相似的路径，networkX中的networkX并不总是返回两条路径，而我只需要两条路径。

Answer 1

nx.disjointpaths查找不共享任何边缘的路径。虽然输入中的所有路径都共享边缘，但您可以找到具有最少共同点的路径的配对：

def edges(p):
   return {(p[i], p[i+1]) for i in range(len(p)-1)}

paths = [['T1', 'E1B', 'E2B', 'ACD6B', 'DE6', 'T3'], ['T1', 'E1B', 'ACD3B', 'ACD6B', 'DE6', 'T3'], ['T1', 'E1B', 'ACD3B', 'DE2', 'DE4', 'DE6', 'T3'], ['T1', 'E1B', 'E2B', 'ACD6B', 'ACD3B', 'DE2', 'DE4', 'DE6', 'T3']]
r = {(tuple(j), tuple(k)):edges(j)&edges(k) for j in paths for k in paths if j!=k}
s1, s2 = min(r, key=lambda x:len(r[x]))
print(s1, s2)

输出：

('T1', 'E1B', 'E2B', 'ACD6B', 'DE6', 'T3') 
('T1', 'E1B', 'ACD3B', 'DE2', 'DE4', 'DE6', 'T3')