Fast way to get edges crossing two sets of nodes in networkx.Graph
<p>What's the fasted way in <code>networkx</code> to get the crossing edges between two disjoint node sets? 
Is there some ready-made function to use?</p>

<p>The way I am using now:</p>

<pre><code>import networkx as nx
from itertools import product
A = set(range(50))
B = set(range(50, 100))
g = nx.complete_graph(100)
cross_edges = [(n1, n2)
  for n1, n2 in product(A, B)
  if n1 in g.adj and n2 in g.adj[n1]]
</code></pre>

<p>It depends on assumptions about the graph.</p>

<p>If graph is dense than your approach is optimal since set of result edges is almost the same as <code>product(A,B)</code>. Than it is goot to iterate through all possible edges (<code>product(A,B)</code>) and check is it an edge.</p>

<p>If graph is sparse than it would be faster to iterate through existing edges and check for edges between A and B. Something like:</p>

<pre><code>Bs = set(B)            # 'in' operator is faster for sets
result = []
for n1 in A:           # Iterate through first set
  for n2 in g.adj[n1]: # Than through edges connected to a node
    if n2 in Bs:       # Check is it edge between A and B
      result.append(n1, n2)
</code></pre>

<p>Possible optimization is to set A to be smaller of two input sets.</p>

python graph-theory networkx