2006_02_22 BH2.1_2006  Slight modifications of BH2.1_2002 to allow compilation with g++3.4.4.
BH2.1_2002 will compile with g++ versions thru at least 3.2.


Here is some preliminary documentation.

We have implemented Bestvina-Handel algorithm for the
punctured disk. The code has been written in a way that
will readily permit generalizaton to other punctured surfaces.

We have followed the paper "Train Tracks for Surface Homeomorphisms"
(Topology, 34,109-140, 1995) closely, except in step 6, where if
a folding occurs we return to the top of the main loop, since
folding can cause Lemma 4.2.1 to cease to be satisfied.
Secondly we have inserted an additional check for reducibility
to catch some reducible cases missed by original algorithm.
(See bottom of this document.)

We are very eager to hear of, and fix, any bugs you detect.
Please send bug reports to ringland@acsu.buffalo.edu.

Please also send mail to ringland@acsu.buffalo.edu if
you would like to be informed about bugs, bug fixes,
and other updates. Otherwise, it would be advisable to check
this page again soon, since changes are certain to be
made over the next week or so as testing continues.

The code can be compiled successfully using the current
native C++ compilers (CC) of Sun and Silicon Graphics.
(The Gnu compiler (g++) will not work because of the way
it implements templates.)

--------------------------------------------------------------------

A homeomorphism class of the punctured disk is characterized as
in the following example.

Edges: { 1 2 3 4 5 6 }
Periphery: { 1 2 3 }
Punctures: { 7 8 9 }
Graph: { < 1 -1 -4 > < 2 -2 -5 > < 3 -3 -6 > < 4 5 6 > }
Map: { 
  1 -> ( 3 ) 
  2 -> ( 1 ) 
  3 -> ( 2 ) 
  4 -> ( 4 1 -4 5 2 -5 6 ) 
  5 -> ( 4 ) 
  6 -> ( 5 ) 
}
Equator: ( 1 7 -1 2 8 -2 3 9 -3 ) 


The above labels correspond as follows to the terminology of 
the Topology paper. "Edges" is the set of edge names (natural numbers), 
"Periphery" is the peripheral subset thereof, and "Punctures" is the set of 
puncture names (natural numbers not in Edges) (which is used in tracking 
the embedding).  "Graph" is the graph, G, the set of links of the vertices, 
each being the circular list of directed edges originating at a vertex. 
"Map" is the map, g, from the set of directed edges in G to edge paths in G. 
"Equator" is a list of directed edge- (and puncture-) crossings 
of a "thread" that runs through all the punctures, which we
use to keep track of the embedding.

When using the braid-word input mode, the initial graph is a
"bunch of balloons": a circle around each puncture,
each with a single vertex of valence 3, and a single other vertex below 
the "equator".  The equator runs from left to right, and "Equator" lists
the equator-crossings of upward-directed edges.
The link of a vertex is read clockwise.
 
----------------------------------------------------------------------------
To compile the program, simply type

make      

at the Unix prompt.

To run the program, type

stepBH

at the Unix prompt. Then enter either a braid word, such as

(1 2 3 -2 -2)

or enter a characterization of the homeomorphism class in
the format described above and illustrated again below.

Edges: { 1 2 3 4 5 6 7 8 }
Periphery: { 1 2 3 4 }
Punctures: { 9 10 11 12 }
Graph: { < 1 -1 -5 > < 2 -2 -6 > < 3 -3 -7 > < 4 -4 -8 > < 5 6 7 8 > }
Map: { 
  1 -> ( 4 ) 
  2 -> ( 3 ) 
  3 -> ( 1 ) 
  4 -> ( 2 ) 
  5 -> ( 6 -2 -6 5 1 -5 6 2 -6 8 ) 
  6 -> ( 6 -2 -6 5 1 -5 6 2 -6 8 -4 -8 6 -2 -6 5 -1 -5 6 2 -6 5 1 -5 6 2 -6 7 ) 
  7 -> ( 6 -2 -6 5 ) 
  8 -> ( 8 -4 -8 6 -2 -6 5 -1 -5 6 ) 
}
Equator: ( 1 9 -1 2 10 -2 3 11 -3 4 12 -4 ) 


The driver in stepBH.c enables you specify individual moves,
or to run the BH algorithm automatically. (A summary of the 
instruction syntax appears when you run the program.)

It is a simple matter to write drivers for your own purposes.

-----------------------------------------------------------------------------

Additional reducibility check. (5/24/96)

In addition to looking at the matrix M_H, we now check for the
existence of a subgraph of the peripheral subgraph that is
forward and backward invariant. This catches reducible cases such
as

Edges: { 1 2 3 4 5 6 7 8 }
Periphery: { 1 2 3 4 8 }
Punctures: { 9 10 11 12 }
Graph: { < 1 -1 -5 > < 2 -2 -6 > < 3 -3  -7 > < 6 8 -4 5 > < 4 -8 7 > }
Map: {
  5 -> { 5 1 -5 8 7 }
  6 -> { 5 }
  7 -> { 7 -3 -7 -8 6 }
  4 -> { 4 }
  8 -> { 8 }
  3 -> { 2 }
  2 -> { 1 }
  1 -> { 3 }
}
Equator: ( 1 9 -1 2 10 -2 3 11 -3 4 12 -4 )

which were missed by the original formulation.
