Graph Analytics with Python -Graph Search-
Tags: python, datascience, graph, networkx
Published: 2021-01-19 06:11:47

<!--グラフ上で最短経路を見つけるという試みは，現実において鉄道網や配送ルートの考案において応用されている．ネットワーク$G=(V,E)$と二つの頂点$v_s$と$v_t$が与えられているとし，この際に$v_s$から$v_t$への経路を探索することを考える．-->
The attempt to find the shortest path on a graph has been applied in real life in devising railroad networks and delivery routes. Given a network $G=(V,E)$ and two vertices $v_s$ and $v_t$, we want to find a path from $v_s$ to $v_t$.

# Breadth Firtst Search and Depth First Search

<!--まずは幅優先探索(BFS)による探索を行う．BFSは，$v_s$に隣接する距離1の頂点をすべて探し，次に距離2の全ての頂点，そして距離3の全ての頂点という順で探していく手法である．ここで，Networkxに用意されているZachary's karate clubというグラフモデルを使用する．-->
We start with a breadth-first search (BFS), which searches for all vertices adjacent to $v_s$ at distance 1, then all vertices at distance 2, and then all vertices at distance 3, in that order. We use a graph model called Zachary's karate club, which is available in Networkx.

<!--なお空手とは日本の武道であり，日本で人気アニメの名探偵コナンにおける蘭姉ちゃんは空手の全国大会チャンピオンである．-->
Karate is a Japanese martial art, and the sister of Ran in the popular Japanese anime Detective Conan is a national karate champion.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/r7qykefxsqdjzb369gwa.jpg)

<!--Networkxの関数であるbfs_edgesでは，引数として対象ネットワーク，探索開始点，探索の深さの上限を与える．上限がnの場合に探索した辺とn-1の場合に探索した辺の差を求めることで，距離nの頂点につながる辺だけを得ることができる．深さ4でリストの中身が空になるため，このネットワークの頂点0からは距離3まで他のすべての頂点に到達できることがわかる．-->
In bfs_edges, a function of Networkx, we give the target network, the starting point of the search, and an upper limit on the depth of the search. By computing the difference between the edges searched when the upper limit is n and the edges searched when the upper limit is n-1, we can obtain only the edges that lead to vertices with distance n. Since the list is empty at depth 4, we know that from vertex 0 of this network, we can reach all other vertices up to distance 3.

```Python
G = nx.karate_club_graph()
plt.figure(figsize=(5,5))
nx.draw_spring(G, node_size=400, node_color="#00C98D", with_labels=True, font_weight="bold")
print("BFS", list(nx.bfs_edges(G, source=0)))

# Depth = 1
d1 = list(nx.bfs_edges(G, source=0, depth_limit=1))
print("depth 1:", d1)

# Depth = 2
d2 = list(nx.bfs_edges(G, source=0, depth_limit=2))
print("depth 2:", list(set(d2) - set(d1)))

# Depth = 3
d3 = list(nx.bfs_edges(G, source=0, depth_limit=3))
print("depth 3:", list(set(d3) - set(d2)))

# Depth = 4
d4 = list(nx.bfs_edges(G, source=0, depth_limit=4))
print("depth 4:", list(set(d4) - set(d3)))
```

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/dy186rcf5zsqr2jow2um.png)

```
BFS [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (0, 10), (0, 11), (0, 12), (0, 13), (0, 17), (0, 19), (0, 21), (0, 31), (1, 30), (2, 9), (2, 27), (2, 28), (2, 32), (5, 16), (8, 33), (31, 24), (31, 25), (27, 23), (32, 14), (32, 15), (32, 18), (32, 20), (32, 22), (32, 29), (33, 26)]
depth 1: [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (0, 10), (0, 11), (0, 12), (0, 13), (0, 17), (0, 19), (0, 21), (0, 31)]
depth 2: [(1, 30), (2, 28), (2, 9), (5, 16), (8, 33), (2, 32), (31, 24), (31, 25), (2, 27)]
depth 3: [(27, 23), (32, 22), (32, 15), (32, 20), (33, 26), (32, 14), (32, 18), (32, 29)]
depth 4: []
```

<!--続いてDepth First Search(DFS)である．これは頂点V_sに隣接する距離1 の頂点を一つ選び，それに隣接する距離2の頂点のなかからまだ訪れていない頂点を一つ選びという順で探索する手法である．-->
Next is Depth First Search (DFS). This is a search method that selects one vertex at distance 1 adjacent to vertex V_s, then selects one vertex at distance 2 adjacent to it that has not yet been visited, and so on.

```Python
print("DFS:", list(nx.dfs_edges(G, source=0)))
print("traversed nodes:", list(nx.dfs_preorder_nodes(G, source=0)))
```

<!--頂点0から深さ優先探索を実施した際に通る辺のリストと，訪れた頂点のリストを示しており，それぞれdfs_edgesとdfs_preorder_nodesによって計算している．頂点0から1,2,3,7と探索してそこでバックトラックしてから頂点3から12,13と探索していることがわかる．-->
It shows the list of edges and the list of vertices visited during the depth-first search from vertex 0, computed by dfs_edges and dfs_preorder_nodes, respectively. We can see that from vertex 0, we search 1, 2, 3, 7, backtrack there, and then search 12, 13 from vertex 3.

```
DFS: [(0, 1), (1, 2), (2, 3), (3, 7), (3, 12), (3, 13), (13, 33), (33, 8), (8, 30), (30, 32), (32, 14), (32, 15), (32, 18), (32, 20), (32, 22), (32, 23), (23, 25), (25, 24), (24, 27), (24, 31), (31, 28), (23, 29), (29, 26), (33, 9), (33, 19), (1, 17), (1, 21), (0, 4), (4, 6), (6, 5), (5, 10), (5, 16), (0, 11)]
traversed nodes: [0, 1, 2, 3, 7, 12, 13, 33, 8, 30, 32, 14, 15, 18, 20, 22, 23, 25, 24, 27, 31, 28, 29, 26, 9, 19, 17, 21, 4, 6, 5, 10, 16, 11]
```

<!--幅優先探索と深さ優先探索の比較をしたのが以下の図である．-->

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/1fdmdojplweft8pd9v7o.png)

#Dijkstra's Algorithm

<!--全ての辺のコストが同じであれば幅優先探索や深さ優先探索でよいが，辺の距離が異なる場合もある．そのような場合に有効な探索として，ダイクストラのアルゴリズムがある．ダイクストラのアルゴリズムは，グラフと開始頂点が与えられたときに各頂点への最短経路長を求めるアルゴリズムである．-->
If the cost of all edges is the same, width-first search or depth-first search can be used, but there are cases where the distances between edges are different. In such a case, Dijkstra's algorithm is an effective search method. Dijkstra's algorithm is an algorithm to find the shortest path length to each vertex, given a graph and a starting vertex.

```Python
#Define Graph
G = nx.Graph()
G.add_nodes_from(range(0, 5))
G.add_weighted_edges_from([(0, 1, 7), (0, 2, 9), (0, 5, 14), (1, 2, 10), (1, 3, 15), (2, 3, 11), (2, 5, 2), (3, 4, 6), (4, 5, 9)])

plt.figure(figsize=(5, 5))
pos = nx.spring_layout(G)
nx.draw_networkx_edges(G, pos)
nx.draw_networkx_nodes(G, pos)
nx.draw_networkx_edge_labels(G, pos, font_size=16, edge_labels={(u, v): d["weight"] for u, v, d in G.edges(data=True)})
nx.draw_networkx_labels(G, pos)
plt.axis("off")
plt.show()
```

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/daurfmujypjcy59vuyaw.png)

```Python
dist_estimate = [999] * nx.number_of_nodes(G)
dist_certainty = [0] * nx.number_of_nodes(G)
dist_estimate[1] = 0

while functools.reduce(operator.mul, dist_certainty) == 0:
  print("Estimation: ", dist_estimate)
  print("Certaintly: ", dist_certainty)
  min_v = 999
  for n in nx.nodes(G):
    if (dist_certainty[n] ==0) and (dist_estimate[n] <= min_v):
      min_v = dist_estimate[n]
      min_id = n
    dist_certainty[min_id] = 1
    for nb in G.neighbors(min_id):
      new_estimate = G[min_id][nb]["weight"] + dist_estimate[min_id]
      if new_estimate < dist_estimate[nb]:
        dist_estimate[nb] = new_estimate
        print("Estimation: ", dist_estimate)
        print("Certaintly: ", dist_certainty)
```

<!--初期状態では最短経路長の見積もりは非常に大きな整数であり，その確かさは0である．経路長の見積もりの配列のなかで最短のものを確かな見積もりとみなして，その頂点を経由して隣接する頂点に至る経路の距離を計算している．そして，それがこれまでの最短経路長の見積もりよりも短ければその見積もりを更新するという処理を繰り返す．-->
Initially, the shortest path length estimates are very large integers, and their certainty is zero. The shortest path in the array of path length estimates is considered as a reliable estimate, and the distance of the path through that vertex to the neighboring vertex is calculated. If it is shorter than the previous estimate of the shortest path length, the process is repeated to update the estimate.

```
Estimation:  [999, 0, 999, 999, 999, 999]
Certaintly:  [0, 0, 0, 0, 0, 0]
Estimation:  [7, 0, 999, 999, 999, 999]
Certaintly:  [1, 1, 0, 0, 0, 0]
Estimation:  [7, 0, 10, 999, 999, 999]
Certaintly:  [1, 1, 0, 0, 0, 0]
Estimation:  [7, 0, 10, 15, 999, 999]
Certaintly:  [1, 1, 0, 0, 0, 0]
Estimation:  [7, 0, 10, 15, 999, 999]
Certaintly:  [1, 1, 0, 0, 0, 0]
Estimation:  [7, 0, 10, 15, 999, 12]
Certaintly:  [1, 1, 1, 0, 0, 0]
Estimation:  [7, 0, 10, 15, 999, 12]
Certaintly:  [1, 1, 1, 0, 0, 0]
Estimation:  [7, 0, 10, 15, 21, 12]
Certaintly:  [1, 1, 1, 1, 0, 0]
Estimation:  [7, 0, 10, 15, 21, 12]
Certaintly:  [1, 1, 1, 1, 0, 1]
```

# Conclusion

<!--この記事では，グラフにおける主な探索法として，幅優先探索と深さ優先探索，そしてダイクストラのアルゴリズムについて説明を行った．他にもグラフにおける探索法はあるので，下記リンクを参考に実装してみると良い．-->
In this article, I explained the main search methods for graphs: breadth-first search, depth-first search, and Dijkstra's algorithm. There are other search methods for graphs, so please refer to the following links and try to implement them.

[Graph Data Structure](https://www.programiz.com/dsa/graph)