DOI: 10.5281/zenodo.4905882
title: Min-Cut/Max-Flow Problem Instances for Benchmarking

description: <strong>NOTE:</strong> This dataset is now <strong><em>outdated</em></strong>. Please see https://doi.org/10.11583/DTU.17091101 for the updated version with <em>many more problems.</em> This is a collection of min-cut/max-flow problem instances that can be used for benchmarking min-cut/max-flow algorithms. The collection is released in companionship with the paper: Jensen et al., "Review of Serial and Parallel Min-Cut/Max-Flow Algorithms for Computer Vision", T-PAMI, 2022. The problem instances are collected from a wide selection of sources to be as representative as possible. Specifically, this collection contains: Most of the problem instances (some are unavailable due to dead links) published by the University of Waterloo: https://vision.cs.uwaterloo.ca/data/maxflow Super-resolution, texture restoration, deconvolution, decision tree field (DTF) and automatic labeling environment from Verma & Batra, "MaxFlow Revisited: An Empirical Comparison of Maxflow Algorithms for Dense Vision Problems", 2012, BMVC Sparse Layered Graph instances from Jeppesen et al., "Sparse Layered Graphs for Multi-Object Segmentation", 2020, CVPR Multi-object surface fitting from Jensen et al., "Multi-Object Graph-Based Segmentation With Non-Overlapping Surfaces", 2020, CVPRW The reason for releasing this collection is to provide a single place to download all datasets used in our paper (and various previous paper) instead of having to scavenge from multiple sources. Furthermore, several of the problem instances typically used for benchmarking min-cut/max-flow algorithms are no longer available at their original locations and may be difficult to find. By storing the data on Zenodo with a dedicated DOI we hope to avoid this. For license information, see below. <strong>Files and formats</strong> We provide all problem instances in two file formats: DIMACS and a custom binary format. Both are described below. Each file has been zipped, and similar files have then been grouped into their own zip file (i.e. it is a zip of zips). DIMACS files have been prefixed with `dimacs_` and binary files have been prefixed with `bin_`. <strong>DIMACS</strong> All problem instances are available in DIMACS format (explained here: http://lpsolve.sourceforge.net/5.5/DIMACS_maxf.htm). For the larger problem instances, we have also published a partition of the graph nodes into blocks for block-based parallel min-cut/max-flow. The partition matches the one used in the companion review paper (Jensen et al., 2021). For a problem instance with filename `&lt;name&gt;.max` the blocks are in the text file `&lt;name&gt;.blk.txt`. The first line gives the number of blocks. The second gives the block index (zero-indexed) for every node; each entry is separated by a space. Example for a sixteen node graph with four blocks: <pre><code>4 0 0 1 1 2 2 3 3 0 0 1 1 2 2 3 3 0 0 1 1 2 2 3 3 0 0 1 1 2 2 3 3</code></pre> <strong>Binary files</strong> While DIMACS has the advantage of being human-readable, storing everything as text requires a lot of space. This makes the files unnecessarily large and slow to parse. To overcome this, we also release all problem instances in a simple binary storage format. We have two formats: one for graphs and one for quadratic pseudo-boolean optimization (QPBO) problems. Code to convert to/from DIMACS is also available at: https://www.doi.org/10.5281/zenodo.4903946 or https://github.com/patmjen/maxflow_algorithms. <strong>Binary BK</strong> (`.bbk`) files are for storing normal graphs for min-cut/max-flow. They closely follow the internal storage format used in the original implementation of the Boykov-Kolmogorov algorithm, meaning that terminal arcs are stored in a separate list from normal neighbor arcs. The format is: Uncompressed: <pre><code>Header: (3 x uint8) 'BBQ' Types codes: (2 x uint8) captype, tcaptype Sizes: (3 x uint64) num_nodes, num_terminal_arcs, num_neighbor_arcs Terminal arcs: (num_terminal_arcs x BkTermArc) Neighbor arcs: (num_neighbor_arcs x BkNborArc)</code></pre> Compressed (using Google's snappy: https://github.com/google/snappy): <pre><code>Header: (3 x uint8) 'bbq' Types codes: (2 x uint8) captype, tcaptype Sizes: (3 x uint64) num_nodes, num_terminal_arcs, num_neighbor_arcs Terminal arcs: (1 x uint64) compressed_bytes_1 (compressed_bytes_1 x uint8) compressed num_terminal_arcs x BkTermArc Neighbor arcs: (1 x uint64) compressed_bytes_2 (compressed_bytes_2 x uint8) compressed num_neighbor_arcs x BkNborArc </code></pre> Where: <pre><code class="language-cpp">/** Enum for switching over POD types. */ enum TypeCode : uint8_t { TYPE_UINT8, TYPE_INT8, TYPE_UINT16, TYPE_INT16, TYPE_UINT32, TYPE_INT32, TYPE_UINT64, TYPE_INT64, TYPE_FLOAT, TYPE_DOUBLE, TYPE_INVALID = 0xFF }; /** Terminal arc with source and sink capacity for given node. */ template &lt;class Ty&gt; struct BkTermArc { uint64_t node; Ty source_cap; Ty sink_cap; }; /** Neighbor arc with forward and reverse capacity. */ template &lt;class Ty&gt; struct BkNborArc { uint64_t i; uint64_t j; Ty cap; Ty rev_cap; };</code></pre> <strong>Binary QPBO</strong> (`.bq`) files are for storing QPBO problems. Unary and binary terms are stored in separate lists. The format is: Uncompressed: <pre><code>Header: (5 x uint8) 'BQPBO' Types codes: (1 x uint8) captype Sizes: (3 x uint64) num_nodes, num_unary_terms, num_binary_terms Unary arcs: (num_unary_terms x BkUnaryTerm) Binary arcs: (num_binary_terms x BkBinaryTerm)</code></pre> Compressed (using Google's snappy: https://github.com/google/snappy): <pre><code>Header: (5 x uint8) 'bqpbo' Types codes: (1 x uint8) captype Sizes: (3 x uint64) num_nodes, num_unary_terms, num_binary_terms Unary terms: (1 x uint64) compressed_bytes_1 (compressed_bytes_1 x uint8) compressed num_unary_terms x BkUnaryTerm Binary terms: (1 x uint64) compressed_bytes_2 (compressed_bytes_2 x uint8) compressed num_binary_terms x BkBinaryTerm </code></pre> Where:<br> <pre><code class="language-cpp">/** Enum for switching over POD types. */ enum TypeCode : uint8_t { TYPE_UINT8, TYPE_INT8, TYPE_UINT16, TYPE_INT16, TYPE_UINT32, TYPE_INT32, TYPE_UINT64, TYPE_INT64, TYPE_FLOAT, TYPE_DOUBLE, TYPE_INVALID = 0xFF }; /** Unary term */ template &lt;class Ty&gt; struct BkUnaryTerm { uint64_t node; Ty e0; Ty e1; }; /** Binary term */ template &lt;class Ty&gt; struct BkBinaryTerm { uint64_t i; uint64_t j; Ty e00; Ty e01; Ty e10; Ty e11; };</code></pre> <strong>Block</strong> (`.blk`) files are for storing a partition of the graph nodes into disjoint blocks. The format is: <pre><code>Nodes: uint64_t num_nodes Blocks: uint16_t num_blocks Data: (num_nodes x uint16_t) node_blocks</code></pre> We do not claim ownership over the problem instances from the University of Waterloo and those from (Verma and Batra, 2012). Please contact the original sources for additional information. We publish the datasets from (Jeppesen et al., 2020) and (Jensen et al., 2020) under the Creative Commons Attribution 4.0 International (CC BY 4.0), see https://creativecommons.org/licenses/by/4.0/. The specific files are (not counting their `dimacs_`/`bin_` prefix): University of Waterloo (consult original sources) adhead.zip babyface.zip bone.zip bone_sub.zip liver.zip BL06.zip BVZ.zip LB07.zip KZ2.zip Verma & Batra, 2012 (consult original sources): ale.zip dtf.zip deconv.zip super_res.zip texture.zip Jeppesen et al., 2020 (CC BY 4.0): NT32_tomo3.zip NT32_tomo3_216.zip Jensen et al., 2020 (CC BY 4.0): cells.zip foam.zip simcells.zip