helpers.py

# from cvxopt import solvers
# from cvxopt import matrix
import numpy as np
import pickle


# from scipy.stats import rv_discrete


def write(file, content):
    if file:
        f = open(file, 'wb')
        f.write(str(content))
        f.close()


def load(source_file):
    if source_file:
        with open(source_file, "rb") as f:
            return pickle.load(f)


def save(file, content):
    if file:
        with open(file, "wb") as f:
            pickle.dump(content, f)


def projectToSimplex(d, cap):
    keys, vals = zip(*[(key, d[key]) for key in d])

    # print "Projecting:",d

    n = len(vals)
    q = -matrix(vals)
    P = matrix(np.eye(n))

    G = matrix(np.concatenate((np.eye(n), -np.eye(n), np.ones((1, n)))))

    h = matrix(n * [1.0] + n * [0.0] + [cap])

    solvers.options['show_progress'] = False
    res = solvers.qp(P, q, G, h)

    sol = res['x']
    return dict(zip(keys, sol)), res


def constructDistribution(d, cap):
    epsilon = 1.e-3

    # Remove very small values, rescale the rest
    dd = dict((key, d[key]) for key in d if d[key] > epsilon)
    keys, vals = zip(*[(key, d[key]) for key in dd])  # keys: item vals: probability
    ss = sum(vals)
    vals = [val / ss * cap for val in vals]
    dd = dict(zip(keys, vals))

    intvals = [int(np.round(x / epsilon)) for x in vals]  # probabilitepsilon
    intdist = int(1 / epsilon)
    intdd = dict(zip(keys, intvals))

    s = {}
    t = {}
    taus = []
    sumsofar = 0
    for item in keys:
        s[item] = sumsofar
        t[item] = sumsofar + intdd[item]
        taus.append(t[item] % intdist)
        sumsofar = t[item]

    # print s,t,taus
    taus = sorted(set(taus))
    # print taus

    if intdist not in taus:
        taus.append(intdist)

    placements = {}
    prob = {}

    for i in range(len(taus) - 1):
        x = []
        t_low = taus[i]
        t_up = taus[i + 1]

        diff = t_up - t_low

        for ell in range(int(cap)):
            lower = ell * intdist + t_low
            upper = ell * intdist + t_up
            for item in keys:
                # print lower,upper,' inside ', s[item],t[item], '?',
                if lower >= s[item] and upper <= t[item]:
                    x.append(item)
                #    print ' yes'
                # else: print ' no'
        prob[i] = 1. * diff / intdist
        placements[i] = x

    totsum = np.sum(prob.values())
    if not np.allclose(totsum, 1):
        for i in prob:
            prob[i] = 1. * prob[i] / totsum
        # round to 1

    #    print "Placements ",placements,"with prob",prob,"summing to",np.sum(prob.values())

    return placements, prob, rv_discrete(values=(prob.keys(), prob.values()))


def simplify(a, b):
    if a + b <= 1 + 1e-7:
        c = np.random.choice([0, 1], p=[a / (a + b), b / (a + b)])
        return [a + b, 0] if c == 0 else [0, a + b]
    elif 1 - 1e-7 < a + b < 2 + 1e-7:
        ps = [(1 - b) / (2 - a - b), (1 - a) / (2 - a - b)]
        ps = np.array(ps) / sum(ps)
        c = np.random.choice([0, 1], p=ps)
        return [1, a + b - 1] if c == 0 else [a + b - 1, 1]


def depround(x):
    while (True):
        not_rounded = np.where(np.logical_and(x < 1, x > 0))[0]
        if len(not_rounded) == 1:
            if x[not_rounded[0]] > 0.99:
                x[not_rounded[0]] = 1
            elif x[not_rounded[0]] < 0.01:
                x[not_rounded[0]] = 0
            break
        elif len(not_rounded) == 0:
            break
        i, j = not_rounded[:2]
        x[i], x[j] = simplify(x[i], x[j])
    return x


def partition_matroid_round(x, sets_S):
    for S in sets_S:
        x[S] = depround(x[S])
    return x


def sample_spherical(ndim=3):
    vec = np.random.randn(ndim)
    vec /= np.linalg.norm(vec, axis=0)
    return vec


def taverage(r):
    return np.cumsum(r) / np.arange(1, len(r) + 1)