import time as t
import matplotlib.pyplot as plt
import numpy as np
import random as rd

nbc=10

class ChaineInvalide(Exception):
    """Exception levee si une chaine n'est pas valide.
    """
    def __init__(self, chaine, message):
        self.chaine = chaine
        self.message = message

def mesureTemps(fonc):
    def foncMesuree(*argv,**keys):
        T=t.clock()
        res=fonc(*argv,**keys)
        print("\nTemps d'exécution : "+str(t.clock()-T))
        return res
    return foncMesuree

def constructionGraphe(n,manquant=[]):
    sommets=list(range(1,n+1))
    aretes=[]
    for j in range(1,n//2+1):
        for k in range(2,n//j+1):
            aretes.append({j,k*j})
    nbaretes=[sum([1 for k in aretes if j in k]) for j in sommets]
    graphe=(sommets,aretes,nbaretes)
    if manquant:
        for k in manquant:
            graphe=oteSommet(graphe,k)
    return graphe

def oteSommet(graphe,S):
    sommets,aretes,nbaretes=graphe
    sommets=[s for s in sommets if s!=S]
    aretes=[a for a in aretes if S not in a]
    nbaretes=[sum([1 for k in aretes if j in k]) for j in sommets]
    return (sommets,aretes,nbaretes)

# cosmétique
def repGraphe(graphe,n=None):
    sommets,aretes,nbaretes=graphe
    if n is None:
        n=len(sommets)
    for S in sommets:
        x,y=np.cos(S*np.pi*2/n),np.sin(S*np.pi*2/n)
        r=1.05-0.02*(y+x) # pour décaler les labels par rapport au sommet
        plt.plot(x,y,'ok')
        plt.text(x*r,y*r,str(S))
    for k in aretes:
        k=list(k)
        if k[0]<k[1]:
            R=(1+np.cos(k[0]*np.pi*2/n))/2
            G=(1+np.cos(k[0]*np.pi*2/n-np.pi*2/3))/2
            B=(1+np.cos(k[0]*np.pi*2/n-np.pi*4/3))/2
            couleur=(R,G,B)
            X=[np.cos(k[0]*np.pi*2/n),np.cos(k[1]*np.pi*2/n)]
            Y=[np.sin(k[0]*np.pi*2/n),np.sin(k[1]*np.pi*2/n)]
            plt.plot(X,Y,color=couleur)
    plt.axis('scaled')

# cosmétique 2
def repGraphe2(sommets,plc):
    n=len(sommets)
    for S in sommets:
        x,y=np.cos(S*np.pi*2/n),np.sin(S*np.pi*2/n)
        r=1.05-0.02*(y+x) # pour décaler les labels par rapport au sommet
        plt.plot(x,y,'ok')
        plt.text(x*r,y*r,str(S))
    X=[]
    Y=[]
    i=0
    p=len(ch)
    for k in plc:
        X.append(np.cos(k*np.pi*2/n))
        Y.append(np.sin(k*np.pi*2/n))
        i+=1
        if i>1:
            R=(1+np.cos(i*np.pi/p))/2
            G=i/n*(1+np.cos(2*i*np.pi/p-np.pi/2))/2
            B=(1+np.cos(i*np.pi/p-np.pi))/2
            couleur=(R,G,B)
            if i%2:
                ls='-'
            else:
                ls='--'
            plt.plot(X[-2:],Y[-2:],color=couleur,linestyle=ls)
    plt.axis('scaled')

def verif(L,sommets):
    L=L[:]
    for s in L:
        if s not in sommets:
            return str(L)+" n'a pas tous ses sommets dans "+str(sommets)
    ver=[L.pop()]
    while L:
        nouv=L.pop()
        if nouv in ver:
            return "Doublon : "+str(nouv)
        if nouv%ver[-1]!=0 and ver[-1]%nouv!=0:
            return str(nouv)+" et "+str(ver[-1])+"sont des voisins sans lien de divisibilité"
        ver.append(nouv)
    return 0

def _PLC(graphe,debut,total=False,nbc=nbc,verbose=False):
    sommets,aretes,nbaretes=graphe
    n=len(sommets)
    soms=[]
    for k in aretes:
        if debut in k:
            soms.append((k-{debut}).pop())
    if not soms:
        return 1,[debut] 
    nbar=[nbaretes[k] for k in range(n) if sommets[k] in soms]
    if not total:
        m=min(nbar)
        # Le point crucial se trouve là !
        # Plus nbc est grand, plus l'algo est rapide mais moins bon est le chemin trouvé
        d=1 if m==1 else (rd.randint(0,nbc-1)==(nbc-1))
        prochains=[sommets[k] for k in range(n) if sommets[k] in soms and m<=nbaretes[k]<=m+d]
    else:
        prochains=soms
    som,are,nba=oteSommet((sommets,aretes,nbaretes),debut)
    M=0
    Ch=[]
    for P in prochains:
        nb,ch=_PLC((som,are,nba),P,total=total,nbc=nbc)
        if nb>M:
            M=nb
            Ch=[debut]+ch
    return M+1,Ch

@mesureTemps
def PLC(graphe,graine=[],total=False,nbc=nbc,verbose=False,limPremierPas=0):
    """Calcul un long chemin dans un graphe non orienté.
        
Paramètres :
    graphe:
        sous la forme (sommets,aretes,nbaretes) où  
        sommets est la liste des sommets  
        aretes est la liste des arêtes données sous forme d'ensemble  
        nbaretes est la liste du nombre d'arêtes partant de chaque sommet  
    graine:
        liste imposée d'un chemin contenu dans le long chemin renvoyé.
    total:
        si total=True et limPremierPas=0, le chemin renvoyé sera le  
        plus long chemin.  
        
        Attention !!!
        La complexité de l'algorithme est alors beaucoup trop grande pour  
        espérer une valeur de retour si le graphe possède plus de ~40  
        sommets.
    nbc:
        utilisé lorsque total==False. L'algorithme élague alors l'arbre  
        en ne prenant que les sommets possédant un minimum d'arêtes. nbc est  
        utilisé pour, aléatoirement, choisir aussi des sommets avec un peu plus  
        d'arêtes. Plus précisément, la probabilité d'explorer les sommets 
        possédant plus que le minimum d'arêtes est 1/nbc.
    verbose : 
        si verbose=True, affiche l'état d'avancement de la recherche.
    limPremierPas :
        si elle vaut 0, pas de limite  
        sinon, ne prend pour le premier pas après la graine
        que les sommets dont le nombre d'arêtes est inférieur à la valeur donnée.

Valeurs de retour:
    Couple (nb,ch) où:
        nb est le nombre de sommets du chemin;  
        ch est la liste des sommets du chemin.
    """
    if graine:
        n=len(graine)
        message=verif(graine,graphe[0])
        if message:
            raise ChaineInvalide(graine,message)
        S0=graine[0]
        S1=graine[-1]
        for k in graine[1:-1]:
            graphe=oteSommet(graphe,k)
        vois0=[a for a in graphe[0] if a!=S1 and a!=S0 and not(a%S0 and S0%a)]

        if limPremierPas:
            vois0=[l for l in vois0 if sum([1 for a in graphe[1] if l in a])<=limPremierPas]
        graphe=oteSommet(graphe,S0)
        vois1=[a for a in graphe[0] if a!=S1 and a!=S0 and not(a%S1 and S1%a)]
        graphe=oteSommet(graphe,S1)
        M=0
        Ch=[]
        if verbose:
            print('À faire :',vois0,'\nTraitement : ',end='')
        for S in vois0:
            if verbose:
                print(S,end=';')
            nb,ch=_PLC(graphe,S,total=total,nbc=nbc)
            if nb>M:
                M=nb
                Ch=ch
        for k in Ch:
            graphe=oteSommet(graphe,k)
        vois1=[k for k in vois1 if k not in Ch]
        Ch1=[]
        M1=0
        if verbose:
            print()
            print('À faire :',vois1,'\nTraitement : ',end='')
        for s in vois1:
            if verbose:
                print(s,end=';')
            nb1,ch1=_PLC(graphe,s,total=total,nbc=nbc,verbose=verbose)
            if nb1>M1:
                M1=nb1
                Ch1=ch1
        return M1+M+n,Ch[::-1]+graine+Ch1
    else:
        vois1=[k for k in graphe[0] if k!=1]
        if limPremierPas:
            vois1=[k for k in vois1 if sum([1 for a in graphe[1] if k in a])<=lpp]
        nb,ch=_PLC(graphe,1,total=total,nbc=nbc)
        for s in ch:
            graphe=oteSommet(graphe,s)
        vois1=[k for k in vois1 if k not in ch]
        M=0
        Ch=[]
        if verbose:
            print('À faire :',vois0,'\nTraitement : ',end='')
        for s in vois1:
            if verbose:
                print(s,end=';')
            nb1,ch1=_PLC(graphe,s,total=total,nbc=nbc)
            if nb1>M:
                M=nb1
                Ch=ch1
        return nb+M,ch1[-1::-1]+ch

def analyse(n,plc):
    from sympy import sieve
    prems1 = list(sieve.primerange(n//2+1,n+1))
    prems2 = list(sieve.primerange(n//3+1,n//2+1))
    prems3 = list(sieve.primerange(n//4+1,n//3+1))
    el=list(set(range(1,n+1))-set(plc))
    e1=[k for k in el if k in prems1]
    e2=[k for k in el if k in prems2]+[2*k for k in el if k in prems2]
    e3=[k for k in el if k in prems3]+[2*k for k in el if k in prems3]+[3*k for k in el if k in prems3]
    e4=[k for k in el if k not in e1 and k not in e2 and k not in e3]
    return e1,e2,e3,e4

def sauve():
    chaine=[]
    chaine.append("Valeur de n : "+str(n)+'\n\r')
    chaine.append("Valeur de total : "+str(total)+'\n\r')
    chaine.append("Valeur de nbc : "+str(nbc)+'\n\r')
    chaine.append("Valeur de graine : "+str(graine)+'\n\r')
    chaine.append("Valeur de lpp : "+str(lpp)+'\n\r')
    chaine.append("Longueur du plus long chemin trouvé : "+str(nb)+'\n\r')
    chaine.append("Chemin : "+str(ch)+'\n\r')
    chaine.append("Analyse des entiers manquants : "+str(analyse(n,ch))+'\n\r')
    chaine.append("----------------------------------------------------------"+'\n\r')
    with open('Records.txt','a') as f:
        f.writelines(chaine)

rd.seed(t.time())

n=100
# nbc ==1 : pas d'aléatoire, assez lent
# nbc grand : rapide, ne donne probablement pas le plus long chemin
nbc=10
# total == True : donne le plus long chemin (si lpp==0), aucun élagage de l'arbre !!!
# Rq : en fait, le plus long chemin n'est garanti que si graine=[1]
# N'utilise pas nbc mais utilise lpp.
# Complexité beaucoup trop grande dès que n>~35
total=False
# graine : sous-chemin imposé
graine=[69,23,46,92,1]
# lpp == 0 : pas d'élagage de l'arbre pour le premier pas
# lpp > 0 : on ne prend pour le premier pas après la graine
#           que les sommets dont le nombre d'arêtes <=lpp
lpp=0

from sympy import sieve
prems1 = list(sieve.primerange(n//2+1,n+1))
prems2 = list(sieve.primerange(n//3+1,n//2+1))
prems3 = list(sieve.primerange(n//4+1,n//3+1))
prems4 = list(sieve.primerange(n//5+1,n//4+1))

g=constructionGraphe(n)#,manquant=prems1+prems2+[2*k for k in prems2])
nb,ch=PLC(g,graine,total=total,nbc=nbc,verbose=True,limPremierPas=lpp)
print("Valeur de n :",n)
print("Longueur du plus long chemin trouvé :",nb)
print("Chemin :",ch)
repGraphe2(range(1,n+1),ch)
print("Analyse des entiers manquants :\n",analyse(n,ch))
print("Nombres premiers dans les intervalles ]n/2;n], etc...\n",
    prems1,prems2,prems3,prems4)