ポイント
- Pythonを用いて、パスグラフの直積を計算することにより、グリッドグラフを生成します
グリッドグラフ
大きさ$s_0\times s_1\times \cdots\times s_{d-1}$のグリッドグラフ$G([s_1,s_2,\ldots, s_{d-1}])$は次のように定義されます：
- 頂点集合: $\lbrace(i_0, i_1, \ldots, i_{d-1}) | 0\leq i_j \leq s_{j}-1 (0\leq j\leq d-1) \rbrace$ ．つまり，頂点は大きさ$s_0\times s_1\times \cdots\times s_{d-1}$の$d$次元空間上のグリッド点です．
- 辺集合： $\lbrace((i_0, \ldots, i_{d-1}),(i_0,\ldots, i_{k-1}, i_k+1, i_{k+1}, \ldots, i_{d-1})) | 0\leq k\leq d-1 \rbrace$． これは，隣接するグリッド点同士を辺で接続したものです．
ここで，$s_j$ は $j$ 番目の次元の大きさを表し，各頂点 $(i_0, i_1, \ldots, i_{d-1})$ は $d$ 次元空間内のグリッド点を表します．辺は、ある点からその点の任意の次元において1だけ離れた隣接点への接続を表します。
下は，大きさ$3\times 4\times 2$のグリッドグラフ$G([3,4,2])$を図示したものです．
グリッドグラフの求め方
グリッドグラフは，パスグラフの直積を繰り返し計算することによって生成することができます．
グラフの直積
2つのグラフ$G=(V_G,E_G)とH(V_H,E_H)$の直積$G\times H=(V_{G\times H}, E_{G\times H})$は，以下のように定義されます：
- 頂点集合： $V_{G\times H} = \lbrace (u,v) | u\in V_G, v\in V_H\rbrace$．これはグラフ$G$と$H$の頂点のすべての組み合わせです．
- 辺集合： $E_{G\times H}=\lbrace ((u,u'), (v,v')) | (u=v \text{かつ} (v,v') \in E_H)) \text{または} (u'=v' \text{かつ} (u,u') \in E_G) \rbrace$
$G$の頂点を$V_G=\lbrace 0, 1, \ldots, m-1\rbrace$，$H$の頂点を$V_H=\lbrace 0, 1, \ldots, n-1\rbrace$とすると，$G\times H$の頂点は，縦$m$$\times$横$n$のグリッドの格子点$(i,j)$ $(0\leq i\leq m-1, 0\leq j\leq n-1)$とみなすことができます．そして，縦方向，つまり各列は$E_G$による接続で，横方向，つまり各行は$E_H$による接続が行われます．
パスグラフ
大きさ $n$ のパスグラフは，$n$ 個の頂点が一列に並んでおり，隣接する頂点同士が接続されたものです．これは，大きさ $n$ の1次元グリッドグラフ $G([n])$ と一致します．
大きさ4のパスグラフ$P_4$
パスグラフの直積を取ることで，2次元グリッドグラフを生成することが可能です．例えば，大きさ3のパスグラフ $P_3$ と大きさ4のパスグラフ $P_4$ の直積，すなわち $P_3 \times P_4$ は，大きさ $3 \times 4$ のグリッドグラフ $G([3,4])$ に対応します．
さらに，$P_2$ との直積を取ることで，グラフ $P_3 \times P_4 \times P_2$ を得ることができます．これは，先に例示した大きさ $3 \times 4 \times 2$ のグリッドグラフ $G([3,4,2])$ に相当します．
一般に，パスグラフの直積 $P_{s_0} \times P_{s_1} \times \ldots \times P_{s_{d-1}}$ を計算することにより，任意の次元のグリッドグラフ $G([s_0, s_1, \ldots, s_{d-1}])$ を構築することが可能です．
Pythonプログラム
NetworkXライブラリのnx.grid_graph関数を用いれば，簡単にグリッドグラフを生成できます．しかし，ここではパスグラフの直積を使用してグリッドグラフを生成する方法に焦点を当てます．
関数path_graphs(dim)は，大きさのリスト$[s_0, s_1, \ldots, s_{d-1}]$を引数dimとして受け取り，大きさ$s_0, s_1, \ldots, s_{d-1}$の$d$個のパスグラフをリストとして返します．
関数cartesian_products(graphs)は，グラフのリストを引数graphsで受け取り，その直積nx.cartesian_productを用いて計算して返します．この関数は再帰的に処理を行い，graphsに1つのグラフのみ含まれている場合は，そのグラフをそのまま返します．2つ以上のグラフが含まれる場合には，末尾のグラフを除外したリストの直積を再帰的に計算し，その結果と末尾のグラフの直積を計算して返します．
nx.cartesian_productは2つのグラフの各頂点をタプルとして組み合わせるため，cartesian_products関数から得られるグラフの頂点はタプルの入れ子構造，例えば$((2,0),1)$のようになります．関数flatten_graph(G)は，このようにタプルの入れ子になっているグラフGの頂点をフラットにし，例えば$(2,0,1)$のような形式にします。
G = nx.grid_graph([2, 4, 3])はコメントアウトされていますが，この行を有効にすることで、目指す同じ結果を得ることができます．ただし，完全に同一のグラフを得るには，大きさの順序を逆にする必要があります．
import networkx as nx
import matplotlib.pyplot as plt
def path_graphs(dim):
return [nx.path_graph(s) for s in dim]
def cartesian_products(graphs):
if len(graphs) == 1:
return graphs[0]
else:
return nx.cartesian_product(cartesian_products(graphs[:-1]), graphs[-1])
def flatten_graph(G):
def flatten_tuple(t):
for item in t:
if isinstance(item, tuple):
yield from flatten_tuple(item)
else:
yield item
flatten_G = nx.Graph()
flatten_G.add_edges_from(
[(tuple(flatten_tuple(u)), tuple(flatten_tuple(v))) for u, v in G.edges]
)
return flatten_G
def main():
# G = nx.grid_graph((2, 4, 3))
G = flatten_graph(cartesian_products(path_graphs([3, 4, 2])))
print(sorted(G.nodes))
print(sorted(G.edges))
nx.draw(G, with_labels=True)
plt.savefig("graph.png")
if __name__ == "__main__":
main()
#実行結果
大きさ$3\times 4\times 2$のグリッドグラフの頂点と辺が正しく得られています．
[(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (0, 2, 0), (0, 2, 1), (0, 3, 0), (0, 3, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1), (1, 2, 0), (1, 2, 1), (1, 3, 0), (1, 3, 1), (2, 0, 0), (2, 0, 1), (2, 1, 0), (2, 1, 1), (2, 2, 0), (2, 2, 1), (2, 3, 0), (2, 3, 1)]
[((0, 0, 0), (0, 0, 1)), ((0, 0, 0), (0, 1, 0)), ((0, 0, 0), (1, 0, 0)), ((0, 0, 1), (0, 1, 1)), ((0, 0, 1), (1, 0, 1)), ((0, 1, 0), (0, 1, 1)), ((0, 1, 0), (0, 2, 0)), ((0, 1, 0), (1, 1, 0)), ((0, 1, 1), (0, 2, 1)), ((0, 1, 1), (1, 1, 1)), ((0, 2, 0), (0, 2, 1)), ((0, 2, 0), (0, 3, 0)), ((0, 2, 0), (1, 2, 0)), ((0, 2, 1), (0, 3, 1)), ((0, 2, 1), (1, 2, 1)), ((0, 3, 0), (0, 3, 1)), ((0, 3, 0), (1, 3, 0)), ((0, 3, 1), (1, 3, 1)), ((1, 0, 0), (1, 0, 1)), ((1, 0, 0), (1, 1, 0)), ((1, 0, 0), (2, 0, 0)), ((1, 0, 1), (1, 1, 1)), ((1, 0, 1), (2, 0, 1)), ((1, 1, 0), (1, 1, 1)), ((1, 1, 0), (1, 2, 0)), ((1, 1, 0), (2, 1, 0)), ((1, 1, 1), (1, 2, 1)), ((1, 1, 1), (2, 1, 1)), ((1, 2, 0), (1, 2, 1)), ((1, 2, 0), (1, 3, 0)), ((1, 2, 0), (2, 2, 0)), ((1, 2, 1), (1, 3, 1)), ((1, 2, 1), (2, 2, 1)), ((1, 3, 0), (1, 3, 1)), ((1, 3, 0), (2, 3, 0)), ((1, 3, 1), (2, 3, 1)), ((2, 0, 0), (2, 0, 1)), ((2, 0, 0), (2, 1, 0)), ((2, 0, 1), (2, 1, 1)), ((2, 1, 0), (2, 1, 1)), ((2, 1, 0), (2, 2, 0)), ((2, 1, 1), (2, 2, 1)), ((2, 2, 0), (2, 2, 1)), ((2, 2, 0), (2, 3, 0)), ((2, 2, 1), (2, 3, 1)), ((2, 3, 0), (2, 3, 1))]