# coding=utf-8
from tkinter import Tk, Canvas
import math
import time

Noeuds = open("/Users/humazuhair/Downloads/Noeuds.csv", "r")
lignesNode = Noeuds.readlines()
TouslesNoueds = []
for lines in lignesNode:
    TouslesNoueds.append(lines.strip("\r\n"))
Noeuds.close()

# print(TouslesNoueds)

Longitude = []
Latitude = []

for unNode in TouslesNoueds:
    cetArc = unNode.split("\t")
    longt = float(cetArc[1])
    longt *= longt * math.pi / 180
    Longitude.append(longt)
    latt = float(cetArc[2])
    latt *= latt * math.pi / 180
    Latitude.append(latt)

minLat = min(Latitude)
maxLat = max(Latitude)
minLong = min(Longitude)
maxLong = max(Longitude)

arcs = open("/Users/humazuhair/Downloads/Arcs.csv", "r")
lignesArcs = arcs.readlines()
touslesarc = []
for lines in lignesArcs:
    touslesarc.append(lines.strip("\r\n"))
arcs.close()

Origine = []
Destination = []
Longueur = []
Dangerosite = []

for unArc in touslesarc:
    cetArc = unArc.split("\t")
    org = int(cetArc[0])
    Origine.append(org)
    dest = int(cetArc[1])
    Destination.append(dest)
    longueur = int(cetArc[2])
    Longueur.append(longueur)
    dang = int(cetArc[3])
    Dangerosite.append(dang)

nbArcs = len(Origine)

nbSommets = max(max(Origine), max(Destination)) + 1

successeurs = [[] for j in range(nbSommets)]
for u in range(0, nbArcs):
    orig = Origine[u]
    desti = Destination[u]
    successeurs[orig].append(desti)


def arc(i, j):
    for u in range(nbArcs):
        if Origine[u] == i and Destination[u] == j:
            return u


# ########################################################
# Dessin du graphe
# ########################################################

print('*****************************************')
print('* Dessin du graphe                      *')
print('*****************************************')


def cercle(x, y, r, couleur):
    can.create_oval(x - r, y - r, x + r, y + r, outline=couleur, fill=couleur)


def TraceCercle(j, couleur, rayon2):
    x = (Longitude[j] - minLong) * ratioWidth + border
    y = ((Latitude[j] - minLat) * ratioHeight) + border
    y = winHeight - y
    cercle(x, y, rayon2, couleur)


fen = Tk()
fen.title('Graphe')
coul = "dark green"  # ['purple','cyan','maroon','green','red','blue','orange','yellow']

Delta_Long = maxLong - minLong
Delta_Lat = maxLat - minLat
border = 20  # taille en px des bords
winWidth_int = 800
winWidth = winWidth_int + 2 * border  # largeur de la fenetre
winHeight_int = 800
winHeight = winHeight_int + 2 * border  # hauteur de la fenetre : recalculee en fonction de la taille du graphe
# ratio= 1.0          # rapport taille graphe / taille fenetre
ratioWidth = winWidth_int / (maxLong - minLong)  # rapport largeur graphe/ largeur de la fenetre
ratioHeight = winHeight_int / (maxLat - minLat)  # rapport hauteur du graphe hauteur de la fenetre

can = Canvas(fen, width=winWidth, height=winHeight, bg='dark grey')
can.pack(padx=5, pady=5)

#  cercles
rayon = 1  # rayon pour dessin des sommets
rayon_od = 5  # rayon pour sommet origine et destination
# Affichage de tous les sommets
for i in range(0, nbSommets):
    TraceCercle(i, 'black', rayon)


def segment(x1, y1, x2, y2, couleur):
    can.create_line(x1, y1, x2, y2, fill=couleur)


def TraceSegment(i, j, couleur):
    x1 = (Longitude[i] - minLong) * ratioWidth + border
    y1 = ((Latitude[i] - minLat) * ratioHeight) + border
    y1 = winHeight - y1
    x2 = (Longitude[j] - minLong) * ratioWidth + border
    y2 = ((Latitude[j] - minLat) * ratioHeight) + border
    y2 = winHeight - y2
    segment(x1, y1, x2, y2, couleur)


for u in range(nbArcs):
    TraceSegment(Origine[u], Destination[u], 'yellow')

sommet_depart = 3000
sommet_destination = 11342

time_start = time.time()

TraceCercle(sommet_depart, 'green', rayon_od)
TraceCercle(sommet_destination, 'red', rayon_od)


infini = 99999999

Pi = [infini for j in range(nbSommets)]
Piprime = [infini for j in range(nbSommets)]
LePere = [-1 for j in range(nbSommets)]
marque = [0 for j in range(nbSommets)]
Pi[sommet_depart] = 0
Piprime[sommet_depart] = 0

for j in successeurs[sommet_depart]:
    Pi[j] = Longueur[arc(sommet_depart, j)]
    #  print(j, Pi[j])
    LePere[j] = sommet_depart

nb_sommets_explores = 0
fini = False
sommet_retenu = sommet_depart
while nb_sommets_explores < nbSommets and not fini:
    # print(sommet_retenu)
    pimin = infini
    for j in range(nbSommets):
        if Piprime[j] == infini and Pi[j] < pimin:
            sommet_retenu = j
            pimin = Pi[j]
    marque[sommet_retenu] = 1
    # nb_sommets_explores +=1
    Piprime[sommet_retenu] = Pi[sommet_retenu]
    TraceCercle(sommet_retenu, 'yellow', 1)
    if sommet_retenu == sommet_destination:
        fini = True
    for k in successeurs[sommet_retenu]:
        if Pi[k] >= Pi[sommet_retenu] + Longueur[arc(sommet_retenu, k)] \
                and Piprime[k]==infini:
            Pi[k] = Pi[sommet_retenu] + Longueur[arc(sommet_retenu, k)]
            LePere[k] = sommet_retenu
    # if nb_sommets_explores == 5: fini=True

print("calcule du chemin: ")
k = sommet_destination
# mettre à jour les succ de k
while k != sommet_depart:
    Arcs = arc(LePere[k], k)
    TraceCercle(k, 'maroon', 2)
    k = LePere[k]

print(time.time() - time_start)

fen.mainloop()
