如何在图中找到两个无边的随机节点? [英] How to find two randoms nodes with no edges between them in graph?

问题描述

我是python的新手，我想在网络中找到两个随机节点，它们之间没有边，但是我的程序有时返回空列表或两个以上的节点. 谁能帮我这个忙，我的程序是:

I am quite new in python, I want to find two random nodes in network which has no edges between them, But my program sometimes return empty list or more than two nodes. can anyone help me on this, My program is:

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)

推荐答案

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

这篇关于如何在图中找到两个无边的随机节点?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！