Graph regularity DIMACS conventions

From Computer Vision at Western

Jump to: navigation, search

This page explains conventions for DIMACS files in our downloadable max-flow problem instances in vision. They are essentially 'hints' that do not affect the DIMACS format itself, and are only relevant to specialised max-flow implementations.

Contents

Motivation

Graphs corresponding to vision problems tend to have repetitive structure. If the structure is known a priori, max-flow implementations can take advantage and save on memory and processing time. For example, a fully general max-flow implementation must explicitly store connectivity of each arc:

struct Arc {
   int residual_capacity;
   Node* head;
   Arc*  reverse;
   Arc*  next;
};
struct Node {
   Arc* outgoing_arcs;
   ... // algorithm-specific 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
   ... // algorithm-specific stuff
};

This type of optimisation is particularly important on dense graphs and when pointers take 8 bytes (64-bit addressing).

We define conventions regulargrid, complexgrid and capacityhint for providing hints to a max-flow implementation. The conventions are DIMACS comments, and do not affect the DIMACS format itself (i.e. general max-flow solvers can still parse the file).

The regulargrid convention for DIMACS

The simplest example of a repetitive graph structure in vision is the nearest-neighbour grid graph illustrated in 2D below. The source and sink are shown as connected to the lattice from outside.

2D nearest-neighbour grid graph of degree 1 (4-connected).

Translation symmetry of 4-connected grid graph.

Construct full graph from repeated component.

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 (8-connected, 16-connected), larger dimension (3D, 4D) or both.

The structure of a D-dimensional grid graph instance can be characterized by:

  1. integers n_1,\ldots,n_D defining grid size with N=n_1 \cdots n_D vertices, and
  2. non-zero offsets \mathbf{d}_1,\ldots,\mathbf{d}_M \in \mathbb{Z}^D 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 nearest-neighbor problem instance (all capacities 100) can be expressed in a DIMACS file by:

c Example 4x4 nearest-neighbour 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, 4-connected 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 pseudo-boolean optimisation (QPBO) suggests a graph construction with two vertices per variable.

Graph constructio for quadratic pseudo-boolean optimisation (1D example).

Graphs with dense higher-order cliques might be defined by the structure below (3-cliques).

digraph-representable 3-cliques.

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.

2D nearest-neighbour grid graph of degree 1 (4-connected).

Construct full graph from repeated component.

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 D-dimensional repeatable graph instance can be characterized by:

  1. the number k of internal vertices,
  2. integers n_1,\ldots,n_D defining a grid with N=n_1 \cdots n_D vertices
  3. pairs (u_1,v_1),\ldots,(u_M,v_M) \in \mathbb{Z}_{1 \ldots k}^2 identifying tail and head vertex of each arc, and
  4. offsets \mathbf{d}_1,\ldots,\mathbf{d}_M \in \mathbb{Z}^D that, with the ui,vi, define arc connectivity repeated at each vertex.

To avoid loops, if any \mathbf{d}_i=\mathbf{0} then u_i \neq v_i. 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 per-arc memory usage of a general max-flow 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).

Connectivity wraps at boundaries.

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:

  1. Graphs with high regularity, but with sparse structures 'fused' onto the grid (e.g. higher order cliques, long range constraints).
  2. Graphs comprising a number of regular grid graphs, connected with each other in a non-regular way (e.g. random level graphs, reconstruction from multiple 2D images, etc).

When confronted with a DIMACS file that specifies both regular and non-regular graph structures, behaviour is implementation-specific. A max-flow 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.
Personal tools
Toolbox
hack to reserve spacing for research logo