Graph Coarsening Matching Step

Problem

Perform one coarsening round with greedy matching: scan nodes in order and match each unmatched node with its smallest-index unmatched neighbor.

Matched pairs and unmatched nodes become clusters, so the cluster count is n minus the number of pairs. Return [cluster_count, pairs] with pairs sorted.

Hint

Coarsening halves the graph at best, which is why multilevel methods scale well.

Test cases

case 1

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

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

case 2

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

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

case 3

in: [3,[]]

expected: [3,[]]

case 4

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

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

Starter codePython

def coarsening_matching(n, edges):
    # Your code here
    pass

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