2019-05-30 11:49:42 Python

Python

Copy Copied! Full
from graphillion import GraphSet, tutorial # 縦、横の辺の個数 edge = 5 # グリッドグラフをつくる universe = tutorial.grid(edge, edge) # 辺の集合をつくる(タプルのリスト) GraphSet.set_universe(universe) # 全体グラフをつくる # すべての頂点に対する次数制約を表すディクショナリ degree_constraints = {} # すべての頂点の次数を0か2とする number_of_vertex = (edge+1)**2 for i in range(1, number_of_vertex + 1): degree_constraints[i] = (0, 2) # ただし、groupに含まれている頂点の次数は1にする vertex_group = [[2, 6], [1, 11], [3, 22]] # [始点, 終点]の形式 for vertex_pair in vertex_group: degree_constraints[vertex_pair[0]] = 1 degree_constraints[vertex_pair[1]] = 1 # 与えた制約を満たすグラフの集合を返す solutions = GraphSet.graphs(vertex_groups=vertex_group, # 連結成分 degree_constraints=degree_constraints, # 次数 no_loop=True # ループなし ) # 解法があればすべて出力する。なければ何も出力しない。 if len(solutions) >= 1: print("Solution found.") for solution in solutions: tutorial.draw(solution) else: print("No solution found.")
RECOMMEND