La base de la théorie des graphes avec l'animation matplotlib

Sera traité ici.

Bases de la théorie des graphes

Bases de la théorie des graphes </ b> https://qiita.com/maskot1977/items/e1819b7a1053eb9f7d61

J'ai écrit un article dans le passé et j'ai reçu des "j'aime" de nombreuses personnes, mais cette fois, j'aimerais rendre le contenu facile à comprendre grâce à l'animation.

Animation à l'aide de matplotlib

Une animation simple peut être dessinée comme suit.

# -*- coding: UTF-8 -*-
import math
import matplotlib.pyplot as plt
import matplotlib.animation as animation
from IPython.display import HTML

fig = plt.figure()

ims = [] #Vidéo = liste qui stocke un ensemble d'images fixes
for i in range(360):
    rad = math.radians(i)
    x1, y1 = math.cos(rad), math.sin(rad)
    x2, y2 = math.cos(rad * 2), math.sin(rad * 2)
    im = plt.scatter(x1, y1) #Image fixe partie 1 (pas de type liste)
    im2 = plt.scatter(x2, y2) #Image fixe partie 2 (pas de type liste)
    im3 = plt.plot([x1, x2], [y1, y2]) #Image fixe partie 3 (type de liste)
    image = [im, im2] + im3 #Une liste représente une image fixe
    ims.append(image) #Ajouter une image fixe

#Convertir en vidéo
ani = animation.ArtistAnimation(fig, ims, interval=10, repeat_delay=1000)

ani.save("Animation1.gif", writer='pillow') #Enregistrer en tant que fichier gif
HTML(ani.to_jshtml()) #Afficher sur HTML

Animation1.gif

  • Si l'animation se termine et s'arrête, vous pouvez la déplacer à nouveau en cliquant sur l'image.

Données de localisation du bureau de la préfecture du Japon

Utilisez les mêmes données que Bases de la théorie des graphes. Les coordonnées (latitude / longitude) de la ville où se trouve la préfecture sont écrites. La ville où se trouve le bureau préfectoral s'appelle le "haut" </ b>, et la ligne droite reliant les villes est appelée le "côté" </ b>. Les villes reliées par un côté sont appelées "adjacentes" </ b>.

import urllib.request
url = 'https://raw.githubusercontent.com/maskot1977/ipython_notebook/master/toydata/location.txt'
urllib.request.urlretrieve(url, 'location.txt') #Télécharger les données
('location.txt', <http.client.HTTPMessage at 0x11c9c2320>)

Lisons-le en utilisant des pandas, qui n'ont pas été utilisés dans Bases de la théorie des graphes.

import pandas as pd
japan = pd.read_csv('location.txt')
japan
Town Longitude Latitude
0 Sapporo 43.06417 141.34694
1 Aomori 40.82444 140.74000
2 Morioka 39.70361 141.15250
3 Sendai 38.26889 140.87194
4 Akita 39.71861 140.10250
5 Yamagata 38.24056 140.36333
... ... ... ...
45 Kagoshima 31.56028 130.55806
46 Naha 26.21250 127.68111

Illustré.

%matplotlib inline
import matplotlib.pyplot as plt
plt.figure(figsize=(10, 8))
plt.scatter(japan['Latitude'], japan['Longitude'])
for city, x, y in zip(japan['Town'], japan['Latitude'], japan['Longitude']):
    plt.text(x, y, city, alpha=0.5, size=12)
plt.grid()

output_5_1.png

En utilisant les données ci-dessus, créons une animation de recherche de priorité de profondeur, de recherche de priorité de largeur et de recherche de meilleure priorité, qui sont les algorithmes de base de la théorie des graphes.

Matrice de distance

Je ne l'ai pas utilisé dans Basics of Graph Theory, mais si vous utilisez scipy, la matrice de distance (distance entre les sommets) peut être calculée comme suit.

import numpy as np
from scipy.spatial import distance

mat = japan[['Latitude', 'Longitude']].values
dist_mat = distance.cdist(mat, mat, metric='euclidean') #Distance euclidienne

Une fonction qui obtient des coordonnées pour tracer une ligne droite entre deux points

Afin de tracer une ligne droite entre deux points lors du dessin d'un graphe, je vais créer ma propre fonction pour trouver les coordonnées de l'ensemble des côtés (ensemble des sommets).

def get_edges(routes):
    edges = []
    for route in routes:
        if len(route) == 2:
            town1, y1, x1 = [value for value in japan.values][route[0]]
            town2, y2, x2 = [value for value in japan.values][route[1]]
            edges.append([[x1, x2], [y1, y2]])
    return edges

L'exemple d'utilisation ressemble à ceci.

get_edges([[1, 2], [3, 4], [5, 6]])
[[[140.74, 141.1525], [40.82444, 39.70361]],
 [[140.87194, 140.1025], [38.26889, 39.71861]],
 [[140.36333, 140.46778], [38.240559999999995, 37.75]]]

Recherche de priorité de profondeur

Maintenant, en tant que premier algorithme de recherche de graphique, nous allons faire une recherche de priorité de profondeur.

Fonction pour obtenir la liste de contiguïté 1

Dans la recherche de graphe, comment créer une "liste adjacente" (quel sommet peut aller de quel sommet) est très important, mais "relier les arêtes entre les pics au-dessous d'une certaine distance (seuil)" </ b> Je voudrais suivre cette politique. En utilisant numpy et la matrice de distance, qui n'ont pas été utilisées dans Bases de la théorie des graphes, il peut être calculé comme suit.

def neighbor(town, dist_mat=dist_mat, threshold=1): #Fonction pour obtenir la liste de contiguïté 1
    return [x[0] for x in enumerate(np.where(dist_mat[town] <= threshold, True, False)) if x[1]]

L'exemple d'utilisation ressemble à ceci.

neighbor(12) #Quelles villes sont à moins de 1 distance de Tokyo?
[7, 8, 9, 10, 11, 12, 13]

Fonction de recherche graphique 1

Dans Bases de la théorie des graphes, l'instruction while a été utilisée pour résoudre le problème de recherche de graphes, mais ici, je veux montrer la progression étape par étape. J'ai défini la fonction pour avancer d'une étape de la recherche comme suit.

def traverse(i=0): #Une étape de recherche de priorité en profondeur
    if len(stack) != 0: #Si la pile n'est pas vide
        next_town, current_town = stack.pop() #Obtenir l'itinéraire suivant (emplacement actuel et ville suivante)
        current_direction = [[next_town, current_town]] #Pour dessiner
        if next_town not in visited_towns: #Si la ville suivante n'a pas été visitée
            used_routes.append([next_town, current_town]) #Enregistrer l'itinéraire
            visited_towns.append(next_town) #Faites-le visiter
            for nei in neighbor(next_town): #Sortez les villes adjacentes à la ville visitée une par une
                if nei not in visited_towns: #Si vous n'avez pas visité
                    stack.append([nei, next_town]) #Mettez l'itinéraire sur la pile
    return current_direction #Pour dessiner

Animation de recherche de priorité de profondeur 1

Maintenant animons-le.

# -*- coding: UTF-8 -*-
import math
import matplotlib.pyplot as plt
import matplotlib.animation as animation
from IPython.display import HTML

fig = plt.figure(figsize=(10, 8))

stack = [[12, 12]] #Le point de départ est Tokyo
visited_towns = [] #Arrangement pour stocker les villes visitées
used_routes = [] #Un tableau qui stocke les routes réellement utilisées
current_direction = [] #Route en cours de vérification
ims = [] #Disposition pour stocker des images fixes
i = 0
while len(stack) > 0: #Si la pile n'est pas vide
    if i != 0: #La valeur initiale étant affichée la première fois, la recherche ne peut pas continuer.
        current_direction = traverse() #Faites une étape de recherche
    image = [] #Un tableau qui stocke les parties à écrire dans une image fixe
    for edge in get_edges(stack): #La ligne rouge est la route «candidate» dans la pile
        image += plt.plot(edge[0], edge[1], 'r', alpha=0.5)

    for edge in get_edges(current_direction): #La ligne bleue est l'itinéraire en cours de vérification
        image += plt.plot(edge[0], edge[1], 'b', lw=5, alpha=0.5)

    for edge in get_edges(used_routes): #La ligne noire est un itinéraire utilisé
        image += plt.plot(edge[0], edge[1], 'k', lw=2)

    for city, x, y in zip(japan['Town'], japan['Latitude'], japan['Longitude']):
        image.append(plt.text(x, y, city, alpha=0.5, size=12)) #Afficher le nom de la ville

    if len(current_direction) > 0:
        current_town = current_direction[0][0]
        image += plt.plot(japan.iloc[current_town, :]['Latitude'], 
                          japan.iloc[current_town, :]['Longitude'], 
                          markersize=20, marker='o') #Maru est la ville en cours de vérification
    ims.append(image) #Stocker une image fixe
    i += 1

#Convertir en vidéo
ani = animation.ArtistAnimation(fig, ims, interval=500, repeat_delay=1000)

ani.save("Animation2.gif", writer='pillow') #Enregistrer en tant que fichier gif
HTML(ani.to_jshtml()) #Afficher sur HTML

Animation de recherche de priorité de profondeur 1 Animation2.gif

  • Si l'animation se termine et s'arrête, vous pouvez la déplacer à nouveau en cliquant sur l'image.

Fonction pour obtenir la liste de contiguïté 2

Dans la recherche de priorité de profondeur ci-dessus, la «dernière ville de la pile» est la prochaine destination candidate. Lorsque vous vous déplacez dans une ville, les villes voisines sont dans la pile. À ce stade, le comportement change même avec la même recherche de priorité de profondeur en tenant compte de l'ordre de leur mise dans la pile. Modifions-le pour que les villes proches les unes des autres soient préférentiellement sélectionnées comme destinations candidates.

import numpy as np
def neighbor(town, dist_mat=dist_mat, threshold=1): #Fonction pour obtenir la liste de contiguïté 2
    return np.argsort(dist_mat[town])[1:np.where(dist_mat[town] <= threshold, 1, 0).sum()][::-1]

Animation de recherche de priorité de profondeur 2

Le code ci-dessous est le même que celui de la précédente "Animation de recherche de priorité à la profondeur 1" (seul le nom de fichier de la vidéo enregistrée est différent). Voyons comment changer la fonction voisin change son comportement.

# -*- coding: UTF-8 -*-
# -*- coding: UTF-8 -*-
import math
import matplotlib.pyplot as plt
import matplotlib.animation as animation
from IPython.display import HTML

fig = plt.figure(figsize=(10, 8))

stack = [[12, 12]] #Le point de départ est Tokyo
visited_towns = [] #Arrangement pour stocker les villes visitées
used_routes = [] #Un tableau qui stocke les routes réellement utilisées
current_direction = [] #Route en cours de vérification
ims = [] #Disposition pour stocker des images fixes
i = 0
while len(stack) > 0: #Si la pile n'est pas vide
    if i != 0: #La valeur initiale étant affichée la première fois, la recherche ne peut pas continuer.
        if stack[0] != []: #La recherche ne se poursuit pas même au dernier affichage
            current_direction = traverse() #Faites une étape de recherche
    image = [] #Un tableau qui stocke les parties à écrire dans une image fixe
    for edge in get_edges(stack): #La ligne rouge est la route «candidate» dans la pile
        image += plt.plot(edge[0], edge[1], 'r', alpha=0.5)

    for edge in get_edges(current_direction): #La ligne bleue est l'itinéraire en cours de vérification
        image += plt.plot(edge[0], edge[1], 'b', lw=5, alpha=0.5)

    for edge in get_edges(used_routes): #La ligne noire est un itinéraire utilisé
        image += plt.plot(edge[0], edge[1], 'k', lw=2)

    for city, x, y in zip(japan['Town'], japan['Latitude'], japan['Longitude']):
        image.append(plt.text(x, y, city, alpha=0.5, size=12)) #Afficher le nom de la ville

    if len(current_direction) > 0:
        current_town = current_direction[0][0]
        image += plt.plot(japan.iloc[current_town, :]['Latitude'], 
                          japan.iloc[current_town, :]['Longitude'], 
                          markersize=20, marker='o') #Maru est la ville en cours de vérification
    ims.append(image) #Stocker une image fixe
    
    if len(stack) == 0: #Pour le dernier affichage
        current_direction = []
        stack.append([])
    elif stack[0] == []: #Pour la dernière évasion
        break
    i += 1

#Convertir en vidéo
ani = animation.ArtistAnimation(fig, ims, interval=500, repeat_delay=1000)

ani.save("Animation3.gif", writer='pillow') #Enregistrer en tant que fichier gif
HTML(ani.to_jshtml()) #Afficher sur HTML

Animation de recherche de priorité de profondeur 2 Animation3.gif

  • Si l'animation se termine et s'arrête, vous pouvez la déplacer à nouveau en cliquant sur l'image.

Recherche de priorité de largeur

Ensuite, faisons une recherche de priorité de largeur. L'algorithme de base est presque le même, il suffit de mettre la pile (premier entré, dernier sorti) dans une file d'attente (file d'attente: premier entré, premier sorti).

Fonction de recherche graphique 2

Réécrivez la fonction «traversée». La partie à réécrire n'est qu'un seul point indiqué comme "changement". Étant donné que la liste utilisée comme pile change en file d'attente, je voudrais changer le nom de la variable stack, mais cela augmentera la partie à réécrire, alors laissons pile telle quelle.

def traverse(i=0): #1 étape de recherche de priorité de largeur
    if len(stack) != 0:
        next_town, current_town = stack.pop(0) #point de changement
        current_direction = [[next_town, current_town]]
        if next_town not in visited_towns:
            used_routes.append([next_town, current_town])
            visited_towns.append(next_town)
            for nei in neighbor(next_town):
                if nei not in visited_towns:
                    stack.append([nei, next_town])
    return current_direction

Fonction pour obtenir la liste de contiguïté 3

La fonction pour obtenir la liste de contiguïté est également réécrite, mais elle est fondamentalement la même que la précédente. La pile est mise en file d'attente, il vous suffit donc de retourner la commande.

import numpy as np
def neighbor(town, dist_mat=dist_mat, threshold=1): #Fonction pour obtenir la liste de contiguïté 3
    return np.argsort(dist_mat[town])[1:np.where(dist_mat[town] <= threshold, 1, 0).sum()] #Changer seulement la fin

Animation de recherche de priorité de largeur

Le code suivant est également le même que «Animation de recherche de priorité de profondeur 1» et «Animation de recherche de priorité de profondeur 2» (seul le nom de fichier de la vidéo enregistrée est différent). Voyons comment changer la fonction «traverse» change le comportement.

# -*- coding: UTF-8 -*-
import math
import matplotlib.pyplot as plt
import matplotlib.animation as animation
from IPython.display import HTML

fig = plt.figure(figsize=(10, 8))

stack = [[12, 12]] #Le point de départ est Tokyo
visited_towns = [] #Arrangement pour stocker les villes visitées
used_routes = [] #Un tableau qui stocke les routes réellement utilisées
current_direction = [] #Route en cours de vérification
ims = [] #Disposition pour stocker des images fixes
i = 0
while len(stack) > 0: #Si la pile n'est pas vide
    if i != 0: #La valeur initiale étant affichée la première fois, la recherche ne peut pas continuer.
        if stack[0] != []: #La recherche ne se poursuit pas même au dernier affichage
            current_direction = traverse() #Faites une étape de recherche
    image = [] #Un tableau qui stocke les parties à écrire dans une image fixe
    for edge in get_edges(stack): #La ligne rouge est la route «candidate» dans la pile
        image += plt.plot(edge[0], edge[1], 'r', alpha=0.5)

    for edge in get_edges(current_direction): #La ligne bleue est l'itinéraire en cours de vérification
        image += plt.plot(edge[0], edge[1], 'b', lw=5, alpha=0.5)

    for edge in get_edges(used_routes): #La ligne noire est un itinéraire utilisé
        image += plt.plot(edge[0], edge[1], 'k', lw=2)

    for city, x, y in zip(japan['Town'], japan['Latitude'], japan['Longitude']):
        image.append(plt.text(x, y, city, alpha=0.5, size=12)) #Afficher le nom de la ville

    if len(current_direction) > 0:
        current_town = current_direction[0][0]
        image += plt.plot(japan.iloc[current_town, :]['Latitude'], 
                          japan.iloc[current_town, :]['Longitude'], 
                          markersize=20, marker='o') #Maru est la ville en cours de vérification
    ims.append(image) #Stocker une image fixe
    
    if len(stack) == 0: #Pour le dernier affichage
        current_direction = []
        stack.append([])
    elif stack[0] == []: #Pour la dernière évasion
        break
    i += 1

#Convertir en vidéo
ani = animation.ArtistAnimation(fig, ims, interval=500, repeat_delay=1000)

ani.save("Animation4.gif", writer='pillow') #Enregistrer en tant que fichier gif
HTML(ani.to_jshtml()) #Afficher sur HTML

Animation de recherche de priorité de largeur Animation4.gif

  • Si l'animation se termine et s'arrête, vous pouvez la déplacer à nouveau en cliquant sur l'image.

Recherche de la meilleure priorité et arborescence minimale

Enfin, la meilleure recherche prioritaire. Dans les deux premières recherches, nous avons ajouté une priorité pour les villes à courte distance lors de leur ajout à la pile (ou à la file d'attente). La recherche de la meilleure priorité trie la pile entière (en fait une file d'attente) après son ajout afin que les villes avec la distance la plus courte en soient de préférence extraites. Le résultat est un "arbre minimum".

Fonction pour réorganiser la pile

Le seul changement par rapport au passé est de trier à nouveau la pile entière.

def sort_stack(stack):
    return [stack[i] for i in np.argsort([dist_mat[edge[0]][edge[1]] for edge in stack])]

Meilleure animation de recherche de priorité

Le code ci-dessous est fondamentalement le même qu'avant. Les seuls changements sont l'ajout de la fonction sort_stack et le changement de nom du fichier qui enregistre la vidéo.

# -*- coding: UTF-8 -*-
import math
import matplotlib.pyplot as plt
import matplotlib.animation as animation
from IPython.display import HTML

fig = plt.figure(figsize=(10, 8))

stack = [[12, 12]] #Le point de départ est Tokyo
visited_towns = [] #Arrangement pour stocker les villes visitées
used_routes = [] #Un tableau qui stocke les routes réellement utilisées
current_direction = [] #Route en cours de vérification
ims = [] #Disposition pour stocker des images fixes
i = 0
while len(stack) > 0: #Si la pile n'est pas vide
    if i != 0: #La valeur initiale étant affichée la première fois, la recherche ne peut pas continuer.
        if stack[0] != []: #La recherche ne se poursuit pas même au dernier affichage
            stack = sort_stack(stack) #Trier les piles pour une recherche de la meilleure priorité
            current_direction = traverse() #Faites une étape de recherche
    image = [] #Un tableau qui stocke les parties à écrire dans une image fixe
    for edge in get_edges(stack): #La ligne rouge est la route «candidate» dans la pile
        image += plt.plot(edge[0], edge[1], 'r', alpha=0.5)

    for edge in get_edges(current_direction): #La ligne bleue est l'itinéraire en cours de vérification
        image += plt.plot(edge[0], edge[1], 'b', lw=5, alpha=0.5)

    for edge in get_edges(used_routes): #La ligne noire est un itinéraire utilisé
        image += plt.plot(edge[0], edge[1], 'k', lw=2)

    for city, x, y in zip(japan['Town'], japan['Latitude'], japan['Longitude']):
        image.append(plt.text(x, y, city, alpha=0.5, size=12)) #Afficher le nom de la ville

    if len(current_direction) > 0:
        current_town = current_direction[0][0]
        image += plt.plot(japan.iloc[current_town, :]['Latitude'], 
                          japan.iloc[current_town, :]['Longitude'], 
                          markersize=20, marker='o') #Maru est la ville en cours de vérification
    ims.append(image) #Stocker une image fixe
    
    if len(stack) == 0: #Pour le dernier affichage
        current_direction = []
        stack.append([])
    elif stack[0] == []: #Pour la dernière évasion
        break
    i += 1

#Convertir en vidéo
ani = animation.ArtistAnimation(fig, ims, interval=500, repeat_delay=1000)

ani.save("Animation5.gif", writer='pillow') #Enregistrer en tant que fichier gif
HTML(ani.to_jshtml()) #Afficher sur HTML

Meilleure animation de recherche de priorité Animation5.gif

  • Si l'animation se termine et s'arrête, vous pouvez la déplacer à nouveau en cliquant sur l'image.

Recommended Posts