Metapath Count

Problem

Count the walks from a start node that follow a given sequence of edge types.

Each metapath step consumes one edge type, and edges can be reused freely. typed_edges is a list of [u, v, type] triples, path_types is the sequence of types, and start is the starting node. Return the number of matching walks.

Hint

Metapaths encode semantically meaningful typed relations in heterogeneous graphs.

Test cases

case 1

in: [[[0,1,"a"],[1,2,"b"],[2,3,"a"]],["a","b"],0]

expected: 1

case 2

in: [[[0,1,"a"],[1,2,"b"],[2,3,"a"]],["a","b","a"],0]

expected: 1

case 3

in: [[[0,1,"a"],[0,2,"a"],[1,3,"b"],[2,3,"b"]],["a","b"],0]

expected: 2

case 4

in: [[[0,1,"a"]],["b"],0]

expected: 0

Starter codePython

def metapath_count(typed_edges, path_types, start):
    # Your code here
    pass

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