A Python library for efficient graphset operations — search, optimization, and enumeration over a huge number of graphs, powered by ZDD.

📦 Looking for the source code? Head over to github.com/graphillion/graphillion.

Features

  • Lightweight data structures for handling x-illions of graphs
  • Search, optimization, and enumeration over large sets of graphs
  • Real-world applications including power network evaluation (DNET) and railway analysis (Ekillion)
  • Efficient C/C++ backend with a Python interface
  • Parallel computing via OpenMP
  • Interoperability with NetworkX
  • Over 600 unit tests
  • MIT licensed

Check out these short videos (English subtitles available):

Overview

Most graph tools, such as NetworkX, work with a single graph at a time. Graphillion takes a different approach: it operates on a large set of graphs at once. Trillions of trillions of graphs can be processed on a single machine.

The concept of a graphset arises naturally whenever you consider multiple subgraphs of a network — possible driving routes on a road map, feasible power flows on an electric grid, or structures within chemical reaction networks. The number of such subgraphs grows exponentially with graph size, easily reaching trillions even for graphs with just a few hundred edges. A brute-force approach would take millions of years, as the video above illustrates. Graphillion solves this problem.

Graphillion lets you exhaustively yet efficiently search a graphset with complex, even nonconvex, constraints. You can find top-k optimal graphs, extract common properties across all graphs in a set, and more. These capabilities enable applications in graph databases, combinatorial optimization, and structural analysis.

Graphillion was originally developed by the JST ERATO Minato project. If you use it in your research, please cite:

Takeru Inoue, Hiroaki Iwashita, Jun Kawahara, and Shin-ichi Minato: “Graphillion: Software Library Designed for Very Large Sets of Labeled Graphs,” International Journal on Software Tools for Technology Transfer, Springer, vol.18, issue 1, pp.57-66, February 2016. (pdf)

Installation

pip install Graphillion

Requires a 64-bit machine and Python 3. On Linux/macOS, a C++ compiler (GCC 4.2+ or Clang) and Python development headers are needed to build from source. See the installation guide for details.

  • GitHub Repository — source code and full documentation
  • PyPI — package and version history
  • DNET — distribution network evaluation tool built on Graphillion
  • Tutorial — Google Colab notebooks (in Japanese)