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

# はじめに
[前回、NetworkXでグラフの作成と、A*アルゴリズムによる経路探索をしました。](https://qiita.com/tentsukup_channel/items/dbbf3581cb40e44610e4)

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

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

今回のアウトプットは、下図です。
![astar_bunseki２.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1902761/ce5c4806-22e5-ce33-4927-7c12b7cf8bb1.png)
導出した経路を青色で塗りました。エッジ中央の数字がコストです。
コストのラベルに加え、各ノードの座標も描画しています。
~~見づらい気がしますが、ボスg...~~　重要な情報ですね。

# コードを書いていく
## Step0. 準備
Python 3.8.6、NetworkX 2.6.2を使います。まず、import。

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

## Step1. グラフを描画する関数を準備
見出しタイトルの通りです。

~~~python
# 引数は、保存する画像名、グラフ、位置情報（ノード）、色情報（ノード）、色情報（エッジ）、ラベル情報（エッジ）
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）に配置したグラフを作成します。
コストは、１〜１０の整数値をランダムに設定します。
慣れるために、１箇所だけ手動でコストを設定しました。

~~~python
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*アルゴリズムの概要は省略します。

~~~python
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. 実行
~~~python
n=4; m=4 #今回は、4×4の格子状
astar(make_graph(n, m), n, m)
~~~

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