 DIMACS NOTE: These files are the original programs written 
		by Gary R. Waissi. They can compile under Turbo Pascal 5.5 
-----------------------------------------------------------
NETWORK PROBLEM GENERATION AND MAXIMUM FLOW

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;Turbo Pascal 5.5 Version
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; 
		Turbo Pascal 5.5 Version

Another version of the Network Problem Generators,
a program package, that uses windowing, and has 
a user-friendly menu interface is available. The version
uses Turbo Pascal 5.5 features (including CTR, DOS), and
is compiled in Turbo Pascal Units TPU's. The program uses
Turbo Pascal 5.5 feature to overlay UNITs to minimize RAM
memory requirements. The program runs on DOS 3.xx and 
latter versions.

Networks will be stored on diskette, or hard-drive,
(default drive) into user specified ASCII files.

The below, see section 3, described five max-flow network
generators are included in the package, and can be invoked
from the menu. The programs are in one 5.25" diskette and
compiled into one program: MXNETGEN.EXE. The program is
compiled from several UNITs. The following files are
included:

 MxNetGen.exe     Executable program
 MxNetGen.pas     Main program
 MxNetGen.ovr     Overlay file

 Crt, Dos         UNITs supplied by the compiler vendor
 Windows.pas      Windowing program
 Windows.obj      Windowing program object code
 Windows.asm      Windowing program assembly source code
 

 AcMaxi.pas       Acyclic network generator
 BiMaxi.pas       Bipartite network generator
 Tr1Maxi.pas      Transit grid (one-way) generator
 Tr2Maxi.pas      Transit grid (two-way) generator
 RaMaxi.pas       Random network generator

 MxiMain.pas      Max-flow solver main program
                  The Max-Flow solver uses data files
                  generated by the above programs.
                  The Max-Flow solver resides in
                  a total of seven files: 

                  MxiMain.pas  Main program
                  MxiSub1.pas  Max-flow algorithm
                  MxiSub2.pas  Network generator
                  MxiSub3.pas  Common procedures
                  MxiSub4.pas  Variable declarations,
                               tree procedures
                  Explain.pas  Help file
                  Example.max  Example data file.

Notes to Compiling the Source Programs
--------------------------------------
You may compile the source programs using the Turbo 
Pascal 5.5. Please note, that you can compile the 
program only to disk, not memory.


2. DESCRIPTION OF NETWORK GENERATORS

Acyclic Network Generator for Max-Flow
--------------------------------------
Source Files:
AcMaxi.pas   Turbo Pascal 5.5 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 Files:
BiMaxi.pas   Turbo Pascal 5.5 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 Files:
Tr1Maxi.pas   Turbo Pascal 5.5 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 Files:
Tr2Maxi.pas   Turbo Pascal 5.5 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
----------------------------------------------------------
RaMaxi.pas   Turbo Pascal 5.5 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.
       
With Turbo Pascal 5.5 the stack, heap minimum and 
heap maximum sizes can be controlled using the M 
compiler option: [ M stacksize,heapmin,heapmax], 
default [ M 16384,0,655360]. See the program source
code for an example use of this compiler option. 

In Turbo Pascal 5.5 the available memory can be tested
using MemAvail and MaxAvail functions (omitted here for
transportability). Please note, that relatively small
networks, a few thousand nodes and arcs, will already 
cause heap overflow.
----------------------------------------------------------

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

