Wie finden Sie zwei Randoms Knoten ohne Kanten zwischen ihnen in Grafik?

Question

Ich bin ziemlich neu in Python, ich möchte zwei zufällige Knoten im Netzwerk finden, die keine Kanten zwischen ihnen hat, aber mein Programm manchmal leere Liste oder mehr als zwei Knoten zurückgeben. kann mir jemand helfen, auf diesem, Mein Programm ist:

import networkx as nx 
import random 
n=6 
m=10 
G=nx.gnm_random_graph(n, m, seed=None, directed=True) 
result = [] 
nodes = random.sample(G.nodes(), 2) 
for u in nodes: 
    for v in nodes: 
     if u != v and G.has_edge(u,v) is False and G.has_edge(v,u) is False: 
     result.append((u,v)) 
    else: 
     nodes = random.sample(G.nodes(), 2) 
print(result) 

Answer 1

import networkx as nx 
import random 
n=6 
m=10 
G=nx.gnm_random_graph(n, m, seed=None, directed=True) 
nodes = G.nodes() 

def select_2_random_unconnected_nodes(node_list, graph): 

    selected_node = random.choice(node_list) 

    # obtain all the nodes connected to the selected node 
    connected_nodes = [n for _, n in G.edges(selected_node)] 

    print(connected_nodes + [selected_node]) 

    # a feasible node is one not in connected_nodes and also not the first selected_node 
    feasible_nodes = [feasible_n for feasible_n in node_list if feasible_n not in connected_nodes + [selected_node]] 

    # select a second node from the feasible_nodes list 
    select_second_node = random.choice(feasible_nodes) 

    return selected_node, select_second_node 

Answer 2

Wenn Sie nur ein Paar von Knoten wollen, gibt es keinen Grund, eine Liste zu machen. Finde das Paar!

while True: 
    u, v = random.sample(G.nodes(), 2) 
    if not (G.has_edge(u, v) or G.has_edge(v, u)): 
     break 

Jetzt u und v direkt verwenden.