在列表列表中查找 2 个最少 correlating/similar 列表

Question

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

[[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 中的 disjointpaths 在我的情况下并不总是 return 两条路径，我需要恰好二.

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')

在列表列表中查找 2 个最少 correlating/similar 列表

Finding 2 least correlating/similar lists in a list of lists

python

python-3.x

graph

networkx

computer-science