今回は1億年くらいかかりそうな問題を
高速に解く事ができるライブラリ
graphillion についてです。

解説動画はこちら




graphillion


この頂点をノード
線のことをエッジと呼んでいます。

これを応用した問題についてですが
1をスタート
81をゴールとした際に
二回同じところは通らないとして
行くことの出来るルートは何通りあるでしょうか



これを手計算で特にはかなりしんどいですよね。
このような膨大な数になるグラフを高速に解く事ができるのが
graphillionです。


元ネタ

一応こちらの元ネタは
下記のYouTube動画です。


この動画内では
先ほどの問題は4時間くらいかかっていたそうです。

それ以上のサイズになると計算量が膨大になるので
1億年以上掛かっても解ききれない
ということになっています。

組み合わせ数が爆発した際の
恐ろしさを感じさせる動画ですね。



graphillionのインストール

google colabでは下記コマンド実行のみです。

!pip install graphillion

graphillionの使い方


まずは必要なライブラリをインポートします。
グラフの描画に必要なものも合わせてインポートします。

# 必要なモジュールのインポート
from graphillion import GraphSet
import graphillion.tutorial as tl
import matplotlib.pyplot as plt
import networkx as nx
import random

グリッド表示をさせてみる

# N x M のサイズのグリッド表示
def draw_with_matplotlib(edges, n, m, figsize=(4, 3)):
    G = nx.Graph()
    G.add_edges_from(edges)
    pos,node_labels = {},{}
    for i in range(n):
        for j in range(m):
            node = i * m + j + 1
            pos[node] = (j, -i)
            node_labels[node] = str(node)

    plt.figure(figsize=figsize)
    nx.draw(G, pos, labels=node_labels, with_labels=True, node_size=200, node_color='lightblue', edge_color='gray')
    plt.show()

# サイズを指定
n, m = 2,2
universe = tl.grid(n, m)
GraphSet.set_universe(universe)
draw_with_matplotlib(universe, n + 1, m + 1)

glidメソッドで辺の数を指定します(頂点の数-1)

単純にパス(道順の総数)を計算する場合は
スタートの頂点の数値と
ゴールの頂点の数値を指定して
GraphSet.paths(start, goal)
で計算できます。

universe = tl.grid(2, 2)
GraphSet.set_universe(universe)
start, goal = 1, 9
paths = GraphSet.paths(start, goal)
print(f"パスの数 : {len(paths)}")

12


頂点が3x3の場合は
12通りである事がわかります。

この12通りを全通り描画してみましょう。

from graphillion import GraphSet
import graphillion.tutorial as tl
import matplotlib.pyplot as plt
import networkx as nx

def make_grid(n):
    edges = []
    for i in range(n):
        for j in range(n):
            if i < n - 1:
                edges.append((i * n + j + 1, (i + 1) * n + j + 1))
            if j < n - 1:
                edges.append((i * n + j + 1, i * n + (j + 1) + 1))
    return edges

def grid_paths(n):
    universe = make_grid(n)
    GraphSet.set_universe(universe)
    start = 1
    goal = n * n
    paths = GraphSet.paths(start, goal)
    return paths

def draw_paths_in_grid(paths, n):
    num_paths = len(paths)
    rows = 3
    cols = 4
    fig, axes = plt.subplots(rows, cols, figsize=(10, 6))
    G = nx.grid_2d_graph(n, n)
    pos = {(i, j): (j, n - 1 - i) for i in range(n) for j in range(n)}

    for i, path in enumerate(paths):
        row = i // cols
        col = i % cols
        ax = axes[row, col]
        path_edges = [(divmod(u - 1, n), divmod(v - 1, n)) for u, v in path]

        nx.draw(G, pos, with_labels=False, node_size=300, node_color='lightblue', edge_color='lightgray', ax=ax)
        nx.draw_networkx_edges(G, pos, edgelist=path_edges, edge_color='red', width=2, ax=ax)
        ax.set_title(f'Path {i + 1}')
        ax.set_xticks([])
        ax.set_yticks([])

    for j in range(i + 1, rows * cols):
        fig.delaxes(axes.flatten()[j])

    plt.tight_layout()
    plt.show()

n = 3
paths = grid_paths(n)
draw_paths_in_grid(paths, n)

頂点4を通ってから頂点2を通る道順を出す
というようなこともできます。

# 何通りあるか
start = 1
goal = 9
key = 4
treasure = 2

paths = GraphSet.paths(start, goal)
paths_to_key = GraphSet.paths(start, key).excluding(treasure)
treasure_paths = paths.including(paths_to_key).including(treasure)
len(treasure_paths)

2

# 道順リストの描画
from graphillion import GraphSet
import graphillion.tutorial as tl
import matplotlib.pyplot as plt
import networkx as nx

def draw_paths_in_grid(paths, n):
    num_paths = len(paths)
    rows = 1
    cols = 2
    fig, axes = plt.subplots(rows, cols, figsize=(10, 6))
    G = nx.grid_2d_graph(n, n)
    pos = {(i, j): (j, n - 1 - i) for i in range(n) for j in range(n)}

    for i, path in enumerate(paths):
        row, col = divmod(i, cols)
        ax = axes[col] if rows == 1 else axes[row, col]
        path_edges = [(divmod(u - 1, n), divmod(v - 1, n)) for u, v in path]

        nx.draw(G, pos, with_labels=False, node_size=300, node_color='lightblue', edge_color='lightgray', ax=ax)
        nx.draw_networkx_edges(G, pos, edgelist=path_edges, edge_color='red', width=2, ax=ax)
        ax.set_title(f'Path {i + 1}')
        ax.set_xticks([])
        ax.set_yticks([])

    for j in range(i + 1, rows * cols):
        fig.delaxes(axes.flatten()[j])

    plt.tight_layout()
    plt.show()


n, m = 2, 2
universe = tl.grid(n, m)
GraphSet.set_universe(universe)

start = 1
goal = 9
key = 4
treasure = 2

paths = GraphSet.paths(start, goal)
paths_to_key = GraphSet.paths(start, key).excluding(treasure)
treasure_paths = paths.including(paths_to_key).including(treasure)
draw_paths_in_grid(treasure_paths,n+1)

それでは冒頭の

import time
universe = tl.grid(8, 8)
GraphSet.set_universe(universe)
start, goal = 1, 81
s_time = time.time()
paths = GraphSet.paths(start, goal)
times = time.time() - start
print(f"計算時間 : {times}")
print(f"パスのサイズ : {len(paths):,}")

計算時間 : 1723880338.8543057
パスのサイズ : 3,266,598,486,981,642

約3200兆通りです

1つ選んでみるとこんな結果でした。



まとめ