Google Colaboratory + cuGraphで最短経路探索を実装します．

GPUの確認

「Tesla T4, P4, or P100」であれば、OKです。

!nvidia-smi

condaのインストール

複雑なライブラリですので、いくつかの段階に分かれています。

環境の確認

下記のコードで、インストールできる環境か確認します。

!pip install pynvml
!git clone https://github.com/rapidsai/rapidsai-csp-utils.git
!python rapidsai-csp-utils/colab/env-check.py
# ***********************************************************************
# Woo! Your instance has the right kind of GPU, a Tesla T4!
# ***********************************************************************

gccのアップデート

下記のコードで、gccをアップデートします。

ただし、実行後にセッションをクラッシュさせますので、次のセルはまだ実行しないでください。

!bash rapidsai-csp-utils/colab/update_gcc.sh
import os
os._exit(00)
# ***********************************************************************
# Woo! Your instance has the right kind of GPU, a Tesla T4!
# ***********************************************************************

インストールの実行

下記のコードで、condaをインストールします。

ただし、実行後にセッションを再起動させますので、次のセルはまだ実行しないでください。

import condacolab
condacolab.install()
#  Restarting kernel...

下記のコードで、condaを確認します。

# condaの確認
import condacolab
condacolab.check()
# Everything looks OK!

cuGraphのインストール

下記のコードで、cuGraphなどのインストールを実行します。

ただし、20分以上かかります。

!python rapidsai-csp-utils/colab/install_rapids.py stable
import os
os.environ['NUMBAPRO_NVVM'] = '/usr/local/cuda/nvvm/lib64/libnvvm.so'
os.environ['NUMBAPRO_LIBDEVICE'] = '/usr/local/cuda/nvvm/libdevice/'
os.environ['CONDA_PREFIX'] = '/usr/local'
# 追記(2022/7/13)
!pip install cffi==1.15.1

最短経路探索

データの用意

!!git clone https://github.com/python3f/cugraph-learn.git

ネットワークの描画

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

# データの読み込み
csv = 'cugraph-learn/data/min2d.csv'
data = cudf.read_csv(csv, names=['src', 'dst', 'wt'], dtype=['int32', 'int32', 'float32'])

# 12個の頂点と、ランダムに引いた辺を持つグラフを定義
G = nx.Graph()
G.add_nodes_from(list(set(data["src"].values.tolist())))
for i in range(len(G.nodes)):
  G.add_edge(data["src"][i], data["dst"][i])

# 座標を指定せずに描写する
nx.draw_networkx(G, node_color="c")
plt.show()

!(/image/min2d.png)

最短経路探索

# START
import time
import cudf
import cupy
import cugraph

csv = 'cugraph-learn/data/min2d.csv'
data = cudf.read_csv(csv, names=['source', 'destination', 'weight'], dtype=['int32', 'int32', 'float32'])

G = cugraph.Graph()
G.from_cudf_edgelist(data, source='source', destination='destination', edge_attr='weight')

# ODノード
org = 3
dest = 5

start = time.time()
# 最短経路探索
dist = cugraph.sssp(G, org)
path = [des
while dest != -1:
   dest = int(dist[dist['vertex']==des['predecessor'].values[0])
   path.append(dest)

# reverse the list and print
print(path[::-1][1:])

elapsed_time = time.time() - start
print ("elapsed_time:{0}".format(elapsed_time) + "[se")
# [3, 2, 1, 5]
# [create_linkvol] elapsed_time:0.034224510192871094[se

まとめ

Google Colaboratory + cuGraphで最短経路探索を実装しました．

参考サイト

rapidsai/cugraph
rapidsai-community/rapidsai-csp-utils
python3f/cugraph-learn.ipynb
rapids-colab.ipynb - Colaboratory
NVIDIAのRAPIDSでcuML, cuDF, cuGraphを試してみる
[cugraph.Graph.from_cudf_edgelis(https://docs.rapids.ai/api/cugraph/stable/api_docs/api/cugraph.Graph.from_cudf_edgelist.html)
cugraph.sssp
Graph Algorithms on Steroids for data Scientists with cuGraph
NetworkXのグラフを可視化するときに頂点の座標を指定する
cuGraph でページランクを計算したら爆速だった