Awesome

Graphillion - Fast, lightweight library for a huge number of graphs

Japanese page

• News
• Features
• Overview
• Installing
• Tutorial
• Creating graphsets
• Manipulating graphsets
• Parallel computing
• Working with NetworkX
• Library reference
• Example codes
• Future work
• References

News

• Graphillion version 1.0 is released with long-awaited features:
  • Python 3 is supported (Python 2 is as well),
  • Parallel computing is enabled with OpenMP,
  • More efficient configuration (i.e., the edge order) is introduced, and
  • Advanced set operations (e.g., join, meet, quotient) are introduced.
• Graphillion book was published in April 2015 (sorry, written in Japanese).
• Graphillion was used in the lecture by Prof. Jun Kawahara at Nara Institute of Science and Technology in January and February 2015.
• Graphillion version 2.0rc0 is published, and will be officially released soon. You can try 2.0rc0 by the following command.

pip install git+https://github.com/takemaru/graphillion.git@v2.0rc0

Features

Graphillion is a Python software package on search, optimization, and enumeration for a graphset, or a set of graphs.

• Lightweight data structures for handling x-illions of graphs
• Search, optimization, and enumeration performed over a large number of graphs
• Used for several applications, e.g., power network evaluation (DNET), railway analysis (Ekillion), as shown in References
• Efficient implementation extending Python with C/C++
• Parallel computing with OpenMP
• Working with existing graph tools like NetworkX
• Open source MIT license
• Well tested: more than 600 unit tests
• Additional benefits from Python: fast prototyping, easy to teach, and multi-platform

We provide fun short movies to answer the following questions.

• Why Graphillion? Watch Time with class! Let's count!, which is watched more than a million times!

  

• What's Graphillion? Watch Graphillion: Don't count naively.

  

Overview

Graphillion is a Python library for efficient graphset operations. Unlike existing graph tools such as NetworkX, which are designed to manipulate just a single graph at a time, Graphillion handles a large set of graphs very efficiently. Surprisingly, trillions of trillions of graphs can be processed on a single computer with Graphillion.

You may be curious about an uncommon concept of graphset, but it comes along with any graph or network when you consider multiple subgraphs cut from the graph; e.g., considering possible driving routes on a road map, examining feasible electric flows on a power grid, or evaluating the structure of chemical reaction networks. The number of such subgraphs can be trillions even in a graph with just a few hundred edges, since subgraphs increase exponentially with the graph size. It takes millions of years to examine all subgraphs with a naive approach as demonstrated in the fun movie above; Graphillion is our answer to resolve this issue.

Graphillion allows you to exhaustively but efficiently search a graphset with complex, even nonconvex, constraints. In addition, you can find top-k optimal graphs from the complex graphset, and can also extract common properties among all graphs in the set. Thanks to these features, Graphillion has a variety of applications, including graph database, combinatorial optimization, and graph structure analysis. We will show some practical use cases in the following tutorial, including the evaluation of power distribution networks.

Graphillion can be used freely under the MIT license. It is mainly developed by JST ERATO Minato project. We would really appreciate it if you would refer to our paper and address our contribution to the use of Graphillion in your paper.

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)

Graphillion is still under development. We really appreciate any pull request and patch if you add some changes that benefit a wide variety of people.

Now, install Graphillion and go to the tutorial. You'll find its power and utility.

Installing

Requirements

All OSes

• 64-bit machines
  • It is required to handle large numbers
• Python version 2.7/3.4 or later
• NetworkX and Matplotlib - optional for the tutorial
  • NetworkX and Matplotlib are Python modules for creating and drawing a graph. These packages are not required for Graphillion, but used in tutorial. They can be installed by:

$ sudo pip install networkx
$ sudo pip install matplotlib

UNIX including Linux and macOS

• Python development environment (Python.h)
  • It is included with XCode in macOS, while it can be installed by apt-get install python-dev in Ubuntu.
• GCC or Clang
  • To build Graphillion, you need gcc version 4.2 or later.
  • For macOS: use Apple official Clang included in XCode, or a memory allocation error might occur.

Windows

• Visual C++ 2015 Redistributable Packages
  • To run Graphillion on Windows, you need this.

Quick install

Just type:

$ sudo pip install graphillion

and an attempt will be made to find and install an appropriate version that matches your operating system and Python version.

For FreeBSD: Graphillion can also be installed by FreeBSD Ports.

Installing from source

You can install from the source by downloading a source archive file (tar.gz or zip) or by checking out the source files from the GitHub source code repository.

Source archive file

1. Download the source (tar.gz or zip file) from https://github.com/takemaru/graphillion
2. Unpack and change the directory to the source directory (it should have the file setup.py)
3. Run python setup.py build to build
4. (optional) Run python setup.py test -q to execute the tests
5. Run sudo python setup.py install to install

GitHub repository

1. Clone the Graphillion repository git clone https://github.com/takemaru/graphillion.git
2. Change the directory to "graphillion"
3. Run python setup.py build to build
4. (optional) Run python setup.py test -q to execute the tests
5. Run sudo python setup.py install to install

If you don't have permission to install software on your system, you can install it into another directory using the -user, -prefix, or -home flags to setup.py. For example:

$ python setup.py install --prefix=/home/username/python
  or
$ python setup.py install --home=~
  or
$ python setup.py install --user

If you didn't install in the standard Python site-packages directory you will need to set your PYTHONPATH variable to the alternate location. See http://docs.python.org/inst/search-path.html for further details.

Windows

Please see Graphillion for Windows.

Tutorial

If you haven't seen our fun movie, Time with class! Let's count!, please watch it before beginning the tutorial. This movie, which has been watched more than a million times, will convince you of a need for Graphillion. The summary of this tutorial is also provided as a movie, Graphillion: Don't count naively.

We believe that you enjoyed the movies and understood the necessity and features of Graphillion. Now, let's see Graphillion in more detail.

We first introduce the terminology used in Graphillion, as follows:

Vertices (or nodes) can be any hashable object; e.g., a number, a text string, etc. Edges (or links) are defined as a pair of vertices, and a graph is a list of edges; currently, Graphillion supports undirected graphs only. A GraphSet object stores a set of graphs.

Before anything else, we start the Python interpreter and import Graphillion and a helper module; the latter provides some functions like graph creation and drawing for the tutorial.

$ python
>>> from graphillion import GraphSet
>>> import graphillion.tutorial as tl  # helper functions just for the tutorial

Paths on a grid graph

In the beginning, we define our universe. The universe can be any graph, and a graph handled by Graphillion must be a subgraph of this graph. In this tutorial, we use the 8x8 grid graph as our universe (the graph size should be regarded as 9x9, but we follow the definition in the movie).

>>> universe = tl.grid(8, 8)
>>> GraphSet.set_universe(universe)
>>> tl.draw(universe)  # show a pop-up window of our universe

We find all the simple paths between the opposing corners; it took four hours with the supercomputer in the movie.

>>> start = 1
>>> goal = 81
>>> paths = GraphSet.paths(start, goal)
>>> len(paths)  # or paths.len() for very large set
3266598486981642

It's very quick, isn't it? (If you get 980466698, check whether your machine is 32-bit; Graphillion requires 64-bit machines.) Since the paths object contains all the paths, you can enumerate them one by one.

>>> for path in paths:
...     path
... # stop by Ctrl-C because it'll take years
>>> tl.draw(paths.choice())  # show one of the paths

Next, in order to demonstrate the filtering or search capability of Graphillion, we choose paths with given conditions. Let's assume that a treasure box and its key are placed on the grid as shown in the figure.

We consider all paths on which the key is picked up before reaching the treasure box. We're not allowed to pass through the same place twice. First, search for the paths to the key not through the treasure box, and then select the paths including the key's paths and the treasure box.

>>> key = 64
>>> treasure = 18
>>> paths_to_key = GraphSet.paths(start, key).excluding(treasure)  # paths to the key not through the treasure box
>>> treasure_paths = paths.including(paths_to_key).including(treasure)  # paths to goal via the key and treasure box
>>> len(treasure_paths)
789438891932744
>>> tl.draw(treasure_paths.choice())  # show one of the paths

Test if all the treasure paths are a subset of the original paths, which connect between the corners.

>>> treasure_paths < paths  # "<" means "subset-of" in Graphillion
True

We conduct statistical processing with random sampling. Graphillion enables you to choose a sample (a graph) from the graphset uniformly randomly. Draw a histogram of "how many turns on the treasure paths" as follows:

>>> i = 0
>>> data = []
>>> for path in treasure_paths.rand_iter():
...     data.append(tl.how_many_turns(path))  # count the number of turns on the path
...     if i == 100: break
...     i += 1
...
>>> tl.hist(data)

The histogram shows that we make a turn at a corner usually 30-50 times through a single path. Without Graphillion, it would be very hard to investigate such a complicated property for a very large set with 10^14 paths. We also find that the shortest path involves only five turns, which is derived by method min_iter(), an optimizer provided by Graphillion.

>>> for path in treasure_paths.min_iter():
...     print(tl.how_many_turns(path))
...     break  # if not break, multiple paths can be yielded in the ascending order
...
5

As an application of path enumeration, you'll find Ekillion very interesting, which enumerates all JR train paths in Japan's metropolitan and suburbs from startpoint to endpoint.

Power flows on a distribution network

Graphillion works on any graphs other than square grids, and handles other subgraphs than simple paths. Next, we consider a power distribution network in the figure. In this network, we assume that a vertex is a house and an edge is a power line with a switch. The power is provided by the four generators at the corners.

>>> universe = tl.grid(8, 8, 0.37)  # 37 % of edges are randomly removed from 8x8 grid
>>> GraphSet.set_universe(universe)
>>> generators = [1, 9, 73, 81]
>>> tl.draw(universe)

The power flow is determined by configuring switches, which are placed on each line. If a switch is closed (an edge exists on a graph), the power is transmitted on the line; otherwise, not. The power must be transmitted to all houses, while the flow must not have a loop to protect against short circuits. The power flow, hence, must form a forest, a set of trees, rooted at generators. We find all of such forests as follows: (note that the number, 54060425088, can be different since the network was randomly generated in tl.grid())

>>> forests = GraphSet.forests(roots=generators, is_spanning=True)  # a forest represents a power flow covering all houses without loop
>>> len(forests)
54060425088
>>> tl.draw(forests.choice())

The amount of power transmitted from a single generator should be strictly restricted, so as not to exceed the capacity. The forest shown above may have a very large tree, which implies that the generator sends too much power beyond its capacity. Here, we assume that each generator is allowed to provide power to less than 23 houses. We first find all dangerous cases of too much power, and then select safe flows without the dangerous cases.

>>> too_large_trees = GraphSet()  # empty graphset
>>> for substation in generators:
...     too_large_trees |= GraphSet.trees(root=substation).larger(23)  # unsafe power flows
...
>>> safe_forests = forests.excluding(too_large_trees)  # power flows without the unsafe ones
>>> len(safe_forests)
294859080
>>> tl.draw(safe_forests.choice())

Since we found all the safe flows, we try to change the network from the current configuration to a safe one using an optimization technique. The current configuration is given by:

>>> closed_switches = (forests - safe_forests).choice()  # sets of closed switches in unsafe power flows
>>> tl.draw(closed_switches)

New configuration must be one of the safe flows, and must be realized with least switch operations. We put a score (edge weight) on a new switch status if it is inconsistent with the current status, as shown in the table.

>>> scores = {}  # scores for closed switches in the new configuration (default is 0)
>>> for switch in universe:
...     # if current status is closed then the score is 1, else -1
...     scores[switch] = 1 if switch in closed_switches else -1
...

We try to find a new configuration (forest) with a maximum score. The configuration has a maximum score and can be realized with the least switch operations. Compare it with the current configuration above, and you'll find them quite alike; only eight switch operations are required from the terrible unsafe configuration to a safe one.

>>> for forest in safe_forests.max_iter(scores):
...     tl.draw(forest)
...     break  # if not break, multiple configs are yielded from the highest score
...

Finally, we investigate serious failures that prevent safe power delivery. We search for minimal blocking sets, or minimal hitting sets more generally, to study such failures. A hitting set is roughly defined such that all the given sets are hit by at least one element in the hitting set; e.g., given {1, 2}, {2, 3}, and {3}, minimal hitting sets are {1, 3} and {2, 3}. A hitting set indicates a critical failure pattern; if power lines in a hitting set are broken, all the flows can't be configured.

>>> failures = safe_forests.blocking().minimal()  # a set of all minimal blocking sets

To help your understanding, remove all lines in a hitting set from the network, and you'll find no safe flow.

>>> failure = failures.choice()  # a hitting set (a set of critical power lines)
>>> for line in failure:
...     safe_forests = safe_forests.excluding(line)  # remove a line in the hitting set
...
>>> len(safe_forests)
0

Small hitting sets (e.g., less than five lines) might imply vulnerability of the network. We now find 767 small failure patterns, which should be investigated carefully.

>>> len(failures.smaller(5))
767

Though actual power distribution networks are much more complicated, we basically rely on the same idea in the study of power distribution networks. Our power loss minimization tool, which optimizes a network with a nonlinear objective function with nonconvex constraints, is available online at DNET.

Creating graphsets

Graphillion provides three ways to create a GraphSet object; with a graph list, edge constraints, and graph types like paths and trees.

Please don't forget to set the universe before working with GraphSet, as mentioned in tutorial. We use the following universe in this section.

>>> from graphillion import GraphSet
>>> universe = [(1, 2), (1, 4), (2, 3), (2, 5), (3, 6), (4, 5), (5, 6)]
>>> GraphSet.set_universe(universe)

Graph list

This is the most straightforward way to create a GraphSet object. Specify a list of graphs and get an object with the graphs.

In the following example, two graphs, one has a single edge and the other has two edges, are given. A GraphSet object with the two graphs is created.

>>> graph1 = [(1, 4)]
>>> graph2 = [(1, 2), (2, 3)]
>>> gs = GraphSet([graph1, graph2])
>>> gs
GraphSet([[(1, 4)], [(1, 2), (2, 3)]])

If no argument is given, it is treated as an empty list [] and an empty GraphSet is returned.

>>> gs = GraphSet()
>>> gs
GraphSet([])

Edge constraints

Edge constraints specify edges to be included or not included in the object. These constraints must be represented by a dict of included or excluded edge lists. Edges not specified in the dict are "don't-care"; they can be included and excluded in the object.

In the following example, edge (1, 4) is included while edges (1, 2) and (2, 3) aren't.

>>> edges1 = [(1, 4)]
>>> edges2 = [(1, 2), (2, 3)]
>>> GraphSet({'include': edges1, 'exclude': edges2})
GraphSet([[(1, 4)], [(1, 4), (2, 5)], [(1, 4), (3, 6)], ...

An empty dict {} means that no constraint is specified, and so a GraphSet including all possible graphs in the universe is returned (let N the number of edges in the universe, 2^N graphs are stored in the new object).

>>> gs = GraphSet({})
>>> len(gs)
128  # 2^7

Graph types

You can specify a graph type, such as paths and trees, and create a GraphSet object that stores all graphs matching the type. Graphillion supports the following graph types:

GraphClass class supports the following further graph classes:

• claw_graphs
• claw_free_graphs
• diamond_graphs
• diamond_free_graphs
• gem_graphs
• gem_free_graphs
• odd_hole_graphs
• odd_hole_free_graphs
• chordal_graphs
• cographs
• chordal_bipartite_graphs
• split_graphs
• block_graphs
• ptolemaic_graphs
• threshold_graphs
• gridline_graphs
• domino_graphs
• linear_domino_graphs

For example, paths() method takes two arguments, two end vertices, and finds all paths between the vertices.

>>> paths = GraphSet.paths(1, 6)
>>> paths
GraphSet([[(1, 2), (2, 3), (3, 6)], [(1, 2), (2, 5), (5, 6)], [(1, 4), (4, 5 ...

The arguments are defined for each type, please see the library reference in detail.

Graphillion also provides low-level interface graphs() to specify more complicated graph types; actually, the specific methods call this low-level interface internally. The following example is the same with paths(1, 6).

>>> start = 1
>>> end = 6
>>> zero_or_two = xrange(0, 3, 2)
>>> degree_constraints = {start: 1, end: 1,
...                       2: zero_or_two, 3: zero_or_two,
...                       4: zero_or_two, 5: zero_or_two}
>>> GraphSet.graphs(vertex_groups=[[start, end]],
...                 degree_constraints=degree_constraints,
...                 no_loop=True)
GraphSet([[(1, 2), (2, 3), (3, 6)], [(1, 2), (2, 5), (5, 6)], [(1, 4), (4, 5 ...

If these methods are called object methods, like gs.paths(1, 6), graphs are selected only from the GraphSet object. Please see the library reference for more details. The internal implementation of graphs() is independently available as TdZdd.

GraphClass class can be used as follows:

from graphillion.graphclass import GraphClass
gs = GraphClass.claw_free_graphs()

Manipulating graphsets

Graphillion provides many operations to manipulate graphs in a GraphSet object. These operations are classified into selection, modification, and comparison; some of them are derived from Python's set methods. Graphillion also provides some iterators and serialization. Please see the library reference for details of each method.

Selection methods

The following methods select graphs from a given GraphSet object (or two given GraphSet objects if binary operation). No new graphs are generated during the operation.

Creation methods specifying graph types also work as selection methods.

Modification or generation methods

The following methods generate new graphs. Some methods modify graphs stored in gs (self), while others return a GraphSet with the newly generated graphs.

Modifying graphs in gs (self)

Generating new graphs

Comparison and evaluation methods

The following methods provide comparison or evaluation for GraphSet objects.

Iterators

Graphillion provides various iterators. rand_iter() can be used for random sampling in statistical analysis. min_iter() and max_iter() can be used as optimizers, and they yield not just an optimal graph but top-k graphs. pop() and choice() return a graph in the GraphSet object, though they aren't iterators.

Dumping and loading methods

Graphillion allows you to dump a graphset to a file, and to load it from the file. Dumping and loading operations must be done together with pickling the universe; see the library reference in detail.

Python's set methods

Graphillion supports Python's set methods. These methods treat a graph just as an element of the set and don't care the graph structure.

• gs.union(other), gs | other,
• gs.intersection(other), gs & other,
• gs.difference(other), gs - other,
• gs.symmetric_difference(other), gs ^ other,
• gs.update(other), gs |= other,
• gs.add(graph),
• gs.remove(graph), gs.discard(graph),
• gs.clear(),
• gs.isdisjoint(gs),
• gs.issubset(gs),
• gs.issuperset(gs),
• graph in gs,
• len(gs),
• gs.pop(), and
• gs.copy().

Parallel computing

Graphillion runs in parallel using OpenMP, an API supporting multi-platform shared memory multiprocessing. To enjoy parallel computing, specify the number of CPU cores to use by the environmental variable OMP_NUM_THREADS. An example of using four cores is:

$ OMP_NUM_THREADS=4 python your_graphillion_script.py

Currently, the following methods can be parallelized:

• GraphSet.graphs(constraints)
• GraphSet.connected_components(vertices)
• GraphSet.cliques(k)
• GraphSet.trees(root, is_spanning)
• GraphSet.forests(roots, is_spanning)
• GraphSet.cycles(is_hamilton)
• GraphSet.paths(terminal1, terminal2, is_hamilton)
• GraphSet.matchings()
• GraphSet.perfect_matchings()
• GraphSet.induced_graphs()

Working with NetworkX

Graphillion transparently works with existing graph tools like NetworkX. Any object like networkx.Graph can be recognized as a graph in Graphillion, while an edge list is a graph by default.

Define two methods that associate a new graph object with an edge list; one method is used for converting an edge list into a graph object, and the other is vice versa. We show an example for NetworkX.

>>> import networkx as nx
>>> # for NetworkX version 1.x
...
>>> GraphSet.converters['to_graph'] = nx.Graph
>>> GraphSet.converters['to_edges'] = nx.Graph.edges
>>> # for NetworkX version 2.x
...
>>> GraphSet.converters['to_graph'] = nx.from_edgelist
>>> GraphSet.converters['to_edges'] = nx.to_edgelist

We can now pass NetworkX's graph objects to Graphillion like this.

>>> g = nx.Graph(...)  # create a graph by NetworkX
>>> GraphSet.set_universe(g)

We also receive NetworkX's graph objects from Graphillion.

>>> gs.choice()  # return a NeworkX's graph object
<networkx.classes.graph.Graph object at 0x100456d10>

For visualizing graphs, NetworkX provides an interface to Matplotlib plotting package along with several node positioning algorithms.

>>> nx.draw(gs.choice())
>>> import matplotlib.pyplot as plt
>>> plt.show()  # show a pop-up window

Library reference

The library reference can be browsed using pydoc in your terminal window:

$ pydoc graphillion.GraphSet

Or in HTML:

$ pydoc -w graphillion.GraphSet

Example code

Example code is found here.

Future work

• More efficient internal data conversion
• More efficient search algorithms for optimization
• Nonlinear objective functions in optimization
• More efficient algorithms for hitting sets and cliques
• Sync the internal random seed with Python's random
• Documentation on performance
• Multithreading
• Garbage collections
• Mailing lists
• Coding rules
• Developer documents

References

About Graphillion and its internals

• 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. (doi)

• Yuma Inoue and Shin-ichi Minato, "Acceleration of ZDD Construction for Subgraph Enumeration via Path-width Optimization," TCS Technical Reports, TCS-TR-A-16-80, October 2016. (pdf)

• Hana Ito, Yuma Inoue, and Shin-ichi Minato, "Experiments and Considerations on Variable Ordering in Top-Down Construction of ZDDs," Forum on Information Technology, vol.14, no.1, pp.115-116, September 2015. (pdf, in Japanese)

• JST ERATO Minato Discrete Structure Manipulation System Project, "High-Speed Graph Enumeration Algorithms," Morikita Publishing, April 2015. (amazon, in Japanese)

• Jun Kawahara, "Graphillion: Python library handling a huge number of subgraphs," Python Seminer, December 2014. (pdf, in Japanese)

• Jun Kawahara, Takeru Inoue, Hiroaki Iwashita and Shin-ichi Minato, "Frontier-based Search for Enumerating All Constrained Subgraphs with Compressed Representation," Hokkaido University, Division of Computer Science, TCS Technical Reports, TCS-TR-A-14-76, September 2014. (pdf)

• Takeru Inoue, "Graphillion updates," JST ERATO Minato project seminar, February 2014. (pdf)

• Hiroaki Iwashita and Shin-ichi Minato, "Efficient Top-Down ZDD Construction Techniques Using Recursive Specifications," TCS Technical Reports, TCS-TR-A-13-69, December 2013. (pdf)

• Takeru Inoue, Hiroaki Iwashita, Jun Kawahara, and Shin-ichi Minato, "Graphillion: ZDD-based Software Library for Very Large Sets of Graphs," Proc. of the 18th Workshop on Synthesis And System Integration of Mixed Information Technologies (SASIMI), Poster Presentation, October 2013. (html)

• Takeru Inoue, "Graphillion: Python module for very large sets of graphs," PyCon APAC, September 2013.

• Takeru Inoue, "[Invited Talk] Graphillion: Software Library for Very Large Sets of Graphs," Technical Report of IEICE, vol.113, no.140, IN2013-43, pp.43-47, July 2013. (pdf, in Japanese)

• Takahisa Toda, "Hypergraph Transversal Computation with Binary Decision Diagrams," Proc. of 12th International Symposium on Experimental Algorithms (SEA), pp.91-102, June 2013. (doi)

• Graphillion for Windows

• TdZdd - A top-down/breadth-first decision diagram manipulation framework

• GGCount - A C++ program for fast computation of the number of paths in a grid graph

Using Graphillion or related algorithms

• DNET - Distribution Network Evaluation Tool

• Ekillion - Enumerating all JR train paths in Japan

• Teru Ohashi and Tatsuhiro Tsuchiya, "Generating High Strength Test Suites for Combinatorial Interaction Testing Using ZDD-Based Graph Algorithms," Proc. of IEEE 22nd Pacific Rim International Symposium on Dependable Computing (PRDC), pp.78-85, January 2017. (doi)

• Daisuke Yoshino and Eiji Hato, "Fast Enumeration Method of Travel Route of DRT Using Zero-suppressed Binary Decision Diagram," Journal of Japan Society of Civil Engineers, vol.72, no.5, pp.1229-1239, December 2016. (doi)

• Jun Kawahara, Toshiki Saitoh, Hirofumi Suzuki, and Ryo Yoshinaka, "Solving the Longest Oneway-Ticket Problem and Enumerating Letter Graphs by Augmenting the Two Representative Approaches with ZDDs," Proc. of the Computational Intelligence in Information Systems Conference (CIIS), pp.294-305, November 2016. (doi)

• Yuji Takenobu, Norihito Yasuda, Shunsuke Kawano, Yasuhiro Hayashi, and Shin-ichi Minato, "Evaluation of Annual Energy Loss Reduction Based on Reconfiguration Scheduling," IEEE Transactions on Smart Grid, September 2016. (doi)

• Masashi Hashimoto, Tomihiro Utsumi, and Takeru Inoue, "[Invited Talk] Availability Analyses for Photonic Network by Minimal Blocking Set using ZDD based Graphillion," Technical Report of IEICE, vol.116, no.205, PN2016-22, pp.45-51, September 2016. (html, in Japanese)

• Y. Takenobu, S. Kawano, Y. Hayashi, N. Yasuda and S. Minato, "Maximizing hosting capacity of distributed generation by network reconfiguration in distribution system," Proc. of Power Systems Computation Conference (PSCC), pp.1-7, June 2016. (doi)

• Subaru Fukuda and Naoshi Sakamoto, "A Failure Estimation System for Networks Applying Graphillion," Technical Report of IEICE, vol.115, no.483, NS2015-212, pp.255-260, March 2016. (html, in Japanese)

• Arthur Choi, Nazgol Tavabi, and Adnan Darwiche, "Structured Features in Naive Bayes Classification," AAAI, pp.3233-3240, February 2016. (pdf)

• Ikki Fujiwara, Satoshi Fujita, Koji Nakano, Takeru Inoue, and Michihiro Koibuchi, "Let's Solve the Order/Degree Problem to Make the Lowest-latency Interconnections," Technical Report of IEICE, vol.115, no.174, CPSY2015-38, pp.223-228, August 2015. (html, in Japanese)

• Atsushi Takizawa, Yushi Miyata, and Naoki Katoh, "Enumeration of Floor Plans Based on a Zero-Suppressed Binary Decision Diagram," International Journal of Architectural Computing, vol.13, no.1, pp.25-44, March 2015. (pdf)

• Hiroyuki Hanada, Shuhei Denzumi, Yuma Inoue, Hiroshi Aoki, Norihito Yasuda, Shogo Takeuchi, and Shin-ichi Minato, "Enumerating Eulerian Trails via Hamiltonian Path Enumeration," International Workshop on Algorithms and Computation (WALCOM), pp.161-174, February 2015. (doi)

• Takeru Inoue, Norihito Yasuda, Shunsuke Kawano, Yuji Takenobu, Shin-ichi Minato, and Yasuhiro Hayashi, "Distribution Network Verification for Secure Restoration by Enumerating All Critical Failures," IEEE Transactions on Smart Grid, October 2014. (doi)

• Takeru Inoue, Keiji Takano, Takayuki Watanabe, Jun Kawahara, Ryo Yoshinaka, Akihiro Kishimoto, Koji Tsuda, Shin-ichi Minato, and Yasuhiro Hayashi, "Distribution Loss Minimization with Guaranteed Error Bound," IEEE Transactions on Smart Grid, vol.5, issue.1, pp.102-111, January 2014. (doi)

• Ryo Yoshinaka, Toshiki Saitoh, Jun Kawahara, Koji Tsuruma, Hiroaki Iwashita, and Shin-ichi Minato, "Finding All Solutions and Instances of Numberlink and Slitherlink by ZDDs," Algorithms 2012, 5(2), pp.176-213, 2012. (doi)

Citing Graphillion

• Arthur Choi, Yujia Shen, and Adnan Darwiche, "Tractability in Structured Probability Spaces," Proc. of Advances in Neural Information Processing Systems (NIPS), pp.3480-3488, 2017.
• Michihiro Koibuchi, Ikki Fujiwara, Fabien Chaix, and Henri Casanova, "Towards Ideal Hop Counts in Interconnection Networks with Arbitrary Size," Proc. of 4th International Symposium on Computing and Networking (CANDAR), pp.188-194, November 2016. (doi)
• Shin-ichi Minato, "Power of Enumeration -- BDD/ZDD-Based Techniques for Discrete Structure Manipulation," IEEE 46th International Symposium on Multiple-Valued Logic (ISMVL), pp.143-143, July 2016. (doi)
• Masahiro Kawahara, Takehide Soh, Mutsunori Banbara, and Naoyuki Tamura, "Constraint Models for SAT-based Subgraph Search," Proc. of the 30th Annual Conference of the Japanese Society for Artificial Intelligence, 1D4-OS-02a-4, June 2016. (pdf, in Japanese)
• Shin-ichi Minato, "Counting by ZDD," Encyclopedia of Algorithms, Springer, pp.454-458, April 2016. (doi)
• Yasuhiro Takei, Masanori Hariyama, and Michitaka Kameyama, "Evaluation of an FPGA-Based Shortest-Path-Search Accelerator," Proc. of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA), pp.613-617, 2015. (pdf)
• Tsutomu Sasao and Jon T. Butler, "Applications of Zero-Suppressed Decision Diagrams," Morgan & Claypool Publishers, November 2014. (doi)