%load_ext lab_black
グラフの基礎
グラフ(graph)は点(node, vertex, point)集合 $V$ と枝(edge, arc, link)集合 $E$ から構成され，$G=(V,E)$ と記される． 点集合の要素を $u, v (\in V)$ などの記号で表す． 枝集合の要素を $e (\in E)$ と表す． $2$点間に複数の枝がない場合には，両端点 $u,v$ を決めれば一意に枝が 定まるので，枝を両端にある点の組として $(u,v)$ もしくは $uv$ と表すことができる．
枝の両方の端にある点は，互いに隣接(adjacent)しているとよばれる． また，枝は両端の点に接続(incident)しているとよばれる． 点に接続する枝の本数を次数(degree)とよぶ．
枝に「向き」をつけたグラフを有向グラフ(directed graph, digraph) とよび，有向グラフの枝を有向枝(directed edge，arc, link)とよぶ． 一方，通常の（枝に向きをつけない）グラフであることを強調したいときには， グラフを無向グラフ(undirected graph)とよぶ． 点 $u$ から点 $v$ に向かう有向枝 $(u,v) \in E$ に対して，$u$ を枝の尾(tail)もしくは始点， $v$ を枝の頭(head)もしくは終点とよぶ．また，点$v$ を$u$ の後続点(successor)， 点$u$ を $v$ の先行点(predecessor)とよぶ．
パス(path)とは，点とそれに接続する枝が交互に並んだものである． 同じ点を通過しないパスを，特に単純パス(simple path)とよぶ． 閉路(circuit)とは，パスの最初の点（始点）と最後の点（終点）が同じ点であるグラフである． 同じ点を通過しない閉路を，特に単純閉路(cycle)とよぶ．
完全グラフ(complete graph)とは，すべての点間に枝があるグラフである． 完全2部グラフ(complete bipartite graph)とは，点集合を2つの部分集合に分割して， （各集合内の点同士の間には枝をはらず；これが2部グラフの条件である）異なる点集合に含まれるすべての点間に枝をはったグラフである．
ランダムグラフの生成
以下の関数では，グラフは点のリスト nodes と隣接点（の集合）のリスト adj として表現している．
ここで生成するグラフは，「メタヒューリスティクスの数理」（共立出版）で用いられたものであり，グラフ問題に対する様々なメタヒューリスティクスで用いられる．
- rnd_graph: 点数 n と点の発生確率 prob を与えるとランダムグラフの点リスト nodes と枝リスト edges を返す．
- rnd_adj: 点数 n と点の発生確率 prob を与えるとランダムグラフの点リスト nodesと隣接点のリスト adj を返す．
- rnd_adj_fast: rnd_adj関数の高速化版；大きなランダムグラフを生成する場合には，こちらを使う．
- adjacent: 点リスト nodes と枝リスト edges を与えると，隣接点のリスト adj を返す．
nodes, adj = rnd_adj_fast(10, 0.5)
print("nodes=", nodes)
print("adj=", adj)
グラフをnetworkXに変換する関数
networkXは，Python言語で使用可能なグラフ・ネットワークに対する標準パッケージである． networkXについては，http://networkx.github.io/ を参照されたい．
以下に，上の隣接リスト形式のグラフをnetworkXのグラフに変換するプログラムを示す．
G = to_nx_graph(nodes, adj)
print(G.edges())
networkXのグラフをPlotlyの図に変換する関数
Plotlyはオープンソースの描画パッケージである（https://plotly.com/python/）． networkXのグラフをPlotlyの図オブジェクトに変換するプログラムを示す．
for v in G.nodes():
G.nodes[v]["color"] = random.randint(0, 3)
fig = to_plotly_fig(G)
plotly.offline.plot(fig);
ユーティリティー関数群
以下に本書で用いるグラフに対する様々なユーテリティ関数を示す．
- complement: 補グラフを生成する．
- shuffle: グラフの点と隣接リストをランダムにシャッフルする．
- read_gpp_graph: DIMACSのデータフォーマットのグラフ分割問題のグラフを読む．
- read_gpp_coords: DIMACSのデータフォーマットのグラフ分割問題の座標を読む．
- read_graph: DIMACSのデータフォーマットの最大クリーク問題のグラフを読む．
- read_compl_graph: : DIMACSのデータフォーマットの最大クリーク問題の補グラフを読む．
V = [1, 2, 3, 4, 5, 6, 7, 8, 9]
E = [
(1, 2),
(2, 3),
(4, 5),
(5, 6),
(7, 8),
(8, 9),
(1, 4),
(4, 7),
(2, 5),
(5, 8),
(3, 6),
(6, 9),
]
adj = make_adj(V, E)
(d, p) = bfs(V, adj, V[0])
for u in V:
print(f"d[{u}]={d[u]} p[{u}]={p[u]}")
深さ優先探索関数 dfs
深さ優先探索は，可能な限りグラフを「深く」探索する．
深さ優先探索関数 dfs は，点集合 $V$ と隣接リスト（を表す辞書） adj と始点 $s$ を与えると，以下の属性に辞書として情報をもつオブジェクト c を返す．
countを探索の反復数とする．
- 点がはじめて探査されたときの反復数 d （開始時刻を表す）
- 点のすべての隣接点が探索されたときの反復数 f（終了時刻を表す）
- 先行点 p
点をトポロジカルオーダー（先行点がかならず前になる順）を求めるには，点の探索が終了したときに，リストの先頭になるように並べればよい． これは，オブジェクト c のtopo属性に格納されている．
def __dfs_visit(u, c):
c.color[u] = GRAY
c.d[u] = c.count
c.count = c.count + 1
for v in c.adj[u]:
if c.color[v] == WHITE:
c.p[v] = u
__dfs_visit(v, c)
c.color[u] = BLACK
c.topo.insert(0, u)
c.f[u] = c.count
c.count = c.count + 1
def dfs(V, adj):
class DfsContext:
pass
c = DfsContext()
c.adj = adj
c.color = {}
c.p = {}
c.d = {}
c.f = {}
c.topo = []
for u in V:
c.color[u] = WHITE
c.p[u] = NIL
c.count = 0
for u in V:
if c.color[u] == WHITE:
__dfs_visit(u, c)
return c
V = [1, 2, 3, 4, 5, 6, 7, 8, 9]
E = [
(1, 2),
(2, 3),
(4, 5),
(5, 6),
(7, 8),
(8, 9),
(1, 4),
(4, 7),
(2, 5),
(5, 8),
(3, 6),
(6, 9),
]
adj = make_adj(V, E)
c = dfs(V, adj)
for u in V:
print(f"d[{u}]={c.d[u]} f[{u}]={c.f[u]} p[{u}]={c.p[u]}")
print(c.topo)
V = [1, 2, 3, 4, 5, 6, 7, 8, 9]
E = [
(1, 4),
(4, 1),
(2, 3),
(2, 5),
(3, 6),
(5, 4),
(5, 9),
(6, 2),
(7, 8),
(8, 5),
(8, 7),
]
R = scc(V, E)
print(R)