How to make a networkX grid given a list of points and add edge weights?

Question

I have a list of points (x, y) whose values are from 0 to 1

def generate_points(n):
    """Generates n points whose values are in the range (0, 1).

    Args:
        n (int): number of points to generate
    """
    x = [random.uniform(0, 1) for r in range(n)]
    y = [random.uniform(0, 1) for r in range(n)]
    return list(itertools.product(x, y))

I'm trying to generate a 2D grid of these points using NetworkX, and also add edge weights to the graph where the weight from one node to its neighbor is simply the Euclidean distance.

I am not sure about how to go about this though: I'm not very sure how to split my list of points into the m and n required for nx.generators.lattice.grid_2d_graph, nor how to update the edge weights for each one. When I try something like

G = nx.generators.lattice.grid_2d_graph([(0,1), (0, 2)], [(1, 1), (1, 2)])

a different graph is generated each time, even the nodes are the same.

score 2 · Accepted Answer · answered Oct 02 '21 at 21:03

IIUC you want something like this?

#make grid graph
G=nx.generators.lattice.grid_2d_graph(10,10)

# from node names, compute positions with random offset
positions = {(x,y):(1*x+np.random.uniform(0,0.2),1*y+np.random.uniform(0,0.2)) for (x,y) in G.nodes()}

# compute weights using euclidean distance
weights = [np.linalg.norm(np.array(positions[x])-np.array(positions[y])) for (x,y) in G.edges()]    
    
nx.draw_networkx_nodes(G, pos=positions)
nx.draw_networkx_edges(G, pos=positions, width=weights)

score 0 · Answer 2 · answered Jun 23 '22 at 16:24

For people like me who stumble onto this question and want a graph with 8 neighbors instead of just 4, the following worked for me (with help from https://stackoverflow.com/a/652123/7173506):

def neighbours(shape = (8,8), plot_graph = True):
    rows, cols = shape
    G = nx.Graph()
    _ = [G.add_node(i) for i in range(rows*cols)]
    
    for i in range(rows):
        for j in range(cols):
            for x in range(max(0, i-1), min(i+2, rows)):
                for y in range(max(0, j-1), min(j+2, cols)):
                    if(x != i or y != j):
                        G.add_edge(i*rows + j, a[x,y])
    
    # To visualize the graph structure
    if plot_graph:
        plt.figure(figsize=(6,6))
        nx.draw_spectral(G, with_labels=True, font_weight='bold')
        plt.show()
        
    A = nx.adjacency_matrix(G)
    A = A.tocoo()
    return 
                
neighbours((8,8), True)

How to make a networkX grid given a list of points and add edge weights?

2 Answers2