Length-Two Walk Matrix

Problem

Multiply the adjacency matrix by itself once and return the full result.

matrix is a square 0/1 matrix; entry [i][j] of the product counts length-two walks from i to j. Implement the triple loop directly instead of using any library. The output has the same shape as the input.

Hint

The diagonal of the product gives each node's degree in a simple graph.

Test cases

case 1

in: [[[0,1],[1,0]]]

expected: [[1,0],[0,1]]

case 2

in: [[[0,1,0],[1,0,1],[0,1,0]]]

expected: [[1,0,1],[0,2,0],[1,0,1]]

case 3

in: [[[0,0],[0,0]]]

expected: [[0,0],[0,0]]

case 4

in: [[[0,1,0],[0,0,1],[1,0,0]]]

expected: [[0,0,1],[1,0,0],[0,1,0]]

case 5

in: [[[0]]]

expected: [[0]]

Starter codePython

def walk_matrix_two(matrix):
    # Your code here
    pass

5 test cases · run your code against them in the editor