%load_ext lab_black

本章で使用するパッケージ

グラフの基礎

グラフ(graph)は点(node, vertex, point)集合 VV と枝(edge, arc, link)集合 EE から構成され，G=(V,E)G=(V,E) と記される． 点集合の要素を u,v(∈V)u, v (\in V) などの記号で表す． 枝集合の要素を e(∈E)e (\in E) と表す． 22点間に複数の枝がない場合には，両端点 u,vu,v を決めれば一意に枝が 定まるので，枝を両端にある点の組として (u,v)(u,v) もしくは uvuv と表すことができる．

枝の両方の端にある点は，互いに隣接(adjacent)しているとよばれる． また，枝は両端の点に接続(incident)しているとよばれる． 点に接続する枝の本数を次数(degree)とよぶ．

枝に「向き」をつけたグラフを有向グラフ(directed graph, digraph) とよび，有向グラフの枝を有向枝(directed edge，arc, link)とよぶ． 一方，通常の（枝に向きをつけない）グラフであることを強調したいときには， グラフを無向グラフ(undirected graph)とよぶ． 点 uu から点 vv に向かう有向枝 (u,v)∈E(u,v) \in E に対して，uu を枝の尾(tail)もしくは始点， vv を枝の頭(head)もしくは終点とよぶ．また，点vv をuu の後続点(successor)， 点uu を vv の先行点(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 を返す．

rnd_graph[source]

rnd_graph(n, prob)

Make a random graph with 'n' nodes, and edges created between pairs of nodes with probability 'prob'. Returns a pair, consisting of the list of nodes and the list of edges.

rnd_adj[source]

rnd_adj(n, prob)

Make a random graph with 'n' nodes and 'nedges' edges. return node list [nodes] and adjacency list (list of list) [adj]

rnd_adj_fast[source]

rnd_adj_fast(n, prob)

Make a random graph with 'n' nodes, and edges created between pairs of nodes with probability 'prob', running in O(n+m) [n is the number of nodes and m is the number of edges]. Returns a pair, consisting of the list of nodes and the list of edges.

adjacent[source]

adjacent(nodes, edges)

Determine the adjacent nodes on the graph.

nodes, adj = rnd_adj_fast(10, 0.5)
print("nodes=", nodes)
print("adj=", adj)

nodes= [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
adj= [{1, 9}, {0, 2, 4, 5, 6, 7, 8}, {1, 3, 4, 5}, {2, 4, 5, 6, 8}, {1, 2, 3, 7, 8}, {1, 2, 3}, {1, 3}, {8, 1, 4, 9}, {1, 3, 4, 7, 9}, {0, 8, 7}]

グラフをnetworkXに変換する関数

networkXは，Python言語で使用可能なグラフ・ネットワークに対する標準パッケージである． networkXについては，http://networkx.github.io/ を参照されたい．

以下に，上の隣接リスト形式のグラフをnetworkXのグラフに変換するプログラムを示す．

to_nx_graph[source]

to_nx_graph(nodes, adj)

G = to_nx_graph(nodes, adj)
print(G.edges())

[(0, 1), (0, 9), (1, 2), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (9, 7), (9, 8), (2, 3), (2, 4), (2, 5), (4, 3), (4, 7), (4, 8), (5, 3), (6, 3), (7, 8), (8, 3)]

networkXのグラフをPlotlyの図に変換する関数

Plotlyはオープンソースの描画パッケージである（https://plotly.com/python/）． networkXのグラフをPlotlyの図オブジェクトに変換するプログラムを示す．

to_plotly_fig[source]

to_plotly_fig(G, node_size=20, line_width=2, line_color='blue', text_size=20, colorscale='Rainbow', pos=None)

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のデータフォーマットの最大クリーク問題の補グラフを読む．

complement[source]

complement(nodes, edges)

determine the complement of 'edges'

shuffle[source]

shuffle(nodes, adj)

randomize graph: exchange labels of two vertices, a number of times

read_gpp_graph[source]

read_gpp_graph(filename)

Read a file in the format specified by David Johnson for the DIMACS graph partitioning challenge. Instances are available at ftp://dimacs.rutgers.edu/pub/dsj/partition

read_gpp_coords[source]

read_gpp_coords(filename)

Read coordinates for a graph in the format specified by David Johnson for the DIMACS graph partitioning challenge. Instances are available at ftp://dimacs.rutgers.edu/pub/dsj/partition

read_graph[source]

read_graph(filename)

Read a graph from a file in the format specified by David Johnson for the DIMACS clique challenge. Instances are available at ftp://dimacs.rutgers.edu/pub/challenge/graph/benchmarks/clique

read_compl_graph[source]

read_compl_graph(filename)

Produce complementary graph with respect to the one define in a file, in the format specified by David Johnson for the DIMACS clique challenge. Instances are available at ftp://dimacs.rutgers.edu/pub/challenge/graph/benchmarks/clique

隣接グラフの生成関数 make_adj

点集合（リスト，タプル） VV と枝集合（点のタプルのリスト） EE から隣接リストを表す辞書 adj を生成する関数を準備しておく．

make_adj[source]

make_adj(V, E)

Create an adjacency list using V and E.

グラフ基本アルゴリズム

以下では， Introduction to Algorithms (MIT Course Number 6.006；邦訳「アルゴリズムイントロダクション」（近代科学社）) で用いられているグラフの表現と基本アルゴリズムを示す．

グラフは点をキーとし，値をリストとした辞書として表現する．

広がり優先探索関数 bfs

広がり優先探索では，与えられた始点からの距離（枝の本数）が小さいものから順に探索を行う．

広がり優先探索関数 bfsは，集合 VV と隣接リスト（を表す辞書） adj と始点 ss を与えると，広がり優先探索での始点からの距離（枝の本数） d と先行点 p のリストを返す．

点上に定義される色で探索の様子を可視化することができる． 意味は以下の通り．

  • WHITE：未探索
  • GRAY: 探索中
  • BLACK: 探索済み

bfs[source]

bfs(V, adj, s)

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]}")

d[1]=0 p[1]=None
d[2]=1 p[2]=1
d[3]=2 p[3]=2
d[4]=1 p[4]=1
d[5]=2 p[5]=2
d[6]=3 p[6]=3
d[7]=2 p[7]=4
d[8]=3 p[8]=5
d[9]=4 p[9]=6

深さ優先探索関数 dfs

深さ優先探索は，可能な限りグラフを「深く」探索する．

深さ優先探索関数 dfs は，点集合 VV と隣接リスト（を表す辞書） adj と始点 ss を与えると，以下の属性に辞書として情報をもつオブジェクト 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)

d[1]=0 f[1]=17 p[1]=None
d[2]=1 f[2]=12 p[2]=1
d[3]=2 f[3]=7 p[3]=2
d[4]=13 f[4]=16 p[4]=1
d[5]=8 f[5]=11 p[5]=2
d[6]=3 f[6]=6 p[6]=3
d[7]=14 f[7]=15 p[7]=4
d[8]=9 f[8]=10 p[8]=5
d[9]=4 f[9]=5 p[9]=6
[1, 4, 7, 2, 5, 8, 3, 6, 9]

強連結成分関数　scc

強連結成分とは，有向グラフの点の部分集合で，集合内の任意の2点間にパスが存在するものを指す．

make_inverse_adj[source]

make_inverse_adj(V, E)

Create an inversed adjacenct list. That is, all edges (u,v) are recorded as (v,u).

scc[source]

scc(V, E)

__get_super_parent[source]

__get_super_parent(u, p)

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)

[[1, 4], [2, 3, 6], [5], [7, 8], [9]]