Graphes

# -*- coding: utf-8 -*-

from support import *

# EXERCICE 1

G = {
    "A" : { "F" : 35, "C" : 5 },
    "F" : { "G" : 13 },
    "G" : { },
    "E" : { "G" : 14 },
    "B" : { "E" : 15, "C" : 9 },
    "D" : { "A" : 3, "B" : 12 },
    "C" : { "F" : 8, "E" : 10 }
    }

# [v for v in G["A"]] represente l'ensemble des sommets relies à A.
print(str([v for v in G["A"]]))

# EXERCICE 2

infini = float("inf")

def BFS(G, r, distance = False):
    global infini
    Couleur, Pere, Dist = dict(), dict(), dict()
    F = creer_file()
    for u in G:
        Couleur[u] = "Blanc"
        Pere[u] = None
        Dist[u] = infini
    enfiler(F, r)
    Couleur[r] = "Gris"
    Dist[r] = 0
    while not est_vide(F):
        u = tete(F)
        for v in G[u]:
            if Couleur[v] == "Blanc":
                Couleur[v] = "Gris"
                Dist[v] = Dist[u] + 1 * (1 - distance) + G[u][v] * distance
                Pere[v] = u
                enfiler(F, v)
        defiler(F)
        Couleur[u] = "Noir"
    return Dist

# Sans utiliser la vraie distance (distance en arcs)
print(str(BFS(G, "A")))
print(str(BFS(G, "D")))
# L'algorithme ne donnera plus la vraie distance la plus courte :
print(str(BFS(G, "D", True)))

# EXERCICE 3

def DFS(G, r):
    P = creer_pile()
    marque = {}
    parcours = []
    for u in G:
        marque[u] = False
    empiler(P, r)
    while not est_vide(P):
        u = sommet(P)
        desempiler(P)
        if not marque[u]:
            marque[u] = True
            parcours.append(u)
            for v in G[u]:
                if not marque[v]:
                    empiler(P, v)
    return parcours

# Affichage du parcours en profondeur
print(str(DFS(G, "A")))
print(str(DFS(G, "D")))

# EXERCICE 4

def creerMatrice(G):
    import numpy as np
    liste = []
    for i in range(len(G.keys())):
        temp = []
        for j in range(len(G.keys())):
            temp.append(infini)
        liste.append(temp)
    sortedKeys = list(G.keys())
    sortedKeys.sort()
    for i, e in enumerate(sortedKeys):
        liste[i][i] = 0
        for j, v in enumerate(sortedKeys):
            if G[e].get(v, -1) != -1:
                liste[i][j] = G[e][v]
    return np.array(liste)

import numpy as np

def init_distances_min(n):
    global infini
    liste = [[0 if i == j else infini for j in range(n)] for i in range(n)]
    return np.array(liste)

def iterations(distances, distances_min):
    retourne = []
    global infini
    for i in range(len(distances)):
        temp = []
        for j in range(len(distances)):
            temp.append(infini)
        retourne.append(temp)

    for i in range(len(distances)):
        for j in range(len(distances)):
            retourne[i][j] = min(distances_min[i][j], min([distances[i][t] + distances_min[t][j] for t in range(len(G))]))

    return np.array(retourne)

def utiliserIterations(G):
    distances = creerMatrice(G)
    t = init_distances_min(len(G))
    for i in range(len(G)):
        t = iterations(distances, t)
    return t

def itineraire_min(G, A, B):
    carte = utiliserIterations(G)