Walk Count Two Entry

Problem

Compute a single entry of the squared adjacency matrix after one multiplication step.

For adjacency matrix A, the entry (A*A)[i][j] counts walks of length exactly 2 from i to j and equals the dot product of row i with column j. matrix is a square 0/1 matrix for a directed or undirected graph. Return that integer count.

Hint

Sum A[i][k] * A[k][j] over all middle nodes k.

Test cases

case 1

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

expected: 1

case 2

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

expected: 1

case 3

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

expected: 2

case 4

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

expected: 1

case 5

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

expected: 1

Starter codePython

def walk_count_two(matrix, i, j):
    # Your code here
    pass

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