pythonnumpyadjacency-matrix

Adjacency matrix using numpy


I need to generate the following adjacency matrices:

No of Nodes = 3

    A   B   C   AB  AC  BC
A   0   1   1   0   0   1
B   1   0   1   0   1   0
C   1   1   0   1   0   0
AB  0   0   1   0   0   0
AC  0   1   0   0   0   0
BC  1   0   0   0   0   0

To generate an adjacency matrix for 3 nodes, I can use the code available here, which is

out = np.block([
    [1 - np.eye(3), np.eye(3)       ],
    [    np.eye(3), np.zeros((3, 3))]
]).astype(int)

But it cannot use for different number of nodes, for example if we have 5 nodes then:

No of Nodes = 5

    A   B   C   D   E   AB  AC  AD  AE  BC  BD  BE  CD  CE  DE
A   0   1   1   1   1   0   0   0   0   1   1   1   1   1   1
B   1   0   1   1   1   0   1   1   1   0   0   0   1   1   1
C   1   1   0   1   1   1   0   1   1   0   1   1   0   0   1
D   1   1   1   0   1   1   1   0   1   1   0   1   0   1   0
E   1   1   1   1   0   1   1   1   0   1   1   0   1   0   0
AB  0   0   1   1   1   0   0   0   0   0   0   0   0   0   0
AC  0   1   0   1   1   0   0   0   0   0   0   0   0   0   0
AD  0   1   1   0   1   0   0   0   0   0   0   0   0   0   0
AE  0   1   1   1   0   0   0   0   0   0   0   0   0   0   0
BC  1   0   0   1   1   0   0   0   0   0   0   0   0   0   0
BD  1   0   1   0   1   0   0   0   0   0   0   0   0   0   0
BE  1   0   1   1   0   0   0   0   0   0   0   0   0   0   0
CD  1   1   0   0   1   0   0   0   0   0   0   0   0   0   0
CE  1   1   0   1   0   0   0   0   0   0   0   0   0   0   0
DE  1   1   1   0   0   0   0   0   0   0   0   0   0   0   0

Is there any simple and easiest way to implement these adjacency matrices?


Solution

  • Inferring the logic of the output from your two examples, I think something like this might do what you want:

    import numpy as np
    
    def make_matrix(N, dtype=int):
      n_comb = N * (N - 1) // 2
      upper_left = 1 - np.eye(N, dtype=dtype)
      lower_right = np.zeros((n_comb, n_comb), dtype=dtype)
      cross = np.ones((N, N, N), dtype=dtype)
      i = np.arange(N)
      cross[i, :, i] = 0
      cross[:, i, i] = 0
      cross = cross[(np.triu_indices(N, k=1))]
      return np.block([[upper_left, cross.T],
                       [cross, lower_right]])
    
    print(make_matrix(3))
    
    [[0 1 1 0 0 1]
     [1 0 1 0 1 0]
     [1 1 0 1 0 0]
     [0 0 1 0 0 0]
     [0 1 0 0 0 0]
     [1 0 0 0 0 0]]
    
    print(make_matrix(5))
    
    [[0 1 1 1 1 0 0 0 0 1 1 1 1 1 1]
     [1 0 1 1 1 0 1 1 1 0 0 0 1 1 1]
     [1 1 0 1 1 1 0 1 1 0 1 1 0 0 1]
     [1 1 1 0 1 1 1 0 1 1 0 1 0 1 0]
     [1 1 1 1 0 1 1 1 0 1 1 0 1 0 0]
     [0 0 1 1 1 0 0 0 0 0 0 0 0 0 0]
     [0 1 0 1 1 0 0 0 0 0 0 0 0 0 0]
     [0 1 1 0 1 0 0 0 0 0 0 0 0 0 0]
     [0 1 1 1 0 0 0 0 0 0 0 0 0 0 0]
     [1 0 0 1 1 0 0 0 0 0 0 0 0 0 0]
     [1 0 1 0 1 0 0 0 0 0 0 0 0 0 0]
     [1 0 1 1 0 0 0 0 0 0 0 0 0 0 0]
     [1 1 0 0 1 0 0 0 0 0 0 0 0 0 0]
     [1 1 0 1 0 0 0 0 0 0 0 0 0 0 0]
     [1 1 1 0 0 0 0 0 0 0 0 0 0 0 0]]
    

    The logic here is that each row of the upper-right matrix is like the flattened upper-triangle of a straightforward NxN matrix. For example:

    # construct second row of upper-right matrix for 5x5 case:
    x = np.ones((5, 5), dtype=int)
    x[1] = 0
    x[:, 1] = 0
    print(x)
    # [[1 0 1 1 1]
    #  [0 0 0 0 0]
    #  [1 0 1 1 1]
    #  [1 0 1 1 1]
    #  [1 0 1 1 1]]
    
    print(x[np.triu_indices(5, k=1)])
    # [0 1 1 1 0 0 0 1 1 1]