I have a list of paths taken from networkX by nx.shortest_simple_paths(g,s,d)
and the paths are:
[[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]]
What I am trying to do is to find two paths which are the least similar to each other, the disjointpaths
in networkX does not always return two paths in my case and I need exactly two.
Advertisement
Answer
nx.disjointpaths
finds paths that do not share any edge. While all of the paths in your input share edges, you can find the pairing of paths that have the fewest edges in common:
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)
Output:
('T1', 'E1B', 'E2B', 'ACD6B', 'DE6', 'T3') ('T1', 'E1B', 'ACD3B', 'DE2', 'DE4', 'DE6', 'T3')