The traversal graph construction fits on one page in the paper:
Traversals of Object Structures: Specification and Efficient Implementation.
To read this note,
it is assumed that you have the paper in front of you.
Here is some helpful further information. Think of it as footnotes.

The theme of the paper, regarding algorithms,
is to have a general algorithm for strategy graphs.
The key idea is to base the algorithm on the following fundamental
computation: 

FROM-TO:
Given a graph G with two nodes A and B, find
the subgraph consisting of all edges going from A to B in G.
This computation is done by a forward and a backward depth-first traversal.

During the early stages of Demeter we used the concept of 
a propagation graph: it is a subgraph of the class graph which
defines the legal traversal paths. Unfortunately, the idea
of a propagation graph works only in certain cases (when there are
now shortcuts and no zigzags, see the 1995 TOPLAS paper).

This paper introduces a "big brother" of the propagation graph,
called the traversal graph. The traversal graph is obtained
by a FROM-TO computation on a graph which contains multiple
copies of the class graph to which some edges have been added
and some edges have been deleted.

The traversal graph plays a similar role during traversal
as the propagation graph: it is a guidance device and says
which object parts may be traversed.

After this general description, we give some details on Algorithm 1:

Step 1 one creates  k copies of the class graph where k is the number of
edges in the strategy graph. The motivation is to make sure that the
run-time traverals have enough state information so that they
behave correctly. For those who followed our earlier work,
the class graph copying eliminates the shortcut problem. In earlier
work, instead of copying the class graph k times, we used 
k distinct traversal functions.

Step 2 has the purpose to link the copied class graphs. Each strategy
graph node u is responsible for additional edges in the traversal
graph. In the simplest case, the strategy graph node u has one incoming
and one outgoing edge. In this case one additional edge is added
to the traversal graph going from a node in one copy of the class graph
to a node in another copy of the class graph.
The construction is done through the temporary use of an intercopy edge.
If the name map assigns class C to u then the intercopy edge goes from
a traversal graph node whose class is C to another traversal graph
node whose class is C. Then for any subgraph of the form 

   l
a---->b
 \    |
  \   | intercopy edge
 l \  |
    \ |
     VV
      c

where (a,l,b) is a traversal graph edge and (b,c) a temporary intercopy edge,
we add an new class graph edge (a,l,c).

Step 3 deletes selected edges in a copy of the class graphs. 
This allows us to express which edges or nodes are not allowed to be in 
the desired path set. 

Steps 4 and 5 introduce a temporary source and temporary target node.
The idea is that the path set can be computed by taking all the paths 
from the source to the target node in the traversal graph (using
the FROM-TO computation). Step 5 also introduces Ts and Tf:
the start and finish sets of the traversal graph.

To state the correctness of the algorithm, namely that the 
set of paths in the traversal graph corresponds to the set
of allowed object traversals defined by the strategy, we use
several concepts:

natural correspondance X:
It maps paths in class graphs to paths in object graphs by
omitting abstract classes and subclass edges. This works
since the class graphs are flat! In non-flat class graphs there is
not a one-to-one correspondance between class graph paths and object
graph paths. X is easily extended to paths in the traversal graph.

S(G,N,B):
The set of object paths for some object which is an instance of G.
The paths satisfy the strategy S and constraints B.
(This is a little strange: I view B as a part of the strategy.)

Now lemma 5.1 states that
X(paths in traversal graph from Ts to Tf) = S(G,N,B)

It is very nice that a graph theoretic statement captures
the essence of traversal graphs.