Python從邊緣流連接的組件

Question

我想從一個邊緣流找到連接組件

在輸入我有一個這樣的流：

edges_in : [(e1,e2),(e2,e3),(e3,e1),(e5,e6)] 
edges_out: : [(e1,e2)] 

我正在尋找一種算法有輸出：

connected_edges : [[(e2,e3),(e3,e1)],[(e5,e6)]] 

而從這個名單connected_edges有：

connected_nodes : [[e2,e3,e1],[e5,e6]] 

我需要有這種方法保持部件

我已經嘗試了所有圖形庫（如networkX，IGRAPH）在Python和在網絡，但任何工作的一些代碼。

您的幫助很寶貴。

Answer 1

看起來像disjoint-set data structure可以解決這個問題。

該數據結構具有在線將組件連接到組件的功能。並且在每個組中您都可以使用已用邊的標籤。