2015-11-21

ZDD分岐木を描図する

Graphillion ZDD python

from graphillion import GraphSet
import pickle
from itertools import chain
import networkx as nx
import matplotlib.pyplot as plt

# ユニバースの要素数nに
# [(1,2),(2,3),...,(n-1,n)]というユニバースとする
n = 50
universe = []
for i in range(n):
  universe.append((i,i+1))

for i in universe:
  print i

GraphSet.set_universe(universe)

# n個の要素（エッジ）の選び方（サブグラフに相当）をng個取り出すこととする
ng = 20
# それをするにあたり、ユニバースの全サブグラフを部分グラフとして持つGraphSetオブジェクトg_univを作り
# それのランダム・イテレータからのng個をサンプリングする
g_univ = GraphSet({})

g1 = []
i = 1
for sg in g_univ.rand_iter():
  g1.append(sg)
  if i == ng: break
  i += 1
# その部分グラフ集合をG1とする
G1 = GraphSet(g1)
# そのZDDテキスト表記を確認
print(G1.dumps())
# そのテキスト表記は４列行列型なので、それをdataという名前の２次元リストに格納する
data = map (lambda x:x.split(" "),G1.dumps().strip().split("\n"))
# 最終行はピリオドだけなので、除去する
data.pop()
# １次元に広げる
data_fl = list(chain.from_iterable(data))
# 列ごとに格納するべく、行数確認
len_data_fl = len(data_fl)
num_v = len_data_fl/4
# ４列を別々のオブジェクトとする
v_id = data_fl[::4]
v_lab = data_fl[1::4]
v_lo = data_fl[2::4]
v_hi = data_fl[3::4]

# 2タイプのエッジを各行ごとに格納する
e_lo = []
e_hi = []
e_type_lo = []
e_type_hi = []
v_lab_num = []
for i in range(len(v_id)):
  e_lo.append((v_id[i],v_lo[i]))
  e_hi.append((v_id[i],v_hi[i]))
  e_type_lo.append("b")
  e_type_hi.append("r")
  v_lab_num.append(int(v_lab[i]))

# 描図用のグラフオブジェクトを用意する
gg = nx.Graph()
# エッジタイプ別にエッジを登録する
gg.add_edges_from(e_lo,color='b')
gg.add_edges_from(e_hi,color='r')

# 座標は、ノードのラベルをｘ座標に、同じラベルのノードが等間隔でy軸に展開されるように座標を決める
#pos = nx.spring_layout(gg)
pos1 = []
pos2 = []
st = 0.0
# 座標はノードIDと２次元座標のハッシュ
# T,Bのノードをｘ軸最大値、ｙ軸最小・最大値にするために、情報をとりながらループを回す
pos = {v_id[0]:[float(v_lab[0]),st]}

for i in range(1,len(v_id)):
  if v_lab_num[i-1]==v_lab_num[i]:
    st += 1.0
  else:
    st = 0.0
  pos[v_id[i]] = [float(v_lab[i]),st]
  pos1.append(pos[v_id[i]][0])
  pos2.append(pos[v_id[i]][1])
# T,Bの座標を決める
pos['T'] = [max(pos1)+1,0.0]
pos['B'] = [max(pos1)+1,max(pos2)]
#nx.draw(gg)
# ノードをまず描き、エッジを描きたして、最後にmatplotlibで表示する
nx.draw_networkx_nodes(gg,pos,node_color='gray',node_size=10)
nx.draw_networkx_nodes(gg,pos,nodelist=['T'],node_color='r',node_size=10)
nx.draw_networkx_nodes(gg,pos,nodelist=['B'],node_color='blue',node_size=10)

nx.draw_networkx_edges(gg,pos,e_lo,edge_color='gray',alpha=0.1)
nx.draw_networkx_edges(gg,pos,e_hi,edge_color='r')
plt.show()

ちょっと改定

# coding: UTF-8

from graphillion import GraphSet
import pickle
from itertools import chain

import networkx as nx
import matplotlib.pyplot as plt

n = 50
universe = []
for i in range(n):
  universe.append((i,i+1))

for i in universe:
  print i

GraphSet.set_universe(universe)

ng = 20

g_univ = GraphSet({})

g1 = []
i = 1
for sg in g_univ.rand_iter():
  g1.append(sg)
  if i == ng: break
  i += 1

G1 = GraphSet(g1)
print(G1.dumps())

data = map (lambda x:x.split(" "),G1.dumps().strip().split("\n"))
data.pop()


data_fl = list(chain.from_iterable(data))

len_data_fl = len(data_fl)
num_v = len_data_fl/4

v_id = data_fl[::4]
v_lab = data_fl[1::4]
v_lo = data_fl[2::4]
v_hi = data_fl[3::4]

e_lo = []
e_hi = []
e_type_lo = []
e_type_hi = []
v_lab_num = []
for i in range(len(v_id)):
  e_lo.append((v_id[i],v_lo[i]))
  e_hi.append((v_id[i],v_hi[i]))
  e_type_lo.append("b")
  e_type_hi.append("r")
  v_lab_num.append(int(v_lab[i]))

gg = nx.Graph()

gg.add_edges_from(e_lo,color='b')
gg.add_edges_from(e_hi,color='r')

#pos = nx.spring_layout(gg)
st = 0.0 + 0.1 * v_lab_num[0]
pos = {v_id[0]:[float(v_lab[0]),st]}
pos1 = [float(v_lab[0])]
pos2 = [st]
for i in range(1,len(v_id)):
  if v_lab_num[i-1]==v_lab_num[i]:
    st += 1.0
  else:
    st = 0.0 + 0.1 * v_lab_num[i]
  pos[v_id[i]] = [float(v_lab[i]),st]
  pos1.append(pos[v_id[i]][0])
  pos2.append(pos[v_id[i]][1])

#pos['T'] = [max(pos1)+1,0.0 + 0.1 * (v_lab_num[0]+1)]
pos['T'] = [max(pos1)+1,min(pos2)-1]
pos['B'] = [max(pos1)+1,max(pos2)+1]
#nx.draw(gg)
nx.draw_networkx_nodes(gg,pos,node_color='gray',node_size=10)
nx.draw_networkx_nodes(gg,pos,nodelist=['T'],node_color='r',node_size=10)
nx.draw_networkx_nodes(gg,pos,nodelist=['B'],node_color='blue',node_size=10)

nx.draw_networkx_edges(gg,pos,e_lo,edge_color='gray',alpha=0.1)
nx.draw_networkx_edges(gg,pos,e_hi,edge_color='r')
plt.show()