title: What's the most efficient way to extract an edge list from a huge adjacency list?
body: <p>This might be a stupid question, but let's say I have a large (~billions of lines) CSV file which contains adjacency lists where the vertices are represented by strings like:</p>
  
  <pre><code>+------------+---------------------------+
  |     id     |         neighbors         |
  +------------+---------------------------+
  | 'james'    | 'michael, jane, pete'     |
  | 'doug'     | 'cliff'                   |
  | 'amy'      | 'bobby, russell, richard' |
  | 'richard'  | 'kam, earl, cliff'        |
  | 'marshawn' |                           |
  | 'bobby'    | 'emily, james, doug'      |
  +------------+---------------------------+
  </code></pre>
  
  <p>From these kinds of adjacency lists, all I want to do is output a vertex set and an edge set comprised of <strong>undirected</strong> pairs of vertices. That is all.</p>
  
  <p><strong>What is the most efficient strategy to accomplish this, and how do we implement it in Python?</strong></p>
  
  <p>For the sake of brevity in outlining the algorithm below, let:</p>
  
  <ul>
  <li><code>add('bobby')</code>: operation to add vertex 'bobby' to the vertex set </li>
  <li><code>edge('bobby','emily')</code>: operation to add ('bobby', 'emily') to the edge set</li>
  <li><code>ingraph('bobby')</code>: check if vertex 'bobby' is in vertex set</li>
  </ul>
  
  <p>Suppose we take the approach of starting with an empty graph and adding vertices sequentially. Then my first try (in very raw psuedocode) would be something like:</p>
  
  <pre><code>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]
  </code></pre>
  
  <ol>
  <li>Is there an obvious way to improve this algorithm in general (independent of Python)?</li>
  <li>What's the best way to implement such a solution in Python? Iterating through the raw CSV file? Loading it into <code>pandas</code> and using <code>numpy</code> to vectorize this somehow (assuming I have enough memory...)?</li>
  </ol>
  
  <p><strong>EDIT:</strong> By writing "neighbors" I hoped to make it clear that I just want an undirected graph. Sorry if this wasn't obvious.</p>