Min-Cut/Max-Flow Problem Instances for Benchmarking

NOTE: This dataset is now outdated. Please see https://doi.org/10.11583/DTU.17091101 for the updated version with many more problems.

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.

Files and formats

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_`.

DIMACS

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 `.max` the blocks are in the text file `.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:

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

Binary files

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.

Binary BK (`.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:

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)

Compressed (using Google's snappy: https://github.com/google/snappy):

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

Where:

/** 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
struct BkTermArc {
uint64_t node;
Ty source_cap;
Ty sink_cap;
};

/** Neighbor arc with forward and reverse capacity. */
template
struct BkNborArc {
uint64_t i;
uint64_t j;
Ty cap;
Ty rev_cap;
};

Binary QPBO (`.bq`) files are for storing QPBO problems. Unary and binary terms are stored in separate lists. The format is:

Uncompressed:

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)

Compressed (using Google's snappy: https://github.com/google/snappy):

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

Where:

/** 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
struct BkUnaryTerm {
uint64_t node;
Ty e0;
Ty e1;
};

/** Binary term */
template
struct BkBinaryTerm {
uint64_t i;
uint64_t j;
Ty e00;
Ty e01;
Ty e10;
Ty e11;
};

Block (`.blk`) files are for storing a partition of the graph nodes into disjoint blocks. The format is:

Nodes: uint64_t num_nodes
Blocks: uint16_t num_blocks
Data: (num_nodes x uint16_t) node_blocks

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