Gary R. Waissi, University of Michigan-Dearborn
School of Management, Room 113FOB, Dearborn, MI 48128
Tel: (313) 593-5012
E-mail: gary_waissi@um.cc.umich.edu
-----------------------------------------------------------
Table of Contents:
1. NETWORK PROBLEM GENERATORS FOR MAX-FLOW;
   Standard Pascal Versions
2. DESCRIPTION OF NETWORK GENERATORS
3. EXAMPLE OUTPUT DATA FILES
-----------------------------------------------------------
Programs:  
Copyright (C) Gary R. Waissi (1990,1991)

Algorithms:
Copyright (C) Gary R. Waissi (1988,1989,1990,1991)

(updated November, 1990, December 1990, January 1991)
-----------------------------------------------------------
1. NETWORK PROBLEM GENERATORS FOR MAX-FLOW;
   Standard Pascal Versions
-----------------------------------------------------------

The Max-Flow Problem
--------------------
In a maximum flow problem the total flow from a specified
source node to a specified sink is maximized, while 
satisfying flow feasibility and flow conservation 
constraints, as follows:
        
    MAX  SUM f(i,j) over all arcs (i,j) in A

    where f(i,j) = flow on arc (i,j)
          A      = set of arcs in the network

The Network Generators
----------------------
The programs generate max-flow networks in five network
categories; acyclic, bipartite, one-way transit grid, 
two-way transit grid, and random.

Standard Pascal Source Files
----------------------------
  ac-max.pas    Acyclic network generator
  bi-max.pas    Bipartite network generator
  tr1-max.pas   Transit grid network generator, one-way
  tr2-max.pas   Transit grid network generator, two-way
  ra-max.pas    Random network generator

These source programs have been given to public domain
through The Center for Discrete Mathematics and Theoretical
Computer Science (DIMACS), Rutgers University. The programs
are designed for maximum flow applications. All programs
are written in standard Pascal for portability.

Data file formats correspond to DIMACS data file
specifications described in "The First DIMACS International
Algorithm Implementation Challenge: Problem Definitions and
Specifications". Please contact via e-mail:
netflow@dimacs.rutgers.edu

Data File Format
----------------
All the MAX-FLOW networks are given as lists of lines using
the same format. There are four types of lines: comment 
lines c, problem line p, node lines n, arc lines a, as 
follows:

      c This is a comment line. The "p" line gives the 
      c problem type, here MAX (maximization), number of
      c nodes, and number of arcs. There are exactly two
      c "n" lines. The first "n" line lists the source node
      c number, and a lower case letter s designating the
      c source. The second "n" line lists the sink node
      c number, and a lower case c letter t designating
      c the sink. All user input must be in integers.
      c The "a" lines list the arcs, one line per arc with
      c three numbers: Arc tail node, arc head node, arc
      c flow capacity.
      c For example like this:
      p max NODES ARCS
      n NODE WHICH
      a FROM TO CAP
      c where
      c      max   = specifies the max-flow data file
      c      NODES = number of nodes
      c      ARCS  = number of arcs
      c      NODE  = source of sink node number
      c      WHICH = s for a source node, t for a sink node
      c      FROM  = arc tail node number
      c      TO    = arc head node number
      c      CAP   = arc flow capacity

For simplicity the only supply node s is always numbered
with 1, and the only demand node t is assigned the largest
node number. In all cases, where the user is asked for 
a flow capacity bound, the program will generate random
arc flow capacities. All arc flow lower bounds are set 
equal to zero.

The data files are ASCII files, and can be accessed with
a common editor. 


2. DESCRIPTION OF NETWORK GENERATORS

Acyclic Network Generator for Max-Flow
--------------------------------------
Source Files:
ac-max.pas   Standard Pascal Version
Copyright (C) Gary R. Waissi (1990,1991)

The program generates an ACYCLIC MAX-FLOW network into
a user file. An acyclic network is such that for each
arc (i,j), where i is the arc tail node number, and j is 
the arc head node number, i<j.

The program can generate three types of acyclic networks:

    - Fully dense networks with random capacities
    - Fully dense networks with special capacities
    - Special sparse networks with special capacities.

The two key procedures are:

 PROCEDURE AcyclicNet1;
 PROCEDURE AcyclicNet2;

For the FULLY DENSE acyclic networks the user has two
options for arc flow capacities: random or special
capacities. Special arcs capacities are calculated using
the concept of Glover et al. (published in "A Comprehensive
Computer Evaluation and Enhancement of Maximum Flow
Algorithms", Appl. of MS, Vol 3, 1983) as follows:

     1. For all arcs, say (i,j), where j=i+1 the capacity
        CAP(i,j) of the arc (i,j) is

            CAP(i,j) = 1 + (i - n/2)^2
            where n is the number of nodes

     2. For all arcs, say (i,j), where j>i+1 the capacity

            CAP(i,j) = 1.

The networks were called "hard networks" in the study,
because such networks were found to cause max-flow 
algorithms to their worst case performance.

If random capacities are selected for fully dense networks,
then the program wil generate random arc flow capacities
from a range of values between zero and a user specified
value. All non-integer values are truncated to integer 
values to conform with DIMACS specifications.

The special SPARSE acyclic networks are such that each node
is connected by an arc to the next node and to the sink 
node, i.e. there exist two types of arcs: 

     1. (i,j) where j=i+1 for all i and j\t with capacity n

     2. (i,t) for all i\t with capacity 1.

These simple networks cause the Dinic Layered Network
Algorithm (Dinic, E.A., Algorithm for Solution of a Problem
of Maximum Flow in a Network with Power Estimation, Soviet
Math. Dokl. Vol. 11, No. 5, pp. 1277-1280, 1970), to it's
worst case performance. That is, an acyclic network of n
nodes requires always the generation of (n-1) Dinic 
networks for maximum value flow, regardless of the maximal
flow algorithm applied to the Dinic networks. Many max-flow
algorithms use the Dinic Algorithm to generate auxiliary 
acyclic networks from an original network, and find the 
maximal flow in such an acyclic network. These sparse 
acyclic networks were presented in the dissertation of
Gary R. Waissi, "Acyclic Network Generation and Maximal
Flow Algorithms for Single Commodity Flow", University 
of Michigan, 1985.

This program is robust. A generated arc is written to the
disk file, and not stored in the memory. Disk full causes
a run-time error (101).


Bipartite Network Generator for Max-Flow
----------------------------------------
Source File:
bi-max.pas   Standard Pascal Version
Copyright (C) Gary R. Waissi (1990,1991)

The program generates a BIPARTITE MAX-FLOW NETWORK to 
a user specified file. The set of nodes N can be 
partitioned into two sets N1 and N2, such that all arcs
are directed from N1 to N2.

The program generates two types of networks:

    - Bipartite networks with unit capacities on bipartite
      arcs, and random capacities on arcs from the
      SUPER SOURCE and into the SUPER SINK.

    - Bipartite networks with random capacities.

The key procedure is:

PROCEDURE BipartiteNet;

The user selects the number of nodes on the source side
and sink side of the network respectively. The bipartite
network is appended with two nodes, a common source
SUPER SOURCE, and a common sink SUPER SINK. The SUPER
SOURCE is connected by arcs to all nodes in the SOURCE SET,
N1. The nodes in the SINK SET, N2, are connected by arcs
to the SUPER SINK. The SUPER SOURCE is always numbered with
number one, and the SUPER SINK is numbered with the largest
node number.

The user has two options for the arc capacities: either
random capacities or unit capacities. In the case of random
capacities all arcs capacities are random integers between
zero and a user selected upper bound. In the case of unit
capacities all arc capacities connecting the nodes in the
SOURCE SET, N1, to the nodes in the SINK SET, N2, are unit
capacities, i.e the bipartite arcs. However, the arc 
capacities of arcs from the SUPER SOURCE to N1, as well
as, the arc capacities of arcs from N2 to the SUPER SINK,
are random.

This program is robust. A generated arc is written to the
disk file, and not stored in the memory. Disk full causes
a run-time error (101).


Transit Grid Network Generator for Max-Flow/One-Way System
----------------------------------------------------------
Source File:
tr1-max.pas   Standard Pascal Version

Copyright (C) Gary R. Waissi (1990,1991)

This program generates a ONE-WAY TRANSIT GRID NETWORK for
the MAX-FLOW problem into a user specified file with at
most one arc between any pair of nodes.

The program generates one type of networks:
    
   - One-Way Transit-Grid networks with a SUPER SOURCE
     and a SUPER SINK, random arc flow capacities.

The key procedure is:

PROCEDURE TransitOneNet;

The network resembles a one-way city street network. The
direction of each arc, except those connected to the common
source and common sink respectively, is randomly assigned.
The arc flow capacities are randomly assigned from a range
between zero and a user selected value. All arc capacities
are random integers.

Two nodes a SUPER SOURCE and a SUPER SINK are added to the
network automatically. The SUPER SOURCE is connected by 
arcs to nodes on one side of the grid. The nodes on the 
opposite side of the grid are connected to the SUPER SINK. 

The user is suggested to select a number of nodes in the
network, that creates a complete square grid. The program
works, however, for any n>=4.

For example:

      4 nodes in a 2 x 2 network  (smallest)
      9 nodes in a 3 x 3 network
     16 nodes in a 4 x 4 network
     25 nodes in a 5 x 5 network
          ...
   1600 nodes in a 40 x 40 network
          ...
  10000 nodes in a 100 x 100 network.
          ...

This program is robust. A generated arc is written to the
disk file, and not stored in the memory. Disk full causes
a run-time error (101).

Transit Grid Network Generator for Max-Flow/Two-Way System
----------------------------------------------------------
Source File:
tr2-max.pas   Standard Pascal Version

Copyright (C) Gary R. Waissi  (1990,1991)

This program generates a TWO-WAY TRANSIT GRID NETWORK for
the MAX-FLOW problem into a user specified file with two
arcs between any pair of nodes forming the grid.

The program generates one type of networks:
    
   - Two-Way Transit-Grid networks with a SUPER SOURCE
     and a SUPER SINK, random arc flow capacities.

The key procedure is:

PROCEDURE TransitTwoNet;

The network resembles a two-way city street network. There
are two arcs, one in each direction, between the nodes 
forming the grid. The arc flow capacities are randomly 
assigned from a range between zero and a user selected 
value. 

Two nodes a SUPER SOURCE and a SUPER SINK are added to
the network automatically. The SUPER SOURCE is connected
by two arcs, one in each direction, to nodes on one side of
the grid. The nodes on the opposite side of the grid are
connected by two arcs, one in each direction, to the SUPER
SINK. 

The user is suggested to select a number of nodes in the
network, that creates a complete square grid. The program
works, however, for any n>=4.

For example:

      4 nodes in a 2 x 2 network  (smallest)
      9 nodes in a 3 x 3 network
     16 nodes in a 4 x 4 network
     25 nodes in a 5 x 5 network
          ...
   1600 nodes in a 40 x 40 network
          ...
  10000 nodes in a 100 x 100 network.
          ...

This program is robust. A generated arc is written to the
disk file, and not stored in the memory. Disk full causes
a run-time error (101).


RANDOM NETWORK GENERATOR FOR MAX-FLOW
Source File: 
ra-max.pas   Standard Pascal Version
Copyright (C) Gary R. Waissi (1990,1991)

This program generates a RANDOM MAX-FLOW network into
a user file. The network is generated by randomly pairing
a given number of nodes using a given number of arcs.

The program generates one type of networks:

    - Random networks with random arc flow capacities.

The key procedure is:

PROCEDURE RandomNet;

The maximum number of arcs in a fully dense network cannot
exceed n^2-n. Duplicate arcs and self-loops are not allowed.

This program generates initially a BALANCED ARC TREE to 
store network arcs. This arc tree is temporarily maintained
and manipulated in the RAM. The size of the tree is 
determined by the number of arcs in the random network
selected by the user. The program then generates a pair
of random numbers, say (i,j). This pair of numbers 
represents an arc (i,j) with node i as the arc origin and
node j as the arc destination. The balanced tree is then 
searched to determine, if this arc (i,j) is already 
included in the tree (network). If the pair of numbers
is found, another pair is generated and the search is 
repeated. The process is repeated until the tree (network)
is complete, i.e. the required number of arcs is generated.
The resulting network may be a connected or disconnected
network.

When the network is completed, i.e. the arc tree is filled
with arcs (random pairs of numbers), the network is written
to a file.

Two types of run-time errors may occur:

   101 Disk write error, if the disk becomes full.
   203 Heap overflow error. Each dynamic variable 
       is stored in the heap by stacking them on the
       top of each other.
       
3. EXAMPLE OUTPUT DATA FILES

EXAMPLE: A Fully Dense Acyclic Network
with Random Arc Capacities

c Fully Dense Acyclic Network
c for Max-Flow
c Arcs with random capacities
p max         5        10
n             1  s
n             5  t
a         1         2         7
a         1         3         3
a         1         4         6
a         1         5         5
a         2         3         5
a         2         4         8
a         2         5         2
a         3         4         7
a         3         5         4
a         4         5         2


EXAMPLE: A Fully Dense Acyclic Network
with Special Arc Capacities; (Glover et al
"Hard Network", but with rounded capacities)

c Fully Dense Acyclic Network
c for Max-Flow
c Arcs with special capacities
p max         5        10
n             1  s
n             5  t
a         1         2         3
a         1         3         1
a         1         4         1
a         1         5         1
a         2         3         1
a         2         4         1
a         2         5         1
a         3         4         1
a         3         5         1
a         4         5         3


EXAMPLE: A Sparse Acyclic Network with Special
Arc Capacities; (Dinic Worst Case Network)

c Sparse Acyclic Network
c for Max-Flow
c Arcs with special capacities
p max         5         7
n             1  s
n             5  t
a         1         2         5
a         1         5         1
a         2         3         5
a         2         5         1
a         3         4         5
a         3         5         1
a         4         5         1


EXAMPLE: A Bipartite Network with Unit Capacities

c Bipartite Network for Max-Flow
c with UNIT capacities on bipartite arcs
p max         8        15
n             1  s
n             8  t
a         1         2        11
a         1         3        25
a         1         4         7
a         2         5         1
a         2         6         1
a         2         7         1
a         3         5         1
a         3         6         1
a         3         7         1
a         4         5         1
a         4         6         1
a         4         7         1
a         5         8        10
a         6         8        15
a         7         8        30


EXAMPLE: A Bipartite Network with Random Capacities

c Bipartite Network for Max-Flow
c with RANDOM capacities
p max         8        15
n             1  s
n             8  t
a         1         2        11
a         1         3        30
a         1         4        22
a         2         5         7
a         2         6         8
a         2         7         4
a         3         5         2
a         3         6        10
a         3         7         2
a         4         5        23
a         4         6        27
a         4         7        27
a         5         8        23
a         6         8        18
a         7         8        19


EXAMPLE: One-Way Transit Grid Network
         Random Arc Capacities

c One-Way Transit Grid Network
c for Max-Flow
p max         6         8
n             1  s
n             6  t
a         1         2         8
a         1         3         5
a         2         3         1
a         2         4         8
a         3         5         9
a         5         4         6
a         4         6        10
a         5         6         5


EXAMPLE: Two-Way Transit Grid Network
         Random Arc Capacities

c Two-Way Transit Grid Network
c for Max-Flow
p max         6        16
n             1  s
n             6  t
a         1         2        10
a         2         1         3
a         1         3         7
a         3         1         1
a         2         3        10
a         3         2         9
a         2         4         7
a         4         2         6
a         3         5         5
a         5         3         3
a         4         5         9
a         5         4         2
a         4         6         5
a         6         4         6
a         5         6         6
a         6         5        10


EXAMPLE: Random Network
         Random Arc Capacities

c Random Network
c for Max-Flow
p max         5        10
n             1  s
n             5  t
a         5         3        30
a         4         2        23
a         3         5        16
a         1         3         7
a         2         4         6
a         4         3         6
a         2         1        25
a         1         4        30
a         4         1        23
a         2         5        18
