from networkx import *
from numpy import array


# retourne un graphe, ce graphe est le premier graphe du tp
def creationGraph():
    G = XDiGraph()

    # Ajout des noeuds
    L = []
    for x in range(4):
        for y in range(5):
            L.append((x,y))
            G.add_nodes_from(L)
            
    # Ajout des aretes
    G.add_edge(0,1,5)
    G.add_edge(1,2,8)
    G.add_edge(2,3,4)
    
    G.add_edge(4,5,9)
    G.add_edge(5,6,6)
    G.add_edge(6,7,7)
    
    G.add_edge(8,9,7)
    G.add_edge(9,10,5)
    G.add_edge(10,11,8)
    
    G.add_edge(12,13,8)
    G.add_edge(13,14,6)
    G.add_edge(14,15,5)
    
    G.add_edge(16,17,3)
    G.add_edge(17,18,8)

    G.add_edge(18,19,7)
    
    G.add_edge(0,4,4)
    G.add_edge(4,8,8)
    G.add_edge(8,12,4)
    G.add_edge(12,16,7)
    
    G.add_edge(1,5,7)
    G.add_edge(5,9,5)
    G.add_edge(9,13,4)
    G.add_edge(13,17,5)
    
    G.add_edge(2,6,4)
    G.add_edge(6,10,7)
    G.add_edge(10,14,7)
    G.add_edge(14,18,4)
    
    G.add_edge(3,7,6)
    G.add_edge(7,11,6)
    G.add_edge(11,15,8)
    G.add_edge(15,19,6)
    
    return G




# Algorithme de Floyd-Warshall
def floyd(G):

    M = array([[ 0 ] * 20]*20) # matrice des couts
    P = array(M, copy=1)       # matrice des predecesseurs
    
    # construction de la premiere matrice M et de la premiere matrice P
    for i in range(20):
        for j in range(20):
            if i<>j:
                if G.has_edge(i,j):
                    M[i,j]=G.get_edge(i,j)
                    P[i,j]=i
                else:
                    M[i,j]=-1
                    P[i,j]=-1
            else:
                M[i,j]=0
                P[i,j]=-1

    # construction des 20 matrices suivantes (pour M et P)
    for k in range(20):
        M_old = array(M, copy=1)
        P_old = array(P, copy=1)
        for i in range(20):
            for j in range(20):
                if i<>j:
                    if M_old[i,j]==-1:
                        if M_old[i,k]==-1 or M_old[k,j]==-1:
                            M[i,j]=-1
                            P[i,j]=-1
                        else:
                            M[i,j]=M_old[i,k]+M_old[k,j]
                            P[i,j]=P[k,j]
                    else:
                        if M_old[i,k]==-1 or M_old[k,j]==-1:
                            M[i,j]=M_old[i,j]
                            P[i,j]=P[i,j]                            
                        else:
                            if M_old[i,j]<= M_old[i,k]+M_old[k,j]:
                                M[i,j]=M_old[i,j]
                                P[i,j]=P[i,j]
                            else:
                                M[i,j]=M_old[i,k]+M_old[k,j]
                                P[i,j]=P[k,j]
                else:
                    M[i,j]=0
                    P[i,j]=-1

    return (M,P)






# M et P : les deux matrices construites par la fonction floyd
# source et destination : deux noeuds
# Affiche le chemin et le cout entre source et destination s'il existe,
# sinon previent qu'il n'y a pas de chemin
#
# Attention, le chemin s'affiche a l'envers, cad en partant de
# la destination vers la source

def calcul_chemin(M, P, source, destination):
    print "***********************************"
    if M[source, destination] == -1:
        print "pas de chemin entre %d et %d" % (source, destination)
    else:
        print "chemin entres les noeuds %d et %d" % (source, destination)
        print "distance = %d" % M[source, destination]
        print "chemin :"
        print destination
        a = P[source,destination]
        while a <> source:
            print a
            a = P[source,a]
        print source
    
    

########################################
# main


G = creationGraph()
(M,P) = floyd(G)


# Exemple 1 : on calcul le chemin sans utiliser la fonction calcul_chemin
print "***********************************"
print "chemin du noeud 0 au noeud 19 :"
print "distance = %d" % M[0,19]
# Le chemin s'affiche a l'envers, cad
# en partant de la destination vers la source
print "chemin :"
print 19
a = P[0,19]
while a <> 0:
    print a
    a = P[0,a]
print 0

# Exemples 2 et 3 : utilisation de la fonction calcul_chemin

# Affiche le chemin entre les noeuds 1 et 3
calcul_chemin(M,P,1,3)

# Il n'y a pas de chemin entre les noeuds 1 et 4
calcul_chemin(M,P,1,4)