CODEWITHSUNDEEP
pythonpython-3.xgraphnetworkxcomputer-science
Umair Shahid
Umair Shahid

Reputation: 71

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

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.

Upvotes: 1

Views: 68

Answers (1)

Ajax1234
Ajax1234

Reputation: 71451

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

Upvotes: 1

Related Questions