С 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)
даване:
[['a', 'd', 'e', 'b', 'c'], ['f', 'g']]
Сега трябва да проверите най-бързия алгоритъм ...
OP:
Това работи чудесно! Сега имам това в моята база данни PostgreSQL. Просто организирайте двойки в таблица с две колони, след което използвайте array_agg()
за преминаване към функцията на PL/Python get_connected()
. Благодаря.
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;
(Забележка:редактирах отговора, тъй като реших, че показването на тази стъпка може да е полезно допълнение, но твърде дълго за коментар.)