Lexicographic Product Degree

Problem

Compute the degree matrix of the lexicographic product of two undirected graphs.

In this product the degree of pair (u, v) is n2 * deg1(u) + deg2(v), where n2 is the node count of the second factor. Given the degree sequences of both factors, return the degrees in row-major order with u as the outer index.

Hint

In a lexicographic product each copy of the second graph is joined completely between adjacent first-factor nodes.

Test cases

case 1

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

expected: [[3,4,5],[6,7,8]]

case 2

in: [1,[3],2,[1,1]]

expected: [[7,7]]

case 3

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

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

Starter codePython

def lexicographic_degree(n1, deg1, n2, deg2):
    # Your code here
    pass

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