problem3.py

from pulp import *

def read_input_file(filename):
    f = open(filename,"r")
    i = 0
    G = {}
    vertices = set([])
    for line in f:
        if i >= 3:
            to_add = line.split(" ")
            to_add[2] = to_add[2].split("\r")[0]
            if to_add[0] in G.keys():
                G[to_add[0]][to_add[1]] = int(to_add[2])
            else:
                G[to_add[0]] = {}
                G[to_add[0]][to_add[1]] = int(to_add[2])
            vertices.add(to_add[0])
            vertices.add(to_add[1])
        i += 1
    G['m'] = {}
    f.close()
    return G, vertices

def create_lp(G, vertices, source, dest):
    problem = LpProblem("shortestpath", LpMaximize)

    for vert in vertices:
        to_add = LpVariable(vert, 0)
        if vert in G.keys():
            G[vert]['variable'] = to_add
    #print G

    # objective
    problem += lpSum(G[dest]['variable'])

    # constraints
    for key in vertices:
        if key in G.keys():
            for edge in G[key]:
                if edge != "variable":
                    problem += G[edge]['variable'] - G[key]['variable'] <= G[key][edge]
    problem += G[source]['variable'] == 0
    
    # solution
    #GLPK().solve(problem)
    problem.solve()
    
    #print "source = {}, dest = {}, objective = {}".format(source, dest, value(problem.objective))
    return value(problem.objective)

def part_1(G, vertices):
    for vert in vertices:
        if vert != 'a':
            print "source = {}, dest = {}, objective = {}".format('a', vert, create_lp(G, vertices, 'a', vert))

def part_2(G, vertices):
    G['z'] = {}
    vertices.add('z')
    for vert in vertices:
        if vert != 'a':
           print "source = {}, dest = {}, objective = {}".format('a', vert, create_lp(G, vertices, 'a', vert))

def part_3(G, vertices):
    for vert in vertices:
        if vert != 'm':
            print "source = {}, dest = {}, objective = {}".format(vert, 'm', create_lp(G, vertices, vert, 'm'))

def part_4(G1, G2, vertices):
    dist_to_i = {}
    dist_from_i = {}
    for vert in vertices:
        if vert != 'i':
            dist_to_i[vert] = create_lp(G1, vertices, vert, 'i')
    for vert in vertices:
        if vert != 'i':
            dist_from_i[vert] = create_lp(G2, vertices, 'i', vert)
    for key1 in dist_to_i:
        for key2 in dist_from_i:
            if key1 != key2:
                print "source = {}, dest = {}, combined path through i = {}".format(key1, key2, dist_from_i[key2]+dist_to_i[key1])

if __name__ == "__main__":
    G, vertices = read_input_file("Project3Problem3-1.txt")
    #print G
    #print vertices
    #create_lp(G, vertices, 'a', 'b')
    print "Part 1"
    part_2_vertices = vertices.copy()
    part_2_G = G.copy()
    part_3_G = G.copy()
    part_4_1_G = G.copy()
    part_4_2_G = G.copy()
    part_1(G, vertices)
    print "\nPart2"
    part_2(part_2_G, part_2_vertices)
    print "\nPart3"
    part_3(part_3_G, vertices)
    print "\nPart4"
    part_4(part_4_1_G, part_4_2_G, vertices)