Как найти ребра с общими узлами в Graph Networkx? - PullRequest
Новая
       6

Как найти ребра с общими узлами в Graph Networkx?

1 голос
/ 27 февраля 2020

У меня есть этот график: 

G = nx.MultiGraph()

source_nodes = ['A', 'A', 'B', 'D']
target_nodes = ['B', 'C', 'D', 'E']

for u,v in zip(source_nodes, target_nodes):
    G.add_edge(u, v)

, и ребра, которые я получаю: 

(A, B)
(A, C)
(B, D)
(D, E)

, если целевой узел ребра является исходным узлом другого ребра, я бы нравится создавать грань между ними. Например, для приведенного выше примера новые ребра будут:

(A, D) и (A, E).

Я новичок в Networkx и не знаю, как это сделать. ..

1 Ответ

0 голосов
/ 27 февраля 2020

  1. Во-первых, вы используете MultiGraph . Он не направлен и не хранит информацию об источниках и целях (они становятся равноправными связанными узлами). Вы должны использовать DiGraphs или MultiDiGraphs для хранения информации в ориентированном графе.

  2. NetworkX DiGraphs и MultiDiGraphs имеет функции predecessors и successors, которые могут быть применены к определенному узлу. Вы можете использовать их, чтобы проверить, существует ли ребро от предшественника к преемнику, и если нет, создайте его. 

import networkx as nx

G = nx.DiGraph()  # Not a MultiGraph! (can be MultiDiGraph)

source_nodes = ['A', 'A', 'B', 'D']
target_nodes = ['B', 'C', 'D', 'E']

for u,v in zip(source_nodes, target_nodes):
    G.add_edge(u, v)

# For each node
for n in G.nodes:
    # We check all predecessors and successors
    for p in G.predecessors(n):
        for s in G.successors(n):
            # If graph has no edge from predecessor to successor
            if (p, s) not in G.edges:
                print(p, s)  # Print, can be removed
                # We add this node
                G.add_edge(p, s)

Если вы хотите создать ребра не для всех узлов, а для набор узлов, вы можете заменить G.nodes: в строке for n in G.nodes: на данный набор узлов, например:

for n in [1, 2, 3]:

Если вы хотите создать ребра только для одного узел, вам не нужен главный l oop: 

NODE_ID = 2

# We check all predecessors and successors of a node
for p in G.predecessors(NODE_ID):
    for s in G.successors(NODE_ID):
        # If graph has no edge from predecessor to successor
        if (p, s) not in G.edges:
            print(p, s)  # Print, can be removed
            # We add this node
            G.add_edge(p, s)
...