CODEWITHSUNDEEP
pythongraph-theorynetworkx
xiaohan2012
xiaohan2012

Reputation: 10322

Fast way to get edges crossing two sets of nodes in networkx.Graph

What's the fasted way in networkx to get the crossing edges between two disjoint node sets? Is there some ready-made function to use?

The way I am using now:

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]]

Upvotes: 3

Views: 4041

Answers (3)

insanely_sin
insanely_sin

Reputation: 1026

You can use the edge_boundary function in Networkx.

The edge boundary of a set S with respect to a set T is the set of edges (u, v) such that u is in S and v is in T.

This is also called a cut-set, the set of edges that have one endpoint in each subset of the partition.

Upvotes: 8

Erotemic
Erotemic

Reputation: 5228

This is an old thread but here is the solution I'm working with. 

def edges_cross(graph, nodes1, nodes2):
    """
    Finds edges between two sets of disjoint nodes.
    Running time is O(len(nodes1) * len(nodes2))

    Args:
        graph (nx.Graph): an undirected graph
        nodes1 (set): set of nodes disjoint from nodes2
        nodes2 (set): set of nodes disjoint from nodes1.
    """
    return {(u, v) for u in nodes1
            for v in nodes2.intersection(graph.adj[u])}

If n=len(nodes1) and m=len(nodes2) then this algorithm will run in O(nm) because there are n iterations of the outer loop. Each inner loop calls nodes2.intersection will runs in O(m) time as long as graph.adj[u] is a set (it is actually a dict, but this will operate on its keys which quack like a set). See python docs for more details about set intersection running time.

I also have a function for edges inside of a set of nodes which runs in O(n^2) by a similar argument, but it contains a few tricks to reduce the constant factor as well. 

def edges_inside(graph, nodes):
    """
    Finds edges within a set of nodes
    Running time is O(len(nodes) ** 2)

    Args:
        graph (nx.Graph): an undirected graph
        nodes1 (set): a set of nodes
    """
    result = set([])
    upper = nodes.copy()
    graph_adj = graph.adj
    for u in nodes:
        for v in upper.intersection(graph_adj[u]):
            result.add((u, v))
        upper.remove(u)
    return result

Upvotes: 0

Ante
Ante

Reputation: 5448

It depends on assumptions about the graph.

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

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

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)

Possible optimization is to set A to be smaller of two input sets.

Upvotes: 0

Related Questions