Edge Betweenness

Problem

Compute the (unnormalized, undirected) edge betweenness of every edge with Brandes' algorithm.

For each source, count shortest paths and accumulate dependencies along BFS predecessor lists; each edge receives the dependency flowing through it, and undirected contributions are finally divided by 2. Return scores aligned with the input edge order. edges is a list of [u, v] pairs.

Hint

The bridge between two cliques gets a score proportional to the product of clique sizes.

Test cases

case 1

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

expected: [3,4,3]

case 2

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

expected: [1,1,1]

case 3

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

expected: [1,4,4,9,4,1,4]

Starter codePython

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

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