NetworkXで経路探索をやってみる。（グラフへコスト追加〜探索した経路の可視化）

はじめに

前回、NetworkXでグラフの作成と、A*アルゴリズムによる経路探索をしました。

今回は、グラフにコストを追加して、経路探索してみます。
また、ノードとエッジに色をつけて、経路を可視化してみます

日常生活で、目的地への経路を考えるとき、近道 or 遠回り、混む道 or 空いている道などを考慮することもあります。
これらを、コストとして表現していきます。
通常、隣接するノード間の"距離"を、コストにすることが多いです。

今回のアウトプットは、下図です。

導出した経路を青色で塗りました。エッジ中央の数字がコストです。
コストのラベルに加え、各ノードの座標も描画しています。
見づらい気がしますが、ボスg...　重要な情報ですね。

コードを書いていく

Step0. 準備

Python 3.8.6、NetworkX 2.6.2を使います。まず、import。

import numpy as np
import matplotlib.pyplot as plt
import networkx as nx
import random

Step1. グラフを描画する関数を準備

見出しタイトルの通りです。

# 引数は、保存する画像名、グラフ、位置情報（ノード）、色情報（ノード）、色情報（エッジ）、ラベル情報（エッジ）
def draw_graph(pngname, G, pos, n_color, e_color, e_labels):
    nx.draw_networkx_nodes(G, pos, node_size=30, node_color=n_color)
    nx.draw_networkx_edges(G, pos, edge_color=e_color, width=1)
    nx.draw_networkx_labels(G, pos)
    nx.draw_networkx_edge_labels(G, pos, edge_labels=e_labels) #エッジへラベル追加
    plt.tick_params(left=True, bottom=True, labelleft=True, labelbottom=True)
    plt.savefig(pngname)
    plt.figure()

Step2. グラフの作成（コスト付）

ノードを格子状（n×m）に配置したグラフを作成します。
コストは、１〜１０の整数値をランダムに設定します。
慣れるために、１箇所だけ手動でコストを設定しました。

def make_graph(n, m):# 格子状(n×m)のグラフ作成
    G = nx.Graph()
    # n*mの頂点を追加する
    for i in range(n):
        for j in range(m):
            G.add_node((i,j))

    # 縦横(x、y軸)方向にエッジ追加
    for i in range(n):
        for j in range(m-1):
            if (i,j) in G and (i,j+1) in G:
                w = random.randint(1, 10)# コストは、乱数を設定する
                G.add_weighted_edges_from([((i,j), (i,j+1), w)]) # コスト付き
    for j in range(m):
        for i in range(n-1):
            if (i,j) in G and (i+1,j) in G:
                w = random.randint(1, 10)
                G.add_weighted_edges_from([((i,j), (i+1,j), w)])
                
    # 斜め方向にエッジ追加
    for j in range(m-1):
        for i in range(n-1):
            if (i,j) in G and (i+1,j+1) in G:
                w = random.randint(1, 10)
                G.add_weighted_edges_from([((i,j), (i+1,j+1), w)])

    # 1箇所だけ、コストを手動で変更してみる
    G.add_weighted_edges_from([((2,2), (3,3), 20)])# コスト上書き
    return G

Step3. A*アルゴリズムによる経路探索と、経路の可視化

導出した経路のノード、エッジを着色することで、可視化します。
A*アルゴリズムの概要は省略します。

def distance(a, b):# ヒューリスティック関数は、ユークリッド距離
    (x1, y1) = a
    (x2, y2) = b
    return ((x1-x2)**2+(y1-y2)**2)**0.5

def astar(Gp, n, m):# A*アルゴリズムで経路探索
    # スタート地点：（0, 0）、ゴール地点：（3, 3）
    path = nx.astar_path(Gp, source=(0,0), target=(n-1, m-1), heuristic=distance, weight='weight')
    path_length = nx.astar_path_length(Gp, source=(0,0), target=(n-1, m-1), heuristic=distance, weight='weight')
    print(path)# 導出した経路の確認
    print(path_length)# 導出した経路のコスト合計値

    # 導出した経路のノードを、青色で着色する
    node_color=['blue'if(i in path)==1 else '0.4'for i in Gp.nodes()]

    # 導出した経路の、エッジも着色する
    path_edge=[]
    for i in range(len(path)-1):# "path"は、A*で求めた経路の、ノードのリスト
        tup=(path[i], path[i+1])# エッジ両端のノードをタプルにして、リストに格納する
        path_edge.append(tup)
    edge_color = ['blue'if(j in path_edge)==1 else '0.4'for j in Gp.edges()]

    # グラフを描画する
    pos_1 = {n:(n[0], n[1]) for n in Gp.nodes()}
    edge_labels = {(i, j): w['weight'] for i, j, w in Gp.edges(data=True)}
    draw_graph('graph.png', Gp, pos_1, node_color, edge_color, edge_labels)

Step4. 実行

n=4; m=4 #今回は、4×4の格子状
astar(make_graph(n, m), n, m)

おわりに

コスト付グラフをA*アルゴリズムで経路探索して、経路のノード、エッジを着色して可視化しました。
「何をコストとして設定するか？」アイデア次第で、様々な場面で応用できそうです。
可視化結果も綺麗です。資料作成時、スライドツールでグラフを描く手間が省けました。