Ytukyg

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.

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:

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

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.

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.