SNHeuristics.py 文件源码

def high_degree_nodes(k, G):

    if nx.is_directed(G):
        my_degree_function = G.out_degree
    else:
        my_degree_function = G.degree

    # the top k nodes to be returned; initialization with first k elements
    H = [(my_degree_function(i), i) for i in G.nodes()[0:k]] 
    hq.heapify(H)

    # iterate through the remaining nodes; add to heap if larger than heap root
    for i in G.nodes()[k:]: 
        if my_degree_function(i) > H[0][0]:
            hq.heappushpop(H, (my_degree_function(i), i))

    return H

# Generator variant of high_degree_nodes(k, G)
# More time-efficient for range calls if k log k > log V
# Generates _all_ sets of i nodes of highest degree, with 1 <= i <= k
# -> Time complexity: O(V log (V))
# -> Memory complexity: Theta(V)