ranking.py 文件源码

def create_ranking3(edge_weight, k, adj, num):
    sink = len(adj)
    EMPTY = -2
    ROOT = -1
    MIN_LENGTH = float('-inf')
    # heaps = [[(0, EMPTY, 0) for j in range(k)] for i in xrange(sink + 1)]
    heaps = [[(MIN_LENGTH, EMPTY, 0) for j in range(k + 1)] for i in xrange(sink + 1)]
    heaps[0][0] = (0, ROOT, 0)
    # forward
    for current in xrange(sink):
        new_rank = 0
        for length, parent, rank in heaps[current]:
            if parent != EMPTY:
                for child in adj[current]:
                    ew = edge_weight[0, num[(current, child)]]
                    new_length = length + ew
                    # heapq.heapreplace(heaps[child], (new_length, current, new_rank))
                    heapq.heappush(heaps[child], (new_length, current, new_rank))
                    heaps[child] = heapq.nlargest(k, heaps[child])
            new_rank += 1
    # backward
    ranking = []
    for rank in xrange(k):
        path = []
        current = sink
        current_rank = rank
        while current != ROOT:
            path.append(current)
            _, current, current_rank = heaps[current][current_rank]
        length, _, _ = heaps[sink][rank]
        path = list(reversed(path))
        path = tuple(zip(path[:-1], path[1:]))
        ranking.append((length, path))
    return ranking