TCS-TR-A-13-65Date: Tue Jun 11 16:08:22 2013 Title: Graphillion: Software Library Designed for Very Large Sets of Graphs in Python Authors: Takeru Inoue, Hiroaki Iwashita, Jun Kawahara, and Shin-ichi Minato Contact:
Abstract. Several graph libraries have been developed in the past few decades, but they were designed to work with a few graphs even though the number of subgraphs exponentially increases with graph size. In this paper, we develop Graphillion, a software library for very large sets of graphs. Graphillion is not established on a traditional representation of graphs. Instead, a graph set is simply regarded as a ``set of edge sets'' ignoring vertices, which allows us to employ powerful tools of a ``family of sets'' (a set of sets) and permits large graph sets to be handled efficiently. We also utilize advanced graph enumeration algorithms, which enables the simple family tools to understand the graph structure. Graphillion is implemented as a Python library to encourage easy development of its applications, without introducing significant performance overhead. In experiments, we consider two case studies, a puzzle solver and a power network optimizer, in which several operations and heavy optimization have to be done over very large sets of constrained graphs (i.e., cycles or forests with complicated conditions). The results show that Graphillion allows us to manage an astronomical number of graphs with very low development effort. ©Copyright 2013 Authors |