bandwidth.py

import sys


def max_span(graph, permutation):
    ''' Calculate the maximum span of a permutation. '''
    # O(n^2) calculate max span
    max_span = 0
    for i in range(len(permutation)):
        for j in range(i + 1, len(permutation)):
            span = j - i
            a = permutation[i]
            b = permutation[j]
            if b in graph[a]:
                max_span = max(max_span, span)

    return max_span


def minimum_bandwidth(graph,
                      candidate_weight=0,
                      candidate=None,
                      included_vertices=None,
                      best_candidate=(sys.maxsize, None)):
    ''' Find the permutation of |V| vertices that minimizes the maximum span
    between vertices (i.e hops between vertices). '''
    if candidate is None:
        candidate = []
        included_vertices = set()
    elif len(candidate) == len(graph):
        return (candidate_weight, candidate)

    best_subtree_candidate = best_candidate

    for other in list(graph):
        if other in included_vertices:
            continue
        max_vertex_span = max_span(graph, candidate + [other])

        if max_vertex_span > best_candidate[0]:
            continue

        subtree_candidate = minimum_bandwidth(graph,
                                              max_vertex_span,
                                              candidate + [other],
                                              included_vertices | {other},
                                              best_subtree_candidate)

        best_subtree_candidate = subtree_candidate

    return best_subtree_candidate