Graph Compression Reference Count

Problem

Count the duplicate edge references that a compression pass would remove.

Normalize every edge so u < v and count how many edges are repetitions of an edge already seen. Return the number of duplicates. edges is a list of [u, v] pairs.

Hint

Canonicalizing undirected edges is the first step of any edge-list compression.

Test cases

case 1

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

expected: 3

case 2

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

expected: 0

case 3

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

expected: 2

Starter codePython

def compression_reference_count(edges):
    # Your code here
    pass

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