巨大な隣接リストからエッジリストを抽出する最も効率的な方法は何ですか？

Question

これは愚かな質問であってもよいが、のは、私は大きなを持っているとしましょうかもしれません（〜ラインの十億）の頂点のような文字列で表され隣接リスト含まれているCSVファイル：隣接リストのこれらの種類の中から

+------------+---------------------------+ 
|  id  |   neighbors   | 
+------------+---------------------------+ 
| 'james' | 'michael, jane, pete'  | 
| 'doug'  | 'cliff'     | 
| 'amy'  | 'bobby, russell, richard' | 
| 'richard' | 'kam, earl, cliff'  | 
| 'marshawn' |       | 
| 'bobby' | 'emily, james, doug'  | 
+------------+---------------------------+ 

を私がしたいのは、頂点セットと、の無指向のの頂点のペアで構成されるエッジセットです。それだけです。

これを達成するための最も効率的な戦略は何ですか？また、これをPythonでどのように実装しますか？以下のアルゴリズムを概説で簡潔にするために

は、ましょう：

• add('bobby')：頂点に頂点「ボビー」を追加する操作は、
• edge('bobby','emily')を設定：動作（「ボビー」を追加するために、 「エミリー」）エッジへ
• ingraph('bobby')を設定します。頂点「ボビー」は頂点であるかどうかを確認、我々が取ると

を設定空のグラフから始まり、順番に頂点を追加するアプローチ。次に、（非常に生擬似コードで）私の最初の試みは、のようになります。

ids = [...all id's in the CSV...] 
unexplored = list(ids) 

for i in ids: 
    add(i) 
    for j in unexplored: 
     if i in neighbors(j): 
      if not ingraph(j): add(j) 
      edge(i, j)    
    del unexplored[0] 

1. 一般（パイソンの独立した）に、このアルゴリズムを改善するための明確な方法はありますか？
2. このようなソリューションをPythonで実装する最も良い方法は何ですか？生のCSVファイルを反復処理しますか？ pandasにロードし、numpyを使ってこれを何らかの形でベクトル化します（十分なメモリがあると仮定して...）。

EDIT：書き込むことにより「隣人」私はそれを明確に私は無向グラフにしたいことを確認することを望みました。申し訳ありませんが、これは明らかではない場合。

Answer 1

私は右のあなたを理解していれば、あなたはG（V、E）のように表さグラフを持つようにしたいですあなたが何らかの方法で考える必要がある、それらを表現するために、曖昧さが無くなっています。どちらの方向にも注意を払わず、どちらか一方にエッジがあるかどうかを常に確認するか、正規化します。タプルには英数字ソートを使用します。

だから、我々はあなたが後者を選択したと仮定し、追加して、あなたは自分のファイル、行ずつ処理することができます定義された後、Eは、エントリはこれで

e = (v1, v2), v1 < v2. 

厳密な順序に従うタプルの集合であり、 IDをSet Vに設定し、近傍番号(ID, neighbor)または(neighbor, ID)を含むタプルを英数字の順序で作成し、これをSet Eに追加します。

エッジの正規表現に固執すると、Pythonは一意の要素の順序付けられていないセットとして定義されているので、Setにエッジの重複はありません。 https://docs.python.org/2/library/sets.html

ファイルが正しいと仮定でき、エッジがない場合（IDがないため）、エッジを最初に作成し、後で - 到着したら対応する行で、頂点を作成します。
この仮定を保持することができない場合でも、この方法でグラフ表現を作成することができます。最後にクリーンアップを実装する必要があります。そこでは、エッジセットをもう一度繰り返し、任意の辺がどこにも残っていない（存在しない頂点を指す）か、このエッジを削除するか、または頂点を作成することによって、これを処理します。

Answer 2

編集2 - 右向きの無向グラフで、エッジと頂点を出力したいだけです。derMはそれを持っています。あなたのデータのサイズを気にするだけで、素早く成長します。これはもともとグラフを作成してエッジリストを抽出しないことではありませんか？ EとしてVとEはV erticesとE地区ガバナーエレクト

を持つ2枚のセットです