graphillion.graphset.graphsの引数
graphillionでグラフセットを作成する方法を公式ドキュメントで調べたときのメモ。
graphillionのバージョンはv1.01。
複雑な条件でグラフセットを作成するにはgraphillion.graphset.graphsを使えば良さそう。 graphillion.graphset.graphsで指定できる引数は以下の通り: graphillion/graphset.py at master · takemaru/graphillion · GitHub
graphs(vertex_groups=None, degree_constraints=None, num_edges=None, no_loop=False, graphset=None, linear_constraints=None) Returns a GraphSet with graphs under given constraints. This is the base method for specific graph classes, e.g., paths and trees. This method can be parallelized with OpenMP by specifying the environmental variable `OMP_NUM_THREADS`: `$ OMP_NUM_THREADS=4 python your_graphillion_script.py` Args: vertex_groups: Optional. A nested list. Vertices in an inner list are connected while those in different inner lists are disconnected. For `[[1, 5], [3]]`, 1 and 5 are connected, while they are not connected with 3. degree_constraints: Optional. A dict with a vertex and a range or int. The degree of a vertex is restricted by the range. For `{1: 2, 6: range(2)}`, the degree of vertex 1 is 2 and that of 6 is less than 2, while others are not cared. num_edges: Optional. A range or int. This argument specifies the number of edges used in graphs to be stored. For `range(5)`, less than 5 edges can be used. no_loop: Optional. True or False. This argument specifies if loop is not allowed. graphset: Optional. A GraphSet object. Graphs to be stored are selected from this object. linear_constraints: Optional. A list of linear constraints. A linear constraint consists of weighted edges and lower/upper bounds. An edge weight is a positive or negative number, which defaults to 1. Weights of the edges that are not included in the constraint are zeros. For instance, `linear_constraints=[([(1, 2, 0.6), (2, 5), (3, 6, 1.2)], (1.5, 2.0))]`, feasible graph weights are between 1.5 and 2.0, e.g., `[(1, 2), (2, 3), (3, 6)]` or `[(1, 2), (2, 5), (5, 6)]`. See graphillion/test/graphset.py in detail. Returns: A new GraphSet object.
vertex_groups
, degree_constraints
, no_loop
はdocstringに書いてある通りの意味。
num_edges
はgraphillion.graphset.cliquesの実装を読めば分かるが、列挙されるグラフの辺の数(または範囲)。
graphset
にGraphSet オブジェクトを指定するとユニバースではなくこのgraphsetからグラフが列挙される(?)
linear_constraints
は
$$
l \leq \sum_{e \in E} w_e \leq u
$$
の形の線形制約を複数与えることができる。