def neighbor(town, dist_mat=dist_mat, threshold=1): #Function to get an adjacency list 1
    return [x[0] for x in enumerate(np.where(dist_mat[town] <= threshold, True, False)) if x[1]]

The usage example looks like this.

neighbor(12) #Which cities are within 1 distance from Tokyo?

[7, 8, 9, 10, 11, 12, 13]

Graph search function 1

In Basics of Graph Theory, the while statement was used to solve the graph search problem, but here, I want to show the progress step by step. I defined the function to advance one step of the search as follows.

def traverse(i=0): #One step of depth-first search
    if len(stack) != 0: #If the stack is not empty
        next_town, current_town = stack.pop() #Get the next route (current location and next city)
        current_direction = [[next_town, current_town]] #For drawing
        if next_town not in visited_towns: #If the next city has not been visited
            used_routes.append([next_town, current_town]) #Register the route
            visited_towns.append(next_town) #Make it visited
            for nei in neighbor(next_town): #Take out the cities adjacent to the visited city one by one
                if nei not in visited_towns: #If you haven't visited
                    stack.append([nei, next_town]) #Put the route on the stack
    return current_direction #For drawing

Depth-first search animation 1

Now let's animate it.

# -*- 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]] #The starting point is Tokyo
visited_towns = [] #An array that stores visited cities
used_routes = [] #An array that stores the routes actually used
current_direction = [] #Route currently being checked
ims = [] #Array for storing still images
i = 0
while len(stack) > 0: #If the stack is not empty
    if i != 0: #Since the initial value is displayed the first time, the search cannot proceed.
        current_direction = traverse() #Take the search one step
    image = [] #An array that stores parts to be written in one still image
    for edge in get_edges(stack): #The red line is the "candidate" route in the stack
        image += plt.plot(edge[0], edge[1], 'r', alpha=0.5)

    for edge in get_edges(current_direction): #The blue line is the route currently being checked
        image += plt.plot(edge[0], edge[1], 'b', lw=5, alpha=0.5)

    for edge in get_edges(used_routes): #Black line is used route
        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)) #Show city name

    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 is the city currently being checked
    ims.append(image) #Store one still image
    i += 1

#Convert to video
ani = animation.ArtistAnimation(fig, ims, interval=500, repeat_delay=1000)

ani.save("Animation2.gif", writer='pillow') #Save as gif file
HTML(ani.to_jshtml()) #Display on HTML

Depth-first search animation 1

• If the animation ends and stops, you can move it again by clicking the image.

Function 2 to get an adjacency list

In the depth-first search above, "the last city on the stack" is the next destination candidate. When you move to a city, the cities adjacent to it are put on the stack. At this time, the behavior changes even with the same depth-first search by considering the order in which they are put on the stack. Let's modify it so that cities that are close to each other are preferentially selected as destination candidates.

import numpy as np
def neighbor(town, dist_mat=dist_mat, threshold=1): #Function 2 to get an adjacency list
    return np.argsort(dist_mat[town])[1:np.where(dist_mat[town] <= threshold, 1, 0).sum()][::-1]

Depth-first search animation 2

The code below is the same as "Depth-first search animation 1" (only the file name of the saved video is different). Let's see how changing the function neighbor changes its behavior.

# -*- 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]] #The starting point is Tokyo
visited_towns = [] #An array that stores visited cities
used_routes = [] #An array that stores the routes actually used
current_direction = [] #Route currently being checked
ims = [] #Array for storing still images
i = 0
while len(stack) > 0: #If the stack is not empty
    if i != 0: #Since the initial value is displayed the first time, the search cannot proceed.
        if stack[0] != []: #The search cannot proceed even at the last display
            current_direction = traverse() #Take the search one step
    image = [] #An array that stores parts to be written in one still image
    for edge in get_edges(stack): #The red line is the "candidate" route in the stack
        image += plt.plot(edge[0], edge[1], 'r', alpha=0.5)

    for edge in get_edges(current_direction): #The blue line is the route currently being checked
        image += plt.plot(edge[0], edge[1], 'b', lw=5, alpha=0.5)

    for edge in get_edges(used_routes): #Black line is used route
        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)) #Show city name

    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 is the city currently being checked
    ims.append(image) #Store one still image
    
    if len(stack) == 0: #For the last display
        current_direction = []
        stack.append([])
    elif stack[0] == []: #For the last escape
        break
    i += 1

#Convert to video
ani = animation.ArtistAnimation(fig, ims, interval=500, repeat_delay=1000)

ani.save("Animation3.gif", writer='pillow') #Save as gif file
HTML(ani.to_jshtml()) #Display on HTML

Depth-first search animation 2

• If the animation ends and stops, you can move it again by clicking the image.

Breadth-first search

Next, let's do a breadth-first search. The basic algorithm is almost the same, just put the stack (first in, last out) into a queue (queue: first in, first out).

Graph search function 2

Rewrite the function traverse. The part to be rewritten is only one point shown as "change". Since the list used as a stack changes to a queue, I would like to change the variable name stack, but doing so will increase the part to be rewritten, so let's leave stack as it is.

def traverse(i=0): #One step of breadth-first search
    if len(stack) != 0:
        next_town, current_town = stack.pop(0) #change point
        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

Function to get an adjacency list 3

The function to get the adjacency list is also rewritten, but it is basically the same as the previous one. The stack is queued, so you just flip the order.

import numpy as np
def neighbor(town, dist_mat=dist_mat, threshold=1): #Function to get an adjacency list 3
    return np.argsort(dist_mat[town])[1:np.where(dist_mat[town] <= threshold, 1, 0).sum()] #Change only the end

Breadth-first search animation

The following code is also the same as "Depth-first search animation 1" and "Depth-first search animation 2" (only the file name of the saved video is different). Let's see how changing the function traverse changes its behavior.

# -*- 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]] #The starting point is Tokyo
visited_towns = [] #An array that stores visited cities
used_routes = [] #An array that stores the routes actually used
current_direction = [] #Route currently being checked
ims = [] #Array for storing still images
i = 0
while len(stack) > 0: #If the stack is not empty
    if i != 0: #Since the initial value is displayed the first time, the search cannot proceed.
        if stack[0] != []: #The search cannot proceed even at the last display
            current_direction = traverse() #Take the search one step
    image = [] #An array that stores parts to be written in one still image
    for edge in get_edges(stack): #The red line is the "candidate" route in the stack
        image += plt.plot(edge[0], edge[1], 'r', alpha=0.5)

    for edge in get_edges(current_direction): #The blue line is the route currently being checked
        image += plt.plot(edge[0], edge[1], 'b', lw=5, alpha=0.5)

    for edge in get_edges(used_routes): #Black line is used route
        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)) #Show city name

    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 is the city currently being checked
    ims.append(image) #Store one still image
    
    if len(stack) == 0: #For the last display
        current_direction = []
        stack.append([])
    elif stack[0] == []: #For the last escape
        break
    i += 1

#Convert to video
ani = animation.ArtistAnimation(fig, ims, interval=500, repeat_delay=1000)

ani.save("Animation4.gif", writer='pillow') #Save as gif file
HTML(ani.to_jshtml()) #Display on HTML

Breadth-first search animation

• If the animation ends and stops, you can move it again by clicking the image.

Best-first search and minimum tree

Finally, best-first search. In the top two searches, we've added short-distance cities to be preferentially retrieved when adding to the stack (or queue). Best-first search sorts the entire stack (actually a queue) after it has been added, giving priority to the cities with the shortest distance. The result is a "minimum tree".

Function to rearrange the stack

The only change from the past is to re-sort the entire stack.

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

Best-first search animation

The code below is basically the same as before. The only changes are the addition of the function sort_stack and the rename of the file that saves the video.

# -*- 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]] #The starting point is Tokyo
visited_towns = [] #An array that stores visited cities
used_routes = [] #An array that stores the routes actually used
current_direction = [] #Route currently being checked
ims = [] #Array for storing still images
i = 0
while len(stack) > 0: #If the stack is not empty
    if i != 0: #Since the initial value is displayed the first time, the search cannot proceed.
        if stack[0] != []: #The search cannot proceed even at the last display
            stack = sort_stack(stack) #Sort stack for best-first search
            current_direction = traverse() #Take the search one step
    image = [] #An array that stores parts to be written in one still image
    for edge in get_edges(stack): #The red line is the "candidate" route in the stack
        image += plt.plot(edge[0], edge[1], 'r', alpha=0.5)

    for edge in get_edges(current_direction): #The blue line is the route currently being checked
        image += plt.plot(edge[0], edge[1], 'b', lw=5, alpha=0.5)

    for edge in get_edges(used_routes): #Black line is used route
        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)) #Show city name

    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 is the city currently being checked
    ims.append(image) #Store one still image
    
    if len(stack) == 0: #For the last display
        current_direction = []
        stack.append([])
    elif stack[0] == []: #For the last escape
        break
    i += 1

#Convert to video
ani = animation.ArtistAnimation(fig, ims, interval=500, repeat_delay=1000)

ani.save("Animation5.gif", writer='pillow') #Save as gif file
HTML(ani.to_jshtml()) #Display on HTML

Best-first search animation

• If the animation ends and stops, you can move it again by clicking the image.