networkx는 : 에지로부터 유도 된 서브 그래프 작성

Question

networkx 만 노드들로부터 유도 된 서브 그래프를 작성하는 기능을

Graph.subgraph()

있다. 하지만 가장자리 목록에서 하위 그래프를 만드는 방법은 무엇입니까?

감사합니다.

Answer 1

가장자리 목록이있는 경우 이미 하위 그래프가 있습니다. 목록에서 nx.Graph으로 전화하고 필요에 따라 원래 그래프에서 (연결되지 않은) 노드를 추가하십시오. docs

Graph.__init__(data=None, **attr) 

에서 가장자리, 이름, 그래프 속성을 가진 그래프를 초기화합니다.
데이터를 그래프로 초기화합니다. data = None (기본값)이면 빈 그래프가 생성됩니다. 데이터는 에지 목록 또는 임의의 NetworkX 그래프 개체가 될 수 있습니다.

Answer 2

@larsmans의 대답은 정확합니다. 당신이 Graph.subgraph() 노드에서 생성 된 서브 그래프에 대한이 대신이 기능은 가장자리의 반복자에 작동하는 속성을 가진 기능을 가지고 싶다면

In [1]: import networkx as nx 

In [2]: G = nx.path_graph(6) 

In [3]: G.edges() 
Out[3]: [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5)] 

In [4]: subgraph_edges = [(1,2), (3,4)] 

In [5]: S = nx.Graph(subgraph_edges) 

In [6]: S.edges() 
Out[6]: [(1, 2), (3, 4)] 

Answer 3

, 당신은 원본에 대한 참조를 유지해야합니다 다음은 간단한 예입니다 그래프, 에지 및 노드는 그래프, 에지 또는 노드 데이터 속성의 변경 사항을 전파 할 수 있습니다. 주목할만한 문서 문자열은 Graph.subgraph()입니다.

그래프, 가장자리 또는 노드 속성은 원래 그래프를 가리 킵니다. 노드 또는 에지 구조의 변경 사항은 속성 변경시 원래 그래프 에 반영되지 않습니다.

가장자리/노드의 복사본과 서브 그래프를 만들려면이 사용 속성 : nx.Graph (G.subgraph (nbunch를)) 에지 속성은 컨테이너 인 경우

, 깊은 사본을 사용하여 얻을 수 있습니다 : 그들은 처음부터 새 그래프를 만들 것으로 현재 제안 된 방법은, 원래의 그래프에서 해당 속성의 변화를 반영하지 않습니다

G.subgraph (nbunch) .copy().

에지를 사용하여이를 수행하는 내장 된 함수/방법이 없습니다. 그러나이 함수는 노드 .subgraph의 인프라를 사용하므로 Graph 및 DiGraph에서 작동해야합니다. MultiGraph 및 MultiDiGraph에서는 작동하지 않습니다. 이것은 MultiGraph와 MultiDiGraph가 여러분이 엣지의 키를 참조 할 필요가 있고, 현재의 접근법은 두번째 이후의 인수를 무시하므로 엣지 목록에서 전달 된 속성이 딕셔너리로 ​​첨부 된 속성을 가지고 있는지 여부에 둔감합니다. 또한 참조없이 (ref_back=False을 전달하여) 작성된 경우에도 nx.Graph 또는 nx.DiGraph 클래스 초기화 프로그램을 사용하여 새 그래프를 작성하지 않고 원래 그래프의 deepcopy를 작성합니다. 그것은 다른 케이스를 커버하기 위해 그것을 확장하는 것이 가능합니다 ...하지만 지금은 필요가 없습니다, 그리고 누군가가 명시 적으로 그것을 요구할 때까지 나는 다른 사람이하지 않는다고 가정 할 것입니다. (버전을보고 싶다면 github을보십시오 내가 실제로 사용했던).

def subgraph_from_edges(G,edge_list,ref_back=True): 
    """ 
    Creates a networkx graph that is a subgraph of G 
    defined by the list of edges in edge_list.   

    Requires G to be a networkx Graph or DiGraph 
    edge_list is a list of edges in either (u,v) or (u,v,d) form 
    where u and v are nodes comprising an edge, 
    and d would be a dictionary of edge attributes 

    ref_back determines whether the created subgraph refers to back 
    to the original graph and therefore changes to the subgraph's 
    attributes also affect the original graph, or if it is to create a 
    new copy of the original graph. 
    """ 

    sub_nodes = list({y for x in edge_list for y in x[0:2]}) 
    edge_list_no_data = [edge[0:2] for edge in edge_list] 
    assert all([e in G.edges() for e in edge_list_no_data]) 

    if ref_back: 
     G_sub = G.subgraph(sub_nodes) 
     for edge in G_sub.edges(): 
      if edge not in edge_list_no_data: 
       G_sub.remove_edge(*edge) 
    else: 
     G_sub = G.subgraph(sub_nodes).copy() 
     for edge in G_sub.edges(): 
      if edge not in edge_list_no_data: 
       G_sub.remove_edge(*edge) 

    return G_sub 

비결은 가장자리에 존재하지 않는 모든 노드가 안전하게 그래프에서 절제 (우리에게 노드 집합을 제공), 다음이 남아 있지만 에지 목록에없는 모든 모서리를 제거 할 수 있다는 것입니다 .

참고 : 이제는 상당히 고대의 질문이지만, 질문자가 원래 그래프, 가장자리 및 노드를 직접 참조하는 그래프를 원했던 경우로 해석하면 제공된 대답은 실제로 질문에 대답하지 않습니다. 특히 데이터 속성 포함). 나는 그 해결책이 필요했기 때문에 나는 그것을 아무렇게나 게시 할 것이라고 생각했다. fedges이 서브 그래프를 구축하는 필터링 가장자리의 목록입니다, 여기에

FG = nx.Graph(fedges) 
G = G.subgraph(FG.nodes()) 

: 이전 답변에까지 구축

는

Answer 4

, 정말 간단한 해결 방법이 될 수있는 모든 속성과 원래의 그래프를 유지하려면 . 먼저 필터링 된 모서리를 가진 새로운 임시 그래프 (FG)를 만듭니다. 그런 다음 노드 목록 (FG.nodes())을 사용하여 원본 그래프에서 하위 그래프를 가져옵니다. 실제로 원래 그래프 객체에 하위 그래프 함수를 사용하고 있기 때문에, 그 속성을 잃지 않을 것입니다.