Girvan-Newman Removal Sequence

Problem

Run several Girvan-Newman steps and return the sequence of removed edges.

Each step recomputes undirected edge betweenness with Brandes' algorithm on the current graph, removes the edge with the highest score, breaking ties by the smallest [min, max] endpoint pair, and records it. edges is the original list of [u, v] pairs of a simple graph and steps is the number of removals. Return the removed edges in order.

Hint

After the bridge disappears, each community becomes a symmetric cycle where every edge ties.

Test cases

case 1

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

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

case 2

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

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

case 3

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

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

case 4

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

expected: [[0,1]]

Starter codePython

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

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