CS170 Approximation Example Code

import networkx as nx
import loader
import matplotlib.pyplot as plt
import IPython as ipy
import numpy as np
import random
import itertools
import sys
import operator

import pprint
pp = pprint.PrettyPrinter(indent=4)

BRUTE_FORCE_SIZE = 10
MAG_GRASP_TIMES = 15

def MAG_GRASP(G, A, ranking=None, iterations=10000):
    nodes = G.nodes()
    n = len(nodes)
    if ranking is None:
        ranking = range(n)
        random.shuffle(ranking)

    best_score = score_ranking(A, n, ranking)
    for _ in range(iterations):
        i, j = random.randint(0, n-1), random.randint(0, n-1)
        ranking[i], ranking[j] = ranking[j], ranking[i]
        s = score_ranking(A, n, ranking)
        if s > best_score:
            best_score = s
        else:
            ranking[i], ranking[j] = ranking[j], ranking[i]
    c = [nodes[i]+1 for i in ranking]
    return c, best_score

def brute_force(G, A):
    nodes = G.nodes()
    n = len(nodes)
    best_ranking = range(n)
    best_score = score_ranking(A, n, best_ranking)

    mapp = dict(zip(range(n), nodes))

    assert n <= 10, "Too big for brute force"

    for ranking in itertools.permutations(best_ranking):
        score = score_ranking(A, n, ranking)
        if score > best_score:
            best_score, best_ranking = score, ranking
    return [mapp[r]+1 for r in best_ranking]

def greedy_out(G,A):
    nodes = G.nodes()
    n = len(nodes)
    norm_nodes = range(n)
    mapp = dict(zip(nodes, norm_nodes))
    dicty = {mapp[i]: G.out_degree(i) for i in G.nodes() }
    y = sorted(dicty.items(), key=operator.itemgetter(1),reverse=True)
    ranking = [x[0] for x in y]

    ranking, score = MAG_GRASP(G, A, ranking=ranking)
    return ranking, score

def greedy_in(G,A):
    nodes = G.nodes()
    n = len(nodes)
    norm_nodes = range(n)
    mapp = dict(zip(nodes, norm_nodes))
    dicty = {mapp[i]: G.in_degree(i) for i in G.nodes() }
    y = sorted(dicty.items(), key=operator.itemgetter(1),reverse=False)
    ranking = [x[0] for x in y]

    ranking, score = MAG_GRASP(G, A, ranking=ranking)
    return ranking, score

def Eric(G, A):
    orig = G.copy()
    G = G.copy()
    n = A.shape[0]
    ranking = range(1, n+1)
    nodes = G.nodes()
    norm_nodes = range(1,n+1)
    mapp = dict(zip(nodes, norm_nodes))

    l = 1; u = n
    while u >= l:
        n = len(G.nodes())
        rand = random.randint(0, n-1)
        i = G.nodes()[rand]
        indeg = G.in_degree(i)
        outdeg = G.out_degree(i)
        G.remove_node(i)
        if indeg <= outdeg:
            ranking[mapp[i]-1] = l
            l += 1
        else:
            ranking[mapp[i]-1] = u
            u -= 1
    ranking, score = MAG_GRASP(G, A, ranking=ranking)
    return [r+1 for r in ranking], score

def circle(G, A):
    base_nodes = G.nodes()[:]
    G = G.copy()
    n = len(G.nodes())
    mappp = dict(zip(G.nodes(), range(n)))
    ranking = [G.nodes()[random.randint(0, n-1)]]
    for i in xrange(1,n-1):
        neighbors = G.neighbors(ranking[i-1])
        if len(neighbors) == 0:
            return [i+1 for i in base_nodes], score_ranking(A, n, [mappp[r] for r in base_nodes])
        ranking.append(G.neighbors(ranking[i-1])[0])
        G.remove_node(ranking[i-1])
    G.remove_node(ranking[-1])
    ranking += [G.nodes()[0]]
    return [r+1 for r in ranking], score_ranking(A, n, [mappp[r] for r in ranking])

def ga(G, A, population_size = 100):
    n = A.shape[0]
    inds = np.arange(0,n)

    # Initialization
    population = []
    base = range(n)
    for _ in range(population_size):
        random.shuffle(base)
        population.append(base[:])

    # Selection
    population_scores = np.array([score_ranking(A, n, r) for r in population])
    p = population_scores * 1.0 / np.sum(population_scores)
    new_population = [population[i] for i in np.random.choice(inds, 50, replace=True, p=p)]

    # Apply Genetic Operators
    for _ in range(50):
        pass

def score_ranking(A, n, ranking): #ranking = zero-indexed
    assert min(ranking) == 0, "ranking needs to be zero-indexed"
    b = np.zeros(n)
    for i, j in enumerate(ranking):
        b[j] = i
    return np.sum(A * b - A * b[:, np.newaxis] > 0)

# def f_on_sccs_and_recombine(G, A, f, d):
#     sccs = [g for g in nx.strongly_connected_component_subgraphs(G)]
#     C = nx.condensation(G)
#     ranking = []
#     for i in nx.topological_sort(C):
#         scc = sccs[i]
#         nodes = scc.nodes()
#         if len(nodes) <= 10:
#             c = brute_force(sccs[i], A[nodes, :][:, nodes])

#         else:
#             c = f(sccs[i], A[nodes, :][:, nodes])
#         ranking += c
#     return ranking

# def ensemble(G, A, list_of_funcs):
#     n = A.shape[0]
#     best_score, best_ranking, best_f = -1, range(n), None
#     num_sccs = len([g for g in nx.strongly_connected_component_subgraphs(G)])
#     d = {}
#     for f in list_of_funcs:
#         ranking = f_on_sccs_and_recombine(G, A, f, d)
#         score = score_ranking(A, n, [r-1 for r in ranking])
#         print str(f), score
#         if score > best_score:
#             best_score, best_ranking = score, ranking
#     return best_score, best_ranking


def ensemble(G, A, list_of_funcs):
    n = A.shape[0]
    sccs = [g for g in nx.strongly_connected_component_subgraphs(G)]
    C = nx.condensation(G)
    ranking = []
    total_score = 0
    for i in nx.topological_sort(C):
        scc = sccs[i]
        nodes = scc.nodes()
        sub_A = A[nodes, :][:, nodes]
        if len(nodes) <= BRUTE_FORCE_SIZE:
            ranking += brute_force(scc, sub_A)
        else:
            n = len(nodes)
            best_score, best_ranking, best_f = -1, range(n), None
            for f in list_of_funcs:
                c, score = f(scc, sub_A)
                if score > best_score:
                    best_score, best_ranking = score, c
            ranking += best_ranking
            total_score += best_score
    return ranking, total_score

if __name__ == '__main__':
    draw = False

    # A = loader.generate_instance_shane(100, .7)
    # G = nx.DiGraph(A)
    # n, A = loader.read_graph("data/Eric_raw.in")
    # G = nx.DiGraph(A)
    # score, result = ensemble(G, A, [Eric, greedy_out, greedy_in])
    # print "score: ", score
    # print result
    # n, A = loader.read_graph("data/Eric_trick.in")
    # G = nx.DiGraph(A)
    # score, result = ensemble(G, A, [Eric, greedy_out, greedy_in])
    # print "score: ", score
    # print result

    # sys.exit()
    # f = open("instances_sccs.txt", "w")
    # ct = 0
    _, A1 = loader.read_graph("data/KINGSMEN1.in") # circle
    _, A2 = loader.read_graph("data/KINGSMEN2.in")
    _, A3 = loader.read_graph("data/KINGSMEN3.in")

    _, A1_replaced = loader.read_graph("dual_circle_raw.in")
    _, A2_replaced = loader.read_graph("data/Eric_raw.in")

    # res = ensemble(nx.DiGraph(A1_replaced), A1_replaced, [MAG_GRASP]*15 + [greedy_in, greedy_out] + [circle])
    # res1 = ensemble(nx.DiGraph(A1), A1, [MAG_GRASP]*15 + [greedy_in, greedy_out] + [circle])
    # print score_ranking(A1, 100, [r-1 for r in res])
    # print score_ranking(A1, 100, [r-1 for r in res1])

    # A = loader.generate_circular(100)
    # G = nx.DiGraph(A)
    # res = ensemble(G, A, [circle])
    # print score_ranking(A, 100, [r-1 for r in res])

    # for j in [371, 475, 489, 537, 543]:
    # for j in [53, 530, 489, 537, 543]:
    #     i = str(j) + ".in"
    #     n, A = loader.read_graph("instances/"+i)
    #     G = nx.DiGraph(A)
    #     res = ensemble(G, A, [MAG_GRASP]*15 + [greedy_in, greedy_out] + [circle])
    #     print "edges", np.sum(A)
    #     print "score", score_ranking(A, n, [r-1 for r in res])
    #     print [i for i in nx.strongly_connected_components(G)]
    #     print ""
    #     print ""

    for j in range(1,622):
        i = str(j) + ".in"
        # print "------------------------------------------------\n\n"
        n, A = loader.read_graph("instances/"+i)
        if np.array_equal(A, A1):
            A = A1_replaced
        if np.array_equal(A, A2):
            A = A2_replaced
        if np.array_equal(A, A3):
            A3_to_remove = [[17, 22], [29, 24], [71, 81], [59, 62], [91, 20], [97, 54], [77, 69], [5, 28], [48, 4]]
            for i,j in A3_to_remove:
                assert A[i,j] == 1
                A[i,j] = 0

        print "------------------------"
        print "id:", j
        print "nodes:", A.shape[0]
        G = nx.DiGraph(A)
        print "sccs:", len([i for i in nx.strongly_connected_components(G)])
        ranking, _ = ensemble(G, A, [MAG_GRASP]*MAG_GRASP_TIMES + [greedy_in, greedy_out] + [circle])
        score = int(score_ranking(A, A.shape[0], [r-1 for r in ranking]))
        print score, "/", int(np.sum(A))
        loader.write_single_output(ranking, score, fname="outputs_eric/"+str(j)+".out")
        print ""
        print ""
        # print "total edges: ", np.sum(A)
        # lengths = [len(i) for i in nx.strongly_connected_components(G)]
    #     # f.write(str(j) + ", " + str(lengths) + "\n")
    #     # ct = ct + (1 if len(lengths) > 1 else 0)
    #     if draw:
    #         nx.draw_networkx(G)
    #         plt.savefig("figures/"+i[:i.index(".in")]+".png")
    #         plt.clf()
    #     # print j
    # print "total ct", ct