Graph Relationship between list of tuples

Question

I have a list of tuples, let's say

tuplist = [('a','b'),('a','c'),('e','f'),('f','c'),('d','z'),('z','x')]

I am trying to get the following :

('a','b','c','e','f'),('d','z','x')

This is all the elements linked together (like a tree in graph theory) The order inside the above tuples (can be lists too) does not matter.

I have managed to get a dict of all links for a single element but I am struggling to get to the final result in a clean and efficient way... Here is my code so far :

ll=[('a','b'),('a','c'),('e','f'),('f','c'),('d','z'),('z','x')]
total = {}
total2={}
final=[]
for element in set([item for sublist in ll for item in sublist]):
    tp = []
    for tupl in ll:
        if element in tupl: 
            tp.append(tupl)

    tp = list(frozenset([item for sublist in tp for item in sublist]))
    total[element] = tp
print(total)

before I get into your code, here's a helpful link https://en.wikipedia.org/wiki/Component_(graph_theory) I would pay special attention to the part about https://en.wikipedia.org/wiki/Disjoint-set_data_structure — Kenny Ostrom, Sep 26 '19 at 14:39

yatu · Accepted Answer · 2019-09-26T14:42:49.583

2

Similarly to this post, what you're looking for are known as the connected components of a graph. A simple way is to build a graph with networkx, and find the connected_components:

tuplist = [('a','b'),('a','c'),('e','f'),('f','c'),('d','z'),('z','x')]

import networkx as nx 

G=nx.Graph()
G.add_edges_from(tuplist)
list(nx.connected_components(G))
# [{'a', 'b', 'c', 'e', 'f'}, {'d', 'x', 'z'}]

edited Sep 26 '19 at 14:42

answered Sep 26 '19 at 14:40

yatu

86,083
12
84
139

1

I didn't see any mention of this during my searches but I am not familiar with the graph theory, just stumbled on it while looking to solve my problem. Thanks a lot ! – Mayeul sgc Sep 26 '19 at 14:50

score -1 · Answer 2 · answered Sep 26 '19 at 14:52

Optional recursive solution, although not nearly as elegent as @yatu's solution with networkx:

tuplist = [('a','b'),('a','c'),('e','f'),('f','c'),('d','z'),('z','x')]
def get_graphs(start, c = [], seen = []):
  _r = [b for a, b in tuplist if a == start and b not in seen]+[a for a, b in tuplist if b == start and a not in seen]
  if _r:
     yield from [i for b in _r for i in get_graphs(b, c=c+[start, b, *_r], seen = seen+[start, b])]
  else:
     yield set(c)
     _r = [a for a, _ in tuplist if a not in seen]
     yield from ([] if not _r else get_graphs(_r[0], c = [], seen= seen))


result = list(get_graphs(tuplist[0][0]))
final_result = [a for i, a in enumerate(result) if all(all(k not in b for k in a) for b in result[i+1:])]
to_tuples = list(map(tuple, final_result))

Output:

[('f', 'e', 'a', 'c', 'b'), ('z', 'd', 'x')]

Graph Relationship between list of tuples

2 Answers2