import random as rd
import numpy as np


def suma_kolejnych(x):
    w = 0
    for i in range(1, x+1):
        w += x
    return w

def losuj_gen(color_no):
    return rd.randint(0, color_no-1)

def losuj_populacje_startowa(l_osobnikow, n, color_no):
    populacja = np.zeros((l_osobnikow, n))
    for i in range(l_osobnikow):
        for j in range(n):
            populacja[i][j] = losuj_gen(color_no)
    return populacja

def f_oceny(osobnik, M, n):
    fail_no = 0
    for i in range(len(osobnik)):
        for j in range(n):
            if M[i][j] != 0:
                if osobnik[i] == osobnik[j]:
                    fail_no += 1
    return fail_no

def selekcja_metoda_ranking(populacja, f_oceny, M, n, l_osobnikow):
    osobnik_pom = []
    for i in range(populacja.shape[0]):
        osobnik_pom.append([populacja[i], f_oceny(populacja[i], M, n)])
    sorted(osobnik_pom, key= lambda osobnik_pom: osobnik_pom[1], reverse=True)

    new_populacja = losuj_populacje_startowa(l_osobnikow, n, 1)
    maks_los = suma_kolejnych(populacja.shape[0])
    for i in range(populacja.shape[0]):
        los = rd.randint(0, maks_los-1)
        x = 0
        while los < suma_kolejnych(x):
            x += 1
        for j in range(populacja.shape[1]):
            new_populacja[i][j] = osobnik_pom[0][x][j]
    return new_populacja

def krzyzowanie(populacja, war_krzyzowania, n):
    for i in range(0, populacja.shape[0], 2):
        krzyzuj = rd.random()
        if krzyzuj < war_krzyzowania:
            cross_point = rd.randint(1, n-1)
            rodzic1 = populacja[i]
            rodzic2 = populacja[i+1]
            for j in range(n):
                if j <= cross_point:
                    populacja[i][j] = rodzic2[j]
                    populacja[i+1][j] = rodzic1[j]
    return populacja

def mutacja(populacja, war_mutacji, color_no):
    for i in range(0, populacja.shape[0]):
        mutuj = rd.random()
        if mutuj < war_mutacji:
            for j in range(populacja.shape[1]):
                mutuj_gen = rd.random()
                if mutuj_gen < war_mutacji:
                    populacja[i][j] = losuj_gen(color_no)
    return populacja

def najlepszy(populacja, f_oceny, M, n, best, best_f):
    best_grade = 99999999999
    for osobnik in populacja:
        grade = f_oceny(osobnik, M, n)
        if grade < best_grade:
            best_grade = grade
            if grade < best_f:
                best_f = grade
                best = osobnik
    return best, best_f

def kolorowanie_genetyczne(color_no, M, n, max_iter, l_osobnikow, war_stop, war_krzyzowania, war_mutacji):
    iter_no = 0
    best_f = 99999999
    populacja = losuj_populacje_startowa(l_osobnikow, n, color_no)
    best = populacja[0]
    rd.seed()

    while iter_no < max_iter and best_f > war_stop:
        #selekcja
        populacja = selekcja_metoda_ranking(populacja, f_oceny, M, n, l_osobnikow)
        #krzyzowanie
        populacja = krzyzowanie(populacja, war_krzyzowania, n)
        #mutacja
        populacja = mutacja(populacja, war_mutacji, color_no)
        #spr wyniku
        best, best_f = najlepszy(populacja, f_oceny, M, n, best, best_f)
        iter_no += 1

    best_f /= 2
    if best_f <= war_stop:
        return True, best_f
    else:
        return False, best_f


file = open("C:/my_pc/Code/moje/Algosy/kolorowanie grafow/q6x6.txt", 'r')
n = int(file.readline())
M = np.zeros((n,n))
for line in file:
    pom = line.split()
    M[int(pom[0])-1][int(pom[1])-1] = 1
file.close()

czy, best_f = kolorowanie_genetyczne(10, M, n, 5000, 10, 5, 0.3, 0.8)
print(czy, best_f)