Graph regularity DIMACS conventions
From Computer Vision at Western
This page explains conventions for DIMACS files in our downloadable maxflow problem instances in vision. They are essentially 'hints' that do not affect the DIMACS format itself, and are only relevant to specialised maxflow implementations.
Contents 
Motivation
Graphs corresponding to vision problems tend to have repetitive structure. If the structure is known a priori, maxflow implementations can take advantage and save on memory and processing time. For example, a fully general maxflow implementation must explicitly store connectivity of each arc:
struct Arc { int residual_capacity; Node* head; Arc* reverse; Arc* next; }; struct Node { Arc* outgoing_arcs; ... // algorithmspecific stuff };
whereas a specialised implementation for graphics/vision can represent all connectivity with a single 'neighbourhood' definition. This neighbourhood structure is assumed to repeat at each grid location. Graph storage structures can therefore be simplified, such as
struct Node { int terminal_residual_capacity; // represents capacity from/to source/sink int outgoing_residual_capacity[4]; // assume 4 outgoing arcs at every vertex ... // algorithmspecific stuff };
This type of optimisation is particularly important on dense graphs and when pointers take 8 bytes (64bit addressing).
We define conventions regulargrid
, complexgrid
and capacityhint
for providing hints to a maxflow implementation. The conventions are DIMACS comments, and do not affect the DIMACS format itself (i.e. general maxflow solvers can still parse the file).
The regulargrid convention for DIMACS
The simplest example of a repetitive graph structure in vision is the nearestneighbour grid graph illustrated in 2D below. The source and sink are shown as connected to the lattice from outside.



The above 4x4 lattice might correspond to the pixel arrangement in an image of width and height 4. Problems in vision may require a neighbourhood of larger degree (8connected, 16connected), larger dimension (3D, 4D) or both.
The structure of a Ddimensional grid graph instance can be characterized by:
 integers defining grid size with vertices, and
 nonzero offsets defining arc connectivity repeated at each vertex.
To define a problem instance, we need up to NM positive arc capacities between neighbours in the lattice, plus up to 2N capacities between vertices from/to s / t.
Example. A 2D nearestneighbor problem instance (all capacities 100) can be expressed in a DIMACS file by:
c Example 4x4 nearestneighbour grid graph instance. 16+2 nodes, and 48+2 arcs p max 18 50 n 1 s n 2 t c The next comment lines specify a 4x4, 4connected 2D grid structure. The c next 16 vertex ids (3..18) become reserved for this 4x4 grid in raster order. c regulargrid 4 4 c (1, 0) c (+1, 0) c ( 0,1) c ( 0,+1) a 1 3 100 a 18 2 100 a 3 4 100 a 4 3 100 a 4 5 100 a 5 4 100 ...
The complexgrid convention for DIMACS
Some computer vision problems demand graphs with a complicated but still repetitive structure. For example, quadratic pseudoboolean optimisation (QPBO) suggests a graph construction with two vertices per variable.
Graphs with dense higherorder cliques might be defined by the structure below (3cliques).
In multiview reconstruction problems, graphs corresponding to the dual of a cell complex are used to partition a space such that a binary vertex labeling corresponds to a contour/surface.


The three examples above have one thing in common: translational symmetry with respect to some 'local structure'. In particular, the translational symmetry aligns with grid axes. That means that there is a local structure that is repeated in each grid dimension independently.
The structure of an Ddimensional repeatable graph instance can be characterized by:
 the number k of internal vertices,
 integers defining a grid with vertices
 pairs identifying tail and head vertex of each arc, and
 offsets that, with the u_{i},v_{i}, define arc connectivity repeated at each vertex.
To avoid loops, if any then . Notice that when k = 1 this scheme reduces to the regulargrid
specification from earlier.
To define a problem instance, we need up to NM positive arc capacities between neighbours in the lattice, plus up to 2kN capacities between vertices from/to s / t.
Example. The 4x1 QPBO structure above could be specified in a DIMACS file by:
c A 4x1 QPBO example. 1 and 2 denote the top/bottom cell vertex. The next c 8 vertex ids become reserved for this (2x)4x1 grid in raster order. c complexgrid 2 4 c 1, 2, ( 0) c 2, 1, ( 0) c 1, 1, (+1) c 1, 2, (+1) c 2, 1, (+1) c 2, 2, (+1) c 1, 1, (1) c 1, 2, (1) c 2, 1, (1) c 2, 2, (1)
The capacityhint convention for DIMACS
Most of the perarc memory usage of a general maxflow implementations is dedicated to pointer storage (see motivation above). In contrast, a specialised implementation's memory usage is often proportial to the storage type of residual capacities. In many computer vision applications, small integers are adequate in the problem formulation. If capacities are at most 127 (and therefore residual capacities are at most 254), an implementation that can use unsigned char
internally instead of unsigned
will only need a fraction of the memory.
Example. This DIMACS comment is a hint to the implementation that any general arc capacities that follow (including those from/to s / t) are at most 1000, and regular arc capacities that follow, defined by subsequent regulargrid
/complexgrid
, are at most 100:
c capacityhint 1000 100
Boundary arcs: how to interpret arcs that 'leave' the grid
Since there are boundaries to the grid, arcs that 'leave' the grid should be considered to 'wrap'. For example, arcs with 2D offset (1,0) at the leftmost column should be connected to vertices in the rightmost column, and vice versa for offset (1,0). This type of connectivity is illustrated below, and is important for some graph constructions (surface of tori, repeating video).
If this is type of connectivity is not desired, set these boundary arc capacities to zero.
Mixing general graphs & grid graphs
If a DIMACS file specifies positive capacity for arcs that are not part of the repeatable structure (nor between s / t) then the problem instance is not fully regular/complex representable.
Though difficult to implement, there are reasons for wanting more generality than just a repeatable grid graph structure:
 Graphs with high regularity, but with sparse structures 'fused' onto the grid (e.g. higher order cliques, long range constraints).
 Graphs comprising a number of regular grid graphs, connected with each other in a nonregular way (e.g. random level graphs, reconstruction from multiple 2D images, etc).
When confronted with a DIMACS file that specifies both regular and nonregular graph structures, behaviour is implementationspecific. A maxflow implementation could...
 Construct the full graph with full performance benefits for the regular components (presumably via dark magic/voodoo).
 Fall back to a fully general implementation (no benefits of regularity).
 Fail completely.