Maryam
Maryam

Reputation: 33

How to find two randoms nodes with no edges between them in graph?

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)

Upvotes: 1

Views: 809

Answers (2)

EDWhyte
EDWhyte

Reputation: 351

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

Upvotes: 0

Alex Hall
Alex Hall

Reputation: 36063

If you just want one pair of nodes, there is no reason to make a list. Just find the pair!

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

Now use u and v directly.

Upvotes: 2

Related Questions