Archive for the ‘Graphillion’ Category

Graphillion

Friday, June 21st, 2013

Graphillion

From the webpage:

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 hundreds of 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 funny 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 a graph structure analysis. We will show some practical use cases in the following tutorial, including evaluation of power distribution networks.

Just skimming the tutorial, this looks way cool!

Be sure to check out the references:

  • Takeru Inoue, Hiroaki Iwashita, Jun Kawahara, and Shin-ichi Minato: “Graphillion: Software Library Designed for Very Large Sets of Graphs in Python,” Hokkaido University, Division of Computer Science, TCS Technical Reports, TCS-TR-A-13-65, June 2013.
    (pdf)
  • Takeru Inoue, Keiji Takano, Takayuki Watanabe, Jun Kawahara, Ryo Yoshinaka, Akihiro Kishimoto, Koji Tsuda, Shin-ichi Minato, and Yasuhiro Hayashi, “Loss Minimization of Power Distribution Networks with Guaranteed Error Bound,” Hokkaido University, Division of Computer Science, TCS Technical Reports, TCS-TR-A-12-59, 2012. (pdf)
  • 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)
  • DNET – Distribution Network Evaluation Tool

I first saw this in a tweet by David Gutelius.