import dijkstra

graph = {
        'directed': True,
        'vertices': ['A', 'B', 'C', 'D', 'E'],
        'edges': [
            ('A', 'B', 10),
            ('A', 'C', 3),
            ('B', 'C', 1),
            ('B', 'D', 2),
            ('C', 'D', 8),
            ('C', 'E', 2),
            ('D', 'E', 7),
            ('E', 'B', 4),
            ('E', 'D', 9)
            ]
        }

all_shortest_paths_dj = {}

for i, u in enumerate(graph['vertices']):
    all_shortest_paths_dj[u] = {}
    for j, v in enumerate(graph['vertices']):
        all_shortest_paths_dj[u][v] = dijkstra.dijkstra_path(graph, u, v)

print(all_shortest_paths_dj)

import datatools
import graphtools
from string import ascii_lowercase as myletters
from copy import deepcopy

def huffman(C, f):
    n = len(C)
    Q = datatools.Heap(C, f)
    for i in range(0, n - 1):
        x = Q.extract_min()
        y = Q.extract_min()
        z = (x, y)
        f[z] = f[x] + f[y]
        Q.insert(z, f[z])
    return Q.extract_min()

def get_tree_codes(tree, codes = {}, prefix = ""):
    if len(tree) == 1:
        codes[tree] = prefix
    else:
        get_tree_codes(tree[0], codes, prefix + "0")
        get_tree_codes(tree[1], codes, prefix + "1")
    return codes

def create_dict(f, message):
    f = dict([(myletters[i], message.count(myletters[i])) for i in range(25)])
    f = {x:y for x,y in f.items() if y != 0}
    f[' '] = message.count(' ')
    return f

def get_tree_with_frequencies(tree, f, freqs = {}):
    if len(tree) == 1:
        freqs[tree] = f[tree]
    else:
        freqs[0], freqs[1] = {}, {}
        get_tree_with_frequencies(tree[0], f, freqs[0])
        get_tree_with_frequencies(tree[1], f, freqs[1])
    return freqs

mydict = 0
message = "this is an example message to be encoded"

mydict = create_dict(mydict,message)
mydict2 = deepcopy(mydict)

res = huffman(list(mydict2.keys()), mydict2)

dict_codes = get_tree_codes(res)

coded_message = ""
for i in range(len(message)):
    coded_message += dict_codes[message[i]]

print("--- Answer 1 ---")
print(mydict)
print()
print("--- Answer 2 ---")
print(res)
print()
print("--- Answer 3 ---")
print(dict_codes)
print()
print("--- Answer 4 ---")
print(coded_message)
print()
print("--- Answer 5 ---")
graphtools.plot_huffman_tree(get_tree_with_frequencies(res, mydict))

P = [0,1,5,8,9,10,17,17,18,20,21,23,25,27,27,28,29,30,32,34,35,37,38,38,38,40,41,42,43,45,45,46,47,50,51,52,55,56,58,65,65,67]

def cut_cable(P,n):
    c = [0] * (n+1)
    cuts = [(0,0)]*(n+1)
    next_cut = n
    for i in range(0, n+1):
        max_c_i = 0
        max_i = -1
        max_j = -1
        for j in range(0,i):
            if P[i-j] + c[j] > max_c_i:
                max_c_i = P[i-j] + c[j]
                max_i = i
                max_j = j
        c[i] = max_c_i
        cuts[i] = max_i-max_j, max_j
    #print("P[%d] gia %d kai %d" % (max_i, max_i-max_j, max_j))
    #print(cuts)
    
    print("\nTa kopsimata tha ginoun stis theseis")
    while True:
        print("%d," % (cuts[next_cut][0]), end='')
        next_cut = cuts[next_cut][1]
        if next_cut == 0:
            break
    print(" kai to megisto kerdos einai %d" % (c[n]))
    return c[n]

cut_cable(P,41)