import time
from timeit import default_timer as timer
from random import randint
from copy import deepcopy
from copy import copy
import sys

sys.setrecursionlimit(1000000000)

def makeEuGraphMatrix(rozmiar, pokrycie):
    matrix = [[0]*rozmiar for x in range(rozmiar)]
    MAX = rozmiar*(rozmiar-1) * pokrycie
    dodane = 0
    stopien = 1
    while stopien < rozmiar / 2.0 and dodane < MAX:
        for start in range(stopien):
            aktualny = start
            while True:
                nastepny = (aktualny + stopien) % rozmiar
                if matrix[aktualny][nastepny] > 0:
                    break
                matrix[aktualny][nastepny] = matrix[nastepny][aktualny] = 1
                dodane += 2
                aktualny = nastepny
            if dodane >= MAX:
                break
        stopien += 1
    return matrix



def makeListaIncydencjiFromMatrix(matrix):
    lista = []
    for i in range(len(matrix)):
        sasiedzi = []
        for j in range(len(matrix)):
            if matrix[i][j] > 0:
                sasiedzi.append(j)
        lista.append(sasiedzi)
    return lista

def printMatrix(matrix):
    linia = "\t"
    for i in range(len(matrix)):
        linia += "%d\t" % i
    print(linia)
    for i in range(len(matrix)):
        linia = "%d\t" % i
        for j in matrix[i]:
            linia += "%d\t" % j
        print(linia)

def printListaIncydencji(lista):
    for i in range(len(lista)):
        linia = "%d | " % i
        for j in lista[i]:
            linia += "%d " % j[0]
        print(linia)



def SearchEulerPath(graph):
    stack =[0]
    path = []
    while len(stack) > 0:
        v = stack[-1]
        if len(graph[v]) > 0:
            u = graph[v][0]
            del graph[v][0]
            del graph[u][graph[u].index(v)]
            stack.append(u)
        else:
            path.append(stack.pop())
    return path

def SearchHamiltonPath(graph):
    def SHP(v, visited = [False] * len(graph), path = []):
        visited[v] = True
        path += [v]
        for w in graph[v]:
            if not visited[w]:
                finalPath = SHP(w, visited, path)
                if not finalPath == None:
                    return finalPath
        if len(path) == len(graph):
            if path[0] in graph[path[-1]]:
                return path
        visited[v] = False
        return None
    return SHP(0)


def SearchAllHamiltonPaths(graph):
    tab = []
    def SHP(v, visited = [False] * len(graph), path = []):
        visited[v] = True
        path = path + [v]
        for w in graph[v]:
            if not visited[w]:
                SHP(w, visited, path)
        if len(path) == len(graph):
            if path[0] in graph[path[-1]]:
                tab.append(path[:])
        visited[v] = False
    SHP(0)
    return tab

average_H_03 = 0
average_H_07 = 0
average_EU_03 = 0
average_EU_07 = 0
average_AH_05 = 0

wierzcholki_alg_1_2 = int(input("Podaj ilość wierzchołków do algorytmów 1 i 2: "))
#zageszczenie_1_2 = float(input("Podaj zagęszczenie wieszchołków do algorytmów 1 i 2: "))
wierzcholki_alg_3= int(input("Podaj ilość wierzchołków do algorytmu 3: "))


print("\n")
print("Wierzchołki_1_2 : ", wierzcholki_alg_1_2,"\t\t\tWierzchołki_3 = ", wierzcholki_alg_3, "\n\n")

for i in range(10):
    graph_1 = makeEuGraphMatrix(wierzcholki_alg_1_2, 0.3)
    graph_1 = makeListaIncydencjiFromMatrix(graph_1)

    graph_2 = makeEuGraphMatrix(wierzcholki_alg_1_2, 0.7)
    graph_2 = makeListaIncydencjiFromMatrix(graph_2)

    graph_3 = makeEuGraphMatrix(wierzcholki_alg_3, 0.5)
    graph_3 = makeListaIncydencjiFromMatrix(graph_3)


    graph_kopia1_03 = deepcopy(graph_1)
    graph_kopia2_03 = deepcopy(graph_1)
    graph_kopia3_07 = deepcopy(graph_2)
    graph_kopia4_07 = deepcopy(graph_2)
    graph_kopia5_05 = deepcopy(graph_3)




    start_SearchHamiltonPath_03 = timer()
    SearchHamiltonPath(graph_kopia1_03)                                             #Ścieżka Hamiltona_03
    time_SearchHamiltonPath_03 = timer() - start_SearchHamiltonPath_03

    start_SearchHamiltonPath_07 = timer()
    SearchHamiltonPath(graph_kopia3_07)                                             #Ścieżka Hamiltona_07
    time_SearchHamiltonPath_07 = timer() - start_SearchHamiltonPath_07

    start_SearchEulerPath_03 = timer()
    SearchEulerPath(graph_kopia2_03)                                                   #Ścieżka Eulera_03
    time_SearchEulerPath_03 = timer() - start_SearchEulerPath_03

    start_SearchEulerPath_07 = timer()
    SearchEulerPath(graph_kopia4_07)                                                   #Ścieżka Eulera_03
    time_SearchEulerPath_07 = timer() - start_SearchEulerPath_07

    start_SearchAllHamiltonPaths_05 = timer()
    SearchAllHamiltonPaths(graph_kopia5_05)                                        #Wszystkie ścieżki Hamiltona_5
    time_SearchAllHamiltonPaths_05 = timer() - start_SearchAllHamiltonPaths_05

    #time_hamilton = end_SearchHamiltonPath - start_SearchHamiltonPath
    #time_euler = end_SearchEulerPath - start_SearchEulerPath
    #time_all_hamilton = end_SearchAllHamiltonPaths - start_SearchAllHamiltonPaths

    average_H_03 = average_H_03 + time_SearchHamiltonPath_03
    average_H_07 = average_H_07 + time_SearchHamiltonPath_07
    average_EU_03 = average_EU_03 + time_SearchEulerPath_03
    average_EU_07 = average_EU_07 + time_SearchEulerPath_07
    average_AH_05 = average_AH_05 + time_SearchAllHamiltonPaths_05
    print( time_SearchHamiltonPath_03, "\t", time_SearchHamiltonPath_07, "\t", time_SearchEulerPath_03, "\t", time_SearchEulerPath_07, "\t", time_SearchAllHamiltonPaths_05)

print("H_03\nH_07\nEU_03\nEU_07\nAH_05\n")

print("\n")
average_H_03 = average_H_03 / 10
print(average_H_03)

average_H_07 = average_H_07 / 10
print(average_H_07)

average_EU_03 = average_EU_03 / 10
print(average_EU_03)

average_EU_07 = average_EU_07 / 10
print(average_EU_07)

average_AH_05 = average_AH_05 / 10
print(average_AH_05)