Brandes Source Dependencies

Problem

Compute the single-source pair dependencies used by Brandes' betweenness algorithm.

BFS from source builds shortest-path counts sigma and predecessor lists, then nodes are processed in reverse BFS order so each predecessor v gains (sigma[v] / sigma[w]) * (1 + delta[w]). edges is a list of [u, v] pairs of an undirected unweighted graph. Return the dependency array delta with delta[source] = 0.0.

Hint

Dependencies flow backwards from the farthest nodes toward the source.

Test cases

case 1

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

expected: [0,1,0]

case 2

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

expected: [0,0.5,0,0.5]

case 3

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

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

case 4

in: [1,[],0]

expected: [0]

Starter codePython

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

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