Cách tổng hợp các cặp phù hợp thành các thành phần được kết nối trong Python

Với networkX:

import networkx as nx
G1=nx.Graph()
G1.add_edges_from([("a","b"),("b","c"),("c","d"),("d","e"),("f","g")])
sorted(nx.connected_components(G1), key = len, reverse=True)

tặng:

[['a', 'd', 'e', 'b', 'c'], ['f', 'g']]

Bạn phải kiểm tra thuật toán nhanh nhất bây giờ ...

OP:

Điều này hoạt động tuyệt vời! Tôi có cái này trong cơ sở dữ liệu PostgreSQL của tôi bây giờ. Chỉ cần tổ chức các cặp thành một bảng hai cột, sau đó sử dụng array_agg() để chuyển đến hàm PL / Python get_connected() . Cảm ơn.

CREATE OR REPLACE FUNCTION get_connected(
    lhs text[],
    rhs text[])
  RETURNS SETOF text[] AS
$BODY$
    pairs = zip(lhs, rhs)

    import networkx as nx
    G=nx.Graph()
    G.add_edges_from(pairs)
    return sorted(nx.connected_components(G), key = len, reverse=True)

$BODY$ LANGUAGE plpythonu;

(Lưu ý:Tôi đã chỉnh sửa câu trả lời, vì tôi nghĩ việc hiển thị bước này có thể là phụ lục hữu ích, nhưng quá dài cho một nhận xét.)