Embedded Files
グラフの最小次数順序を算出する Python スクリプト
グラフの最小次数順序を算出する Python スクリプト
[1] より、最小次数順序について説明します。重み付き無向グラフが与えられたとき、次数が最小であるような頂点を選択して削除する操作を反復して得られる点の順序を最小次数順序 (minimum degree ordering) とよびます。ここで、最小次数順序の最後の点と最後から 2 番目の点の対をフラット対 (flat pair) とよびます。
本スクリプトでは、Python でグラフを取り扱うモジュール NetworkX と、可視化のモジュール Matplotlib を用いて、最小次数順序を算出する過程を可視化し、最小次数順序とフラット対を Python のリストとして返します。
備考: 本スクリプトでは辺重みが 1 のグラフを構成しています。
import networkx as nximport matplotlib.pyplot as pltimport numpy as npimport random
FONT_SIZE = 20
def construct_graph(size_vertex_set): """ 頂点数 size_vertex_set から辺を適当に付加することでグラフを構成する関数 """ G = nx.Graph() # 初期化 [ G.add_node(index + 1) for index in range(size_vertex_set) ] # 頂点集合の構成 for index in range(size_vertex_set * 3): # 頂点番号を 1--${頂点集合のサイズ} から選らんで辺の端点とする、 v = random.randint(1, size_vertex_set) w = random.randint(1, size_vertex_set) if v != w: # 自己ループの除外 G.add_edge(v, w) return G
def mdo(G): """ 入力グラフ G から最小次数順序とフラット対を算出する関数 """ degree_list = G.degree # グラフの次数を取得 vertex_set_size = len(degree_list) # 頂点数を取得 fig = plt.figure(figsize=(30, 30)) plt.subplots_adjust(wspace=1, hspace=1) # ラベルがきちんと表示させるように余白をもたせる。 # 入力グラフを描画 ax = fig.add_subplot(5, 5, 1) pos = nx.shell_layout(G) ax.set_title('$G_0 = (V, E)$', fontsize=FONT_SIZE) nx.draw(G, pos=pos, ax=ax, with_labels=True, node_size=1, font_size=20)
# 最小次数順序を算出 mdo_list = [] for index in range(vertex_set_size): min_value_vertex = 0 min_value = float('inf') for degree in degree_list: print('index: {0}, degree: {1}'.format(index, degree)) if degree[1] < min_value: # 最小次数の候補より判定対象の次数が小さい場合 min_value_vertex = degree[0] # 最小次数となるような頂点の候補 min_value = degree[1] # 最小次数の候補 print('min_value_vertex: {0}, min_value: {1}'.format(min_value_vertex, min_value)) mdo_list.append(min_value_vertex) G.remove_node(min_value_vertex) # # 入力グラフから頂点を逐次的に削除 ax = fig.add_subplot(5, 5, index + 2) pos = nx.shell_layout(G) ax.set_title('$G_{{{0}}} := G_{{{1}}} - {2}$'.format(index + 1, index, min_value_vertex), fontsize=FONT_SIZE) nx.draw(G, pos=pos, ax=ax, with_labels=True, node_size=1, font_size=FONT_SIZE) flat_pair = [mdo_list[-1], mdo_list[-2]] return mdo_list, flat_pair mdo_list, flat_pair = mdo(construct_graph(10))print(mdo_list)print(flat_pair)
参考文献[1] 茨木, 永持 and 石井, グラフ理論―連結構造とその応用―, 朝倉書店, (2010)
Google Sites
Report abuse