Graphillion is a Python software library that provides functions for solving combinatorial problems related to undirected graphs. Graphillion is easy to install, allowing users to immediately take advantage of its capabilities without knowledge of the data structures used in the library. For a given graph, the library holds all subgraphs of the graph that satisfy specified constraints such as paths, trees, and matchings, as well as all vertex sets on the graph such as independent sets and dominating sets. In addition, it can perform solution enumeration, set operations, and uniform random sampling of solutions. This chapter demonstrates how to use Graphillion with examples of Python code and evaluates its performance.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Graphillion: Combinatorial Solver for Graph Problems

  • Jun Kawahara

摘要

Graphillion is a Python software library that provides functions for solving combinatorial problems related to undirected graphs. Graphillion is easy to install, allowing users to immediately take advantage of its capabilities without knowledge of the data structures used in the library. For a given graph, the library holds all subgraphs of the graph that satisfy specified constraints such as paths, trees, and matchings, as well as all vertex sets on the graph such as independent sets and dominating sets. In addition, it can perform solution enumeration, set operations, and uniform random sampling of solutions. This chapter demonstrates how to use Graphillion with examples of Python code and evaluates its performance.