networkx.Graph의 두 노드 집합을 교차하는 가장자리를 얻는 빠른 방법

Question

networkx의 두 단절된 노드 집합 사이에 교차 모서리를 얻기 위해 단식하는 방법은 무엇입니까? 사용할 기성품이 있습니까? 내가 지금 사용하고

방법은 :

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

Answer 1

이 그래프에 대한 가정에 따라 달라집니다.

결과 가장자리가 product(A,B)과 거의 같아서 그래프가 고밀도 인 경우 최적보다 좋습니다. 가능한 모든 가장자리 (product(A,B))를 반복하고 goog가 가장자리인지 확인하십시오.

그래프처럼 기존 에지 반복 a 및 B. 무언가 사이의 에지를 검사하기 위해 빠른 것보다 희박한 경우

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) 

가능한 최적화는 두 개의 입력 세트 작게 설정하는 것이다 .

Answer 2

이것은 오래된 스레드이지만 여기에 나와있는 해결책이 있습니다.

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

n=len(nodes1) 및 m=len(nodes2) 경우 외부 루프의 n 개의 반복이 있기 때문에 다음이 알고리즘은 O(nm)에서 실행됩니다. 각 내부 루프는 을 호출하며 graph.adj[u]이 집합 인 한 O(m) 시간에 실행됩니다 (실제로는 dict이지만 이것은 세트와 같은 돌팔매질하는 키에서 작동합니다). 교차로 실행 시간 설정에 대한 자세한 내용은 python docs을 참조하십시오.

비슷한 인수로 O(n^2)에서 실행되는 노드 집합 내부의 가장자리에 대한 함수도 있지만 상수 요소를 줄이기위한 몇 가지 트릭이 포함되어 있습니다.

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