Concatenate 2d array rows if at least one value equals

Question

I am trying to achieve the following. Examining the matrix

[[ 9 10]
 [10  9]
 [11 17]
 [11 18]
 [12 13]
 [13 12]
 [17 11]
 [17 18]
 [18 11]
 [18 17]]

I want to "merge" all lines that have at least one similar value. In this example, I want to get

[[9,10]
[11, 17, 18]
[12, 13]]

I know that numpy works with fixed form arrays. So I'm trying to populate another nans array with these values. A simple approach would be a for loop, where I loop over each line, check if the array of results already has one of the values ​​and expands, if so, if not put in the next free line. I did this without numpy using a list of lists to host groups.

groups = []
for pair in matrix:
    pair = [pair[0], pair[1]]
    append_pair = True                
    for sublist in groups:
        if pair[0] in sublist or pair[1] in sublist:
            sublist.extend(x for x in pair if x not in sublist)
            append_pair = False
    if append_pair is True:
        groups.append(pair)

Is there a better way to do this?

Answer 1

Here is an optimized approach, but a bit hacked:

In [14]: def find_intersection(m_list):
            for i,v in enumerate(m_list) : 
                for j,k in enumerate(m_list[i+1:],i+1):
                       if np.in1d(v, k).any():
                              m_list[i] = np.union1d(v, m_list.pop(j))
                              return find_intersection(m_list)
            return m_list
   ....:         

In [15]: find_intersection(a)
Out[15]: [array([ 9, 10]), array([11, 17, 18]), array([12, 13])]

Answer 2

, , . networkx, networkx package connected_components .

import networkx as nx

G = nx.from_edgelist([[ 9, 10],
                     [10,  9],
                     [11, 17],
                     [11, 18],
                     [12, 13],
                     [13, 12],
                     [17, 11],
                     [17, 18],
                     [18, 11],
                     [18, 17]])
list(nx.connected_components(G))
[{9, 10}, {11, 17, 18}, {12, 13}]

numpy. , Scipy scipy.sparse.csgraph.connected_components. . networkx .