ノードリスト内のエッジを取得

Question

両方のノードが与えられたノードのリスト内にあるすべてのエッジを取得する方法を教えてください。 G.edges([list_of_nodes])は、各エッジの少なくとも1つのノードがlist_of_nodesにあるすべてのノードを返します。私はそれを望んでいない。どうすれば入手できますか？

Answer 1

すでに見つかったすべてのエッジをループし、両方のノードがノードのリストにあるかどうかをテストできますが、ノードのリストが大きい場合は最適ではありません。リストに要素が含まれているかどうかを確認するには、リストを反復処理する必要があります。したがって、各エッジの平均エッジ数は2*len(list)/2です。各ノードのチェック数はlen(list)/2です。エッジの数がlen(list)に比例すると仮定すると、これには2次の時間があります。

edges = [(u,v) for u,v in G.edges(list_of_nodes) if u in list_of_nodes and v in list_of_nodes] 

より効率的な方法は、ノードがリストではなくセットに含まれているかどうかをテストします。セットは、要素が含まれているかどうかを非常に高速に確認できます。テストごとにほとんどO(1)です。したがって、完全なものは線形時間で実行されます。

set_of_nodes = set(list_of_nodes) 
edges = [(u,v) for u,v in G.edges(set_of_nodes) if u in set_of_nodes and v in set_of_nodes]