CODEWITHSUNDEEP
pythonmatplotlibplotlynetworkx
Muhammad Asif Khan
Muhammad Asif Khan

Reputation: 319

Connecting Nodes using Assignment Matrix

In typical facility location problems, I have three facilities (Fi, i=1,2,3) and six nodes (Dj, j=1,2,3,4,5,6). I want to plot all Fi and Dj and then connect nodes Dj to facilities Fi, based on an assignment matrix Xij.

The matrix Xij is given as:

Xij = np.array([[1,0,0,1,1,1],
                [0,1,1,0,0,0],
                [0,0,0,0,0,0]])

The first row of Xij shows that nodes Dj (j=0,3,4,5) are allocated to the facility Fi (i=0). Second row shows Nodes Dj (j=1,2) are allocated to second facility Fi (i=2). Third row shows that no node is allocated to Facility Fi(i=2).

I tried to do it in matplotlib, to plot the nodes at specified locations, but don't know how to connect them.

fx = np.array([30, 30, 30])
fy = np.array([10, 20, 30])
f = np.vstack((fx, fy))
px = np.array([50, 50, 50, 50, 50])
py = np.array([10, 15, 20, 25, 30])
p = np.vstack((px, py))
plt.scatter(fx,fy, marker='D', s=100)
plt.scatter(px,py, marker='o', s=100)

Then I read about the Networkx library and tried to plot them as:

G1  = nx.Graph()   
G2  = nx.Graph()
Fi = {0: (10,10),
      1: (10,20),
      2: (10,30)}

Dj ={0: (20,5),
      1: (20,10),
      2: (20,15),
      3: (20,20),
      4: (20,25),
      5: (20,30)}
nx.draw_networkx(G1, Fi, node_color= 'gray', node_size=500)
nx.draw_networkx(G2, Dj, node_color= 'gray', node_size=300)

However, can't figure out how to connect these nodes easily in any tool? The given problem is just a simple version of a bigger network.

Upvotes: 0

Views: 176

Answers (2)

Dinari
Dinari

Reputation: 2557

You need to use pos for drawing in the right location, and for the edges, you should iterate over the matrix:

import numpy as np
import networkx as nx
from matplotlib import pyplot as plt

Xij = np.array([[1,0,0,1,1,1],
                [0,1,1,0,0,0],
                [0,0,0,0,0,0]])

Fi = {'F0': [10,10],
      'F1': [10,20],
      'F2': [10,30]}

Dj ={'D0': [20,5],
      'D1': [20,10],
      'D2': [20,15],
      'D3': [20,20],
      'D4': [20,25],
      'D5': [20,30]}

newD = dict(Dj.items()) #Build a dictionary with all the items, for position
newD.update(Fi.items())

G1  = nx.Graph()   

G1.add_nodes_from(newD)
for i in range(Xij.shape[0]): # Add an edge according to the matrix
    for j in range(Xij.shape[1]):
        if Xij[i,j] == 1:
            G1.add_edge('F'+str(i), 'D'+str(j))


nx.draw(G1, with_labels=True, pos = newD) #Draw, with locations and edges

With result:
enter image description here

Added explanation inline with the code.

Edit: For colors you need to define a color for each node:

colors = ['r' if x[0] == 'D' else 'b' for x in list(G1.nodes)]
nx.draw(G1, with_labels=True,node_color=colors, pos = newD) #Draw, with locations and edges, and colors

Upvotes: 1

Thomas Kimber
Thomas Kimber

Reputation: 11067

One way of doing this is to convert your bipartite assignment matrix into a full adjacency matrix, then using that to populate your nx graph.

Xij = np.array([[1,0,0,1,1,1],
                [0,1,1,0,0,0],
                [0,0,0,0,0,0]])

A = Xij
At = A.T
Z_top_left = np.zeros((A.shape[0], At.shape[1]))
Z_bottom_right = np.zeros((At.shape[0], A.shape[1]))
G = nx.from_numpy_matrix(np.vstack([np.hstack([Z_top_left,A]) , np.hstack([At, Z_bottom_right])]))

Then you can draw your G graph (having set out the positions using methods outlined elsewhere here) and it will contain the edges you're looking for.

bipartite graph

To get from an assignment matrix X, you need to compose an array consisting of X and the transpose of X in the top right and bottom left corners, filling in the rest with zeros, since there are no edges from Facility to Facility or Node to Node (to use your terms). It's a bipartite graph. That's what the hstack and vstack calls are doing in the above.

Alternately, you could loop through your assignment array, with i and j as row/column iterators and do:

G.add_edge(i,j)

This will create the nodes, and connect them with edges. One of the nx.draw family of commands will then lay them out graphically. I also notice there's an upcoming bipartite_layout option coming to networkx at sometime in the future.

Upvotes: 2

Related Questions