Maximum Flow Problem Format

Maximum flow problems are in DIMACS format. See Network Flows and Matching: First DIMACS Implementation Challenge, D. S. Johnson and C. C. McGeoch (editors), AMS, 1993.

Network Structure

A network is a directed graph with n nodes and m arcs.
Nodes are identified by integers 1...n.
Graphs do not have to be symmetric: if an arc (v,w) is in the graph, the reverse arc (w,v) does not have to be in the graph.
Parallel arcs are not allowed.
Self-loops are not allowed.
Arc capacities are 32-bit signed integers.
The source and the sink are distinct.
The sink may be unreachable from the source.

Input Format

Input can be either a file or a stream. By convention, maxflow problem file names should have the suffix .max. Here is a sample file: sample.max.

Problem input consists of ASCII characters.
The input consists of several types of lines>.
Each line begins with a one-character line type designator.
Line fields are separated by at least one blank space.
Each line ends with an end-of-line character.
Line types are as follows. In the format descriptions below, bold characters should appear exactly as typed.
- Comment lines. These lines begin with a lower-case character c and can appear anywhere. Comment lines are ignored by programs.
  c This is a comment.
- Problem line. The problem line is unique and must appear as the first non-comment line. This line has the following format:
  p max n m
  where n and m are the number of nodes and the number of arcs, respectively.
- Node descriptors. Node descriptors are of the form
  n ID WHICH
  where ID is the node id and WHICH is s for the source and t for the sink. Two node descriptors, one for the source and one for the sink, must appear between the problem line and the arc descriptor lines.
- Acr descriptors. Acr descriptors are of the form
  a SRC DST CAP
  where SRC and DST are the tail and the head node ids, respectively, and CAP is the arc capacity.

Output Format

The following output format should be used to produce a complete solution in ASCII. In some cases complete solutions are useful. Note, however, that a maxflow problem can have several optimal solutions. In regular testing, the value of the maximum flow is often sufficient. Some application need minimum cuts rather than maximum flows. When a solver is incorporated in a program, the communication is usually performed at the data structure level. Here is a sample file: sample.sol. Solution line types are as follows.

Comment lines. Same as in the input case.
Solution line. The solution line contains the maximum flow value and has the following format:
s VALUE
Flow assignments. There is one flow assignment line for each arc in the input network. These lines have the following format:
f SRC DST FLOW
where SRC, DST, and FLOW are arc tail, head, and flow value, respectively.