(*
11.2    Digraph - Sequential Bounded Managed Iterator

In this section we provide the implementation module corresponding to
the interface given above in 11.1. The following scheme is used in
organizing this section:
* 11.2.1  Internal Representation
* 11.2.2  Exception Handling
* 11.2.3  Local Routines
* 11.2.4  Graph Constructors
* 11.2.5  Vertex Constructors
* 11.2.6  Edge Constructors
* 11.2.7  Graph Selectors
* 11.2.8  Vertex Selectors
* 11.2.9  Edge Selectors
* 11.2.10 Passive Iterators
* 11.2.11 Active Iterators
* 11.2.12 Module Initialization
*)

IMPLEMENTATION MODULE DigrSBMI;
(*==============================================================
    Version  : V2.01  08 December 1989.
    Compiler : JPI TopSpeed Modula-2
    Code size: 6300 bytes
    Component: Digraph - Sequential Bounded Managed Iterator

    THE ABSTRACTION
    This module provides interface definitions for the directed,
        bounded, unmanaged, iterator graph abstract data type.

    REVISION HISTORY
    v1.00  26 May 1988  C. Lins:
        Initial TML Modula-2 implementation
    v1.01  11-14 Jan 1989  C. Lins:
        Revised interface in conformance with new graph spec (Ch 9).
        Changed implementation to represent vertex abstractly.
    v1.02  10 Apr 1989  C. Lins:
          Corrected initialization of handlers array.
    v1.03  18 Apr 1989   C. Lins:
          Added component id constant.
    v2.00  24 Oct 1989  C. Lins
          Created generic pc version
    v2.01  08 Dec 1989  I.S.C. Houston.
          Adapted to JPI Compiler:
          Used type transfer functions instead of VAL.
          Used shortened library module names for DOS and OS/2.

        (C) Copyright 1989 Charles A. Lins
==============================================================*)

FROM SYSTEM IMPORT
        (*--type*) ADDRESS,
        (*--proc*) ADR;

FROM JPIStorage IMPORT
        (*--proc*) Allocate, Deallocate;

FROM Items IMPORT
        (*--cons*) NullItem,
        (*--type*) Item, AssignProc, DisposeProc;

FROM GraphTypes IMPORT
        (*--type*) Operations, Exceptions, ComponentID;

FROM ErrorHandling IMPORT
        (*--cons*) NullHandler,
        (*--type*) HandlerProc,
        (*--proc*) Raise;

FROM TypeManager IMPORT
        (*--cons*) NullType,
        (*--type*) TypeID,
        (*--proc*) AssignOf, DisposeOf;

        (*-------------------------*)

(*
11.2.1  Internal Representation

The internal representation for a bounded digraph is similar to that used in
the previous chapter for its unbounded counterpart. The main difference is in
the adjacency list representation. We still have a singly linked list
of vertices, the difference being that the list is stored in an array of
vertex nodes. Thus, a Vertex could be represented using an array index. This
was not done for several reasons:
        1. because the TML Modula-2 compiler prohibits redefinition of an
           opaque type as equal to an already defined type (TYPE Vertex = CARDINAL
           is flagged as an error);
        2. making the definition of Vertex transparent in the Definition Module
           exposes to clients an aspect of the implementation (violating information
           hiding principles); and
        3. transformation of the unbounded form into the bounded form, as was done
           here, is facilitated by taking another approach.

The approach used in this module takes advantage of the fact than an element
of an array can be accessed through its ADDRESS. So internally the module can
use indices into the adjacency list where necessary while still maintaining
an abstract presentation to client modules.

This organization is shown below in Figure 11.1.

Figure 11.1

Edge:                   completes the opaque definition as a reference to a dynamically
                                allocated edge node.

Vertex:                 completes the opaque definition as the address of a vertex node
                                in the adjacency list array.

VertexNode:             defines the information requirements for a single vertex of a
                                graph.
        data:           contains the label data item associated with a vertex.
        next:           index of the next vertex in the set of vertices for a graph. The
                                last vertex of the list has a 'next' of 0 indicating
                                the end of the list.
        edges:          link to the first directed edge leaving this vertex. If the vertex
                                has no edges leaving it, this field is set to the NullEdge.
        indegree:       is used in maintaining a count of the number of edges having this
                                vertex as its destination excluding self-loops (which are edges
                                whose source and destination vertices are the same). This count
                                is maintained by the constructors Link, Unlink and Assign. It
                                is used by the constructor Remove in detecting attempts to
                                delete vertices referenced as the destination of an edge. Since
                                the alternative technique for detecting this precondition is
                                a complete traversal of all the edges of a graph, we have chosen
                                to record this information incrementally as edges are inserted
                                and removed from the graph.
        inGraph:        contains the reference to the enclosing graph object for the vertex.
                                This avoids having the graph as a parameter to the vertex selectors.
                                In addition, simplifying the membership test between a vertex and a
                                graph, as well as the membership test for edges (through the
                                initial or final vertex references of the edge).

EdgeNode:               defines the information requirements for a single edge of a graph.
        initial:        contains a reference to the initial (or source) vertex of the edge.
        final:          contains a reference to the final (or destination) vertex of the edge.
        weight:         contains the attribute of the edge.
        next:           contains the link to the next edge leaving the initial vertex.
                                The last edge of this list contains the NullEdge as its value
                                indicating the end of the list.

UnboundedGraph: describes (and holds) attributes of the graph itself.
        labelType,
        attrType:       contain the data type ID for the vertex label and edge attribute,
                                respectively. These two fields are used to retrieve the procedures
                                accomplishing assignment and disposal of data items.
        numVertices,
        numEdges:       contain counts of the total number of vertices and edges in the
                                graph, respectively. Thus, the selectors OrderOf and SizeOf are
                                O(1) algorithms instead of O(|V|) or O(|E|).
        firstVertex: index of the first vertex in the adjacency list for a graph.
        available:      index of the first available vertex in the adjacency list of a graph.
        vertices:       the adjacency list of vertices. When a graph is initially created
                                the array is sized based on the maximum number of vertices desired. So
                                while the upper bound on the VertexIndex is MaxVertex elements, the
                                actual size of the array will be something less than this.
*)

TYPE  Vertex = POINTER TO VertexNode;
TYPE  Edge   = POINTER TO EdgeNode;

TYPE  VertexNode = RECORD
                inGraph : Graph;        (*-- graph in which this vertex is a member *)
                data    : Label;        (*-- data item (label) for this vertex *)
                indegree: CARDINAL; (*-- # of edges ending at this vertex *)
                next    : CARDINAL;     (*-- next vertex in adjacency list *)
                edges   : Edge;         (*-- link to first edge leaving this vertex *)
          END (*-- VertexNode *);

TYPE  EdgeNode = RECORD
                initial : Vertex;       (*-- source vertex for this edge *)
                final   : Vertex;       (*-- destination vertex for this edge *)
                weight  : Attribute;(*-- weight/attribute for this edge *)
                next    : Edge;         (*-- next edge leaving this vertex *)
          END (*-- EdgeNode *);

CONST MaxVertex = 2000;
TYPE  VertexIndex = [1 .. MaxVertex];
TYPE  AdjList = ARRAY VertexIndex OF VertexNode;

TYPE  BoundedGraph = RECORD
                labelType  : TypeID;    (*-- vertex label data type ID *)
                attrType   : TypeID;    (*-- edge attribute data type ID *)
                maxVertices: CARDINAL;  (*-- maximum number of vertices *)
                numVertices: CARDINAL;  (*-- current number of vertices *)
                numEdges   : CARDINAL;  (*-- current number of edges *)
                firstVertex: CARDINAL;  (*-- 1st vertex in adjacency list *)
                available  : CARDINAL;  (*-- 1st free vertex in adjacency list *)
                vertices   : AdjList;   (*-- adjacency list of vertices *)
          END (*-- BoundedGraph *);

TYPE  Graph = POINTER TO BoundedGraph;

        (*-------------------------*)

(*
11.2.2  Exception Handling

graphError holds the exception result from the most recently
invoked operation of this module. The Exceptions enumeration
constant noerr indicates successful completion of the operation and
all operations that may raise an exception assign this value to
graphError before any other processing.

The handlers array holds the current exception handler for the
possible exceptions that may be raised from within this module.

Both are initialized by the module initialization (see 10.3.12).

GraphError      simply returns the current exception result stored
                        in graphError and is used to determine whether a graph
                        operation completed successfully.

SetHandler      makes theHandler the current exception handler for theError
                        by storing theHandler in the handler array.

GetHandler      returns the current exception handler for theError from the
                        handler array.
*)

VAR   graphError : Exceptions;
VAR   handlers   : ARRAY Exceptions OF HandlerProc;

PROCEDURE GraphError () : Exceptions               (*--out  *);
BEGIN
  RETURN graphError;
END GraphError;
(*-------------------------*)

PROCEDURE SetHandler (    theError   : Exceptions  (*--in   *);
                                                  theHandler : HandlerProc (*--in   *));
BEGIN
  handlers[theError] := theHandler;
END SetHandler;
(*-------------------------*)

PROCEDURE GetHandler (    theError   : Exceptions  (*--in   *))
                                                                         : HandlerProc (*--out  *);
BEGIN
  RETURN handlers[theError];
END GetHandler;
(*-------------------------*)

PROCEDURE RaiseErrIn (    theRoutine : Operations  (*--in   *);
                                                  theError   : Exceptions  (*--in   *));
BEGIN
  graphError := theError;
  Raise(ComponentID + ModuleID, theRoutine, theError, handlers[theError]);
END RaiseErrIn;
(*-------------------------*)

(*
11.2.3  Local Routines

FreeAttribute is responsible for retrieval of the edge attribute item disposal
routine and freeing the attribute when no longer needed. This occurs when
        1. a graph is cleared or destroyed (Clear);
        2. an edge is removed from a graph (Unlink);
        3. a vertex is removed from a graph and any edges leaving it are implicitly
           removed (ClearEdges); or
        4. a new attribute is assigned to an edge (SetAttribute).
Complexity: O(1).
*)

PROCEDURE FreeAttribute (    theEdge : Edge (*--inout*));

VAR   free : DisposeProc; (*-- attribute disposal routine, if any *)

BEGIN
  WITH theEdge^ DO
        free := DisposeOf(initial^.inGraph^.attrType);
        free(weight);
  END (*--with*);
END FreeAttribute;
(*-------------------------*)

(*
FreeLabel corresponds to FreeAttribute, above, for the clean-up of vertex labels
when they are no longer needed. The conditions are similar to those above:
        1. a graph is cleared or destroyed (Clear);
        2. an vertex is removed from a graph (Remove); or
        3. a new label is assigned to a vertex (SetLabel).
Complexity: O(1).
*)

PROCEDURE FreeLabel (    theVertex : Vertex (*--inout*));

VAR   free : DisposeProc; (*-- label disposal routine, if any *)

BEGIN
  WITH theVertex^ DO
        free := DisposeOf(inGraph^.labelType);
        free(data);
  END (*--with*);
END FreeLabel;
(*-------------------------*)

(*
InitVertex initializes a single vertex for the free list. O(1)
InitFreeList initializes the free list of available vertices. The free list
of vertices is initialized when a graph is created or when a graph is cleared
of its contents. O(s), where s is the size of the bounded array of vertices.
*)

PROCEDURE InitFreeList (VAR theGraph : Graph      (*--inout*));

  PROCEDURE InitVertex   (VAR theNode  : VertexNode (*--inout*);
                                                          theNext  : CARDINAL   (*--in   *));
  BEGIN
    WITH theNode DO
          inGraph  := theGraph;
          data     := NullItem;
          indegree := 0;
          next     := theNext;
          edges    := NullEdge;
    END (*--with*);
  END InitVertex;

VAR   v : VertexIndex; (*-- running index over vertices of the graph *)

BEGIN
  WITH theGraph^ DO
    FOR v := MIN(VertexIndex) TO maxVertices-1 DO
          InitVertex(vertices[v], v+1);
        END (*--for*);
        InitVertex(vertices[maxVertices], 0);
        numVertices := 0;
        firstVertex := 0;
        available   := MIN(VertexIndex);
  END (*--with*);
END InitFreeList;
(*-------------------------*)

(*
ClearEdges removes all edges leaving a given vertex. This is necessary when
        1. a graph is cleared or destroyed (Clear); or
        2. a vertex is removed from a graph (Remove).
Essentially, the algorithm loops over each edge in the edge list for the vertex
removing the edge from the list, updating the number of edges in the graph,
deallocation of the edge attribute and, finally, deallocation of the edge itself.
Since we guarantee the last edge in the list has a 'next' of NullEdge, 'edges'
(the vertex's link to the first edge) is properly set to the NullEdge upon
completion of the routine. O(outdegree(v)).
*)

PROCEDURE ClearEdges    (    theVertex: Vertex   (*--inout*));

VAR   theEdge : Edge;            (*-- edge to be removed *)

BEGIN
  WITH theVertex^ DO
        WHILE (edges # NullEdge) DO
          theEdge := edges;
          edges := edges^.next;
          DEC(inGraph^.numEdges);
          FreeAttribute(theEdge);
          Deallocate(theEdge, SIZE(theEdge^));
        END (*--while*);
  END (*--with*);
END ClearEdges;
(*-------------------------*)

(*
NewEdge simple creates a new edge with the specified vertex endpoints and weight.
The edge is not added to any edge list, leaving this to the caller. The overflow
exception is automatically raised, if necessary, when a new edge node cannot be
allocated. The structural sharing of the edge attribute is controlled, as described
above for NewVertex, using a similar mechanism. Complexity O(1).
*)

PROCEDURE NewEdge (    fromVertex : Vertex     (*--in   *);
                                           toVertex   : Vertex     (*--in   *);
                                           theWeight  : Attribute  (*--in   *);
                                           theRoutine : Operations (*--in   *))
                                                                  : Edge           (*--out  *);

VAR   theEdge : Edge;   (*-- newly created edge *)

BEGIN
  Allocate(theEdge, SIZE(EdgeNode));
  IF (theEdge = NullEdge) THEN
    RaiseErrIn(theRoutine, overflow);
  ELSE
    WITH theEdge^ DO
          initial := fromVertex;
          final   := toVertex;
          weight  := theWeight;
          next    := NullEdge;
    END (*--with*);
  END (*--if*);
  RETURN theEdge;
END NewEdge;
(*-------------------------*)


(*
11.2.4  Graph Constructors

Create attempts to form a new, empty graph object with the given maximum
number of vertices (theSize) and vertex label and edge label data types.
First, the graph descriptor is allocated, the free list of vertices is
initialized, and the vertex and edge data type IDs are stored in the graph
descriptor. The number of vertices and edges are initialized to zero.
If the descriptor allocation fails the overflow exception is raised and the
NullGraph is returned, otherwise we return the newly allocated graph.
Complexity O(theSize) due to the initialization of the free list of vertices.
*)

CONST baseSize = SIZE(BoundedGraph) - SIZE(AdjList);
CONST nodeSize = SIZE(VertexNode);

PROCEDURE Create   (    labels     : TypeID    (*--in   *);
                                            attributes : TypeID    (*--in   *);
                                            theSize    : CARDINAL  (*--in   *))
                                                                   : Graph     (*--out  *);

VAR   newGraph : Graph; (*-- temporary for new graph object *)

BEGIN
  graphError := noerr;
  Allocate(newGraph, baseSize + (VAL(INTEGER, theSize) * nodeSize));
  IF (newGraph = NullGraph) THEN
    RaiseErrIn(create, overflow);
  ELSE
    WITH newGraph^ DO
          labelType   := labels;
          attrType    := attributes;
          maxVertices := theSize;
          numEdges    := 0;
        END (*--with*);
        InitFreeList(newGraph);
  END (*--if*);
  RETURN newGraph;
END Create;
(*-------------------------*)

(*
Destroy clears theGraph and then deallocates it making theGraph undefined.
SCLStorage.Deallocate automatically releases the proper amount of space
originally allocated and alters the pointer to NIL (which is also the
value of the NullGraph). Complexity O(v+e).
*)

PROCEDURE Destroy (VAR theGraph      : Graph     (*--inout*));
BEGIN
  Clear(theGraph);
  IF (graphError = noerr) THEN
    Deallocate(theGraph, baseSize + (theGraph^.maxVertices * nodeSize));
  END (*--if*);
END Destroy;
(*-------------------------*)

(*
Clear removes all vertices and edges from theGraph making theGraph empty.
We do this by iterating over each of the vertices and clearing all edges
leaving the vertex (ClearEdges). As a final step we ensure that the graph is left in the
empty state by resetting the head of the adjacency list to NIL and the number
of vertices and edges in the graph to zero. The free list of available
vertices is also reinitialized. Complexity O(v+e).
*)

PROCEDURE Clear   (VAR theGraph      : Graph    (*--inout*));

VAR   theVertex : CARDINAL;        (*-- loop index over vertices *)

BEGIN
  graphError := noerr;
  IF (theGraph = NullGraph) THEN
    RaiseErrIn(clear, undefined);
  ELSE
    WITH theGraph^ DO
          theVertex  := firstVertex;
          WHILE (theVertex # 0) DO
            ClearEdges(ADR(vertices[theVertex]));
                FreeLabel(ADR(vertices[theVertex]));
                theVertex := vertices[theVertex].next;
          END (*--for*);
        END (*--with*);
        InitFreeList(theGraph);
  END (*--if*);
END Clear;
(*-------------------------*)

(*
Assign copies the source graph, theGraph, to the target graph, toGraph. The
main body of Assign does this by first copying all the vertices followed by
copying all the edges from the source to the destination graph.
The algorithmic complexity is O(v^2+e) due to the mapping between the vertices
of the source and target graphs while copying the edges (see the discussion
of the vertexMap following RecreateTarget).
*)

PROCEDURE Assign  (    theGraph      : Graph     (*--in   *);
                                   VAR toGraph       : Graph     (*--inout*));

(*
RecreateTarget reconstructs the target graph descriptor so that the fields
defining the vertex label and edge attribute data types,
and (optionally) maximum number of vertices between the
source and destination graphs are the same. If the source and destination
graphs are the same the routine returns FALSE indicating that the postconditions
for the assignment operation are already met.
The routine returns TRUE if the recreation of the target was successful.
Complexity O(v+e) where v and e are the number of vertices and
edges, respectively, in the original toGraph.  When Clearing the target graph
is unnecessary (the toGraph is initially the NullGraph) the complexity falls
to O(1)..
*)

  PROCEDURE RecreateTarget (): BOOLEAN (*--out  *);
  BEGIN
        IF (theGraph = NullGraph) THEN
      RaiseErrIn(assign, undefined);

        ELSIF (toGraph = NullGraph) THEN
      WITH theGraph^ DO
        toGraph := Create(labelType, attrType, maxVertices);
          END (*--with*);

        ELSIF (theGraph = toGraph) THEN
      RETURN FALSE;

        ELSIF (theGraph^.numVertices > toGraph^.maxVertices) THEN
          RaiseErrIn(assign, overflow);

        ELSE
          Clear(toGraph);
      WITH theGraph^ DO
                toGraph^.labelType := labelType;
                toGraph^.attrType  := attrType;
          END (*--with*);
        END (*--if*);
        RETURN (graphError = noerr);
  END RecreateTarget;

(*
One thorny issue in graph assignment is how to set-up the copied edges with the
proper initial and final vertices? The edges of the source graph contain references
to the source graph's vertices, not those of the target graph. The vertex
labels cannot be used since more than one vertex can have the same label. In
this case, an edge from the second (or greater) such vertex in the target graph
would be linked incorrectly to the first vertex having that label. The solution
is in having some form of temporary mapping from the source graph's vertices to
their counterpart in the target graph. The necessary operations are add a mapping
between a vertex from the source graph and its corresponding vertex in the
target graph, and given a source graph vertex return the target graph vertex
mapped to that source vertex.

The data structure implementing our vertex mapping is an unordered array of mapping
entries, one per vertex, between the vertices of the source graph and the
target graph. This array is dynamically created on the heap based on the
number of vertices in the source graph. (The ARRAY [0..0] OF ≡ construct is
a special feature of the TML Modula-2 compiler allowing dynamic arrays.) The
variable mapExtent controls where MapVertex entries are inserted into the
array. A post-increment scheme is used so mapVertex is always one greater than
the number of entries stored in the array.
*)

  TYPE  MapVertex = RECORD
              old : Vertex; (*-- vertex from source graph *)
              new : Vertex; (*-- corresponging vertex in target graph *)
            END (*--MapVertex*);
  TYPE  MapVertices = ARRAY [0..0] OF MapVertex;

  VAR   vertexMap : POINTER TO MapVertices;
  VAR   mapExtent : CARDINAL;


(*
CreateVertexMap allocates a dynamic array of vertex mapping entries on the
heap based on the number of vertices in the source graph. vertexMap is set to
NIL by Allocate if there isn't enough memory available to meet the request.
*)

  PROCEDURE CreateVertexMap;
  BEGIN
        Allocate(vertexMap,
                         VAL(CARDINAL, SIZE(MapVertex)) * theGraph^.numVertices);
        mapExtent := 0;
  END CreateVertexMap;

(*
AddVertexToMap adds a mapping between the vertices of the source and target graphs.
*)

  PROCEDURE AddToVertexMap (    oldVertex : Vertex (*--in   *);
                                                                newVertex : Vertex (*--in   *));
  BEGIN
        WITH vertexMap^[mapExtent] DO
          old := oldVertex;
          new := newVertex;
        END (*--with*);
    INC(mapExtent);
  END AddToVertexMap;

(*
VertexInMap returns the mapping between the vertices of the source and target
graphs. Since every vertex is represented failure to find a mapping is
indicative of either a programming error in CopyVertices or a hardware/system
software error at runtime.
*)

  PROCEDURE VertexInMap (    oldVertex : Vertex (*--in   *))
                                                                           : Vertex (*--out  *);

  VAR   index : CARDINAL;

  BEGIN
    FOR index := 0 TO mapExtent-1 DO
          WITH vertexMap^[index] DO
        IF (oldVertex = old) THEN
                  RETURN new;
                END (*--if*);
          END (*--with*);
    END (*--for*);
        RETURN NullVertex;
  END VertexInMap;

(*
DestroyVertexMap frees up the memory used by the vertexMap when the Assign
operation is complete. Remember that Deallocate automatically
releases the proper amount of space.
*)

  PROCEDURE DestroyVertexMap;
  BEGIN
        Deallocate(vertexMap, SIZE(vertexMap^));
  END DestroyVertexMap;

(*
CopyVertices duplicates the vertices from the source graph to the destination
graph returning TRUE if every vertex was successfully copied and FALSE otherwise.
This BOOLEAN result is used by the main body of Assign to control whether to
continue with the Assign operation by copying the edges. The following local
variables are used:
        1. v:                   indicates the current vertex being copied from the source
                                        graph. This is also used as a 'loop index' over the vertices
                                        from the source graph.
        2. newVertex:   temporary for a new vertex for the destination graph.
        3. lastVertex:  last vertex inserted into the destination graph. This is
                                        used by TailInsert to add a new vertex to the end of the
                                        destination graph's adjacency list.
        4. assignItem:  vertex label assignment routine.

Assignment of the vertex label presents an interesting situation. When a vertex
is added to a graph, the client module expects the given label to be copied using
the Modula-2 assignment statement (even for dynamically allocated data items)
since we simply need to store the value in the vertex object. This is known as
'structural sharing'. But when a graph is duplicated using Assign, new copies
of the vertex labels are necessary - avoiding the problems presented by structural
sharing of dynamically allocated items as described in Volume 1. CopyVertices
resolves this through the assignment procedure associated with the graph's label
data type duplicating the label as a NewVertex is created. Complexity O(v) where
v is the number of vertices in the source graph.
*)

  PROCEDURE CopyVertices () : BOOLEAN;

  VAR   v : CARDINAL;   (*--loop index over vertices being copied *)
  VAR   theVertex : CARDINAL; (*-- index to new vertex *)
  VAR   lastVertex: CARDINAL; (*--last vertex added to list of vertices *)
  VAR   assignItem: AssignProc;

(*
TailInsert adds newVertex to the end of the target graph's adjacency list
given pointers to the first and last elements of the list. Complexity O(1).
*)

    PROCEDURE TailInsert (VAR first : CARDINAL (*--inout *);
                                                  VAR last  : CARDINAL (*--inout *));
    BEGIN
      IF (first = 0) THEN
            first := theVertex;
          ELSE
            toGraph^.vertices[last].next := theVertex;
          END (*--if*);
          last := theVertex;
    END TailInsert;

  BEGIN
        CreateVertexMap;
        IF (vertexMap = NIL) THEN
          RETURN FALSE;
        END (*--if*);

        assignItem := AssignOf(theGraph^.labelType);
        v := theGraph^.firstVertex;
        lastVertex := 0;

    WHILE (v # 0) DO
          WITH toGraph^ DO
            theVertex := available;
            available := vertices[available].next;

            WITH vertices[theVertex] DO
              inGraph  := toGraph;
                  data     := assignItem(theGraph^.vertices[v].data);
                  indegree := theGraph^.vertices[v].indegree;
                  next     := 0;
                  edges    := NullEdge;
            END (*--with*);

            TailInsert(firstVertex, lastVertex);
            INC(numVertices);
            AddToVertexMap(ADR(theGraph^.vertices[v]),
                                           ADR(vertices[theVertex]));
          END (*--with*);
          v := theGraph^.vertices[v].next;
        END (*--while*);

        RETURN TRUE;
  END CopyVertices;


(*
CopyEdges iterates over the edges of the source graph through the adjacency
list of vertices and the edge lists for each vertex. As each edge in the
source graph is encountered, a new edge is constructed in the target graph.
This edge is then added to the target graph's vertex equivalent to the edges'
initial vertex. The initial and final vertices of the new edge are retrieved
from the vertex map created by CopyVertices. Note that NewEdge will raise the
overflow exception if necessary.

The following local variables are used:
        v:                      indicates the current vertex from the source graph whose
                                edges are being copied. This is also used as a 'loop index'
                                over the vertices of the source graph.
        e:                      indicates the current edge of the source graph being copied.
                                Also used as a 'loop index' over the edges leaving each
                                vertex, v.
        fromVertex: the vertex of the target graph corresponding to 'v' in the
                                source graph. Since all edges leaving any given vertex, v,
                                have have 'v' as their initial vertex, fromVertex can be
                                derived from the current vertex of the source graph rather than
                                repeatedly retrieving it from the initial vertex of the edge.
        newEdge:        temporary for a new edge in the target graph.
        lastEdge:       last edge inserted into the edge list of the current vertex
                                (fromVertex) destination graph. This is used by TailInsert
                                to add a new edge to the end of fromVertex's edge list.
        assignItem:     edge attribute assignment routine.

So while the basic loop over the edges is linear with respect to the number of
edges, the linear search of the vertex map nested within the loop over the
source graph's vertices gives this algorithm time complexity O(v^2). A better
mapping algorithm (i.e, one of constant time O(1)) would yield a linear time
algorithm overall for the graph assignment.
*)

  PROCEDURE CopyEdges;

  VAR   v : CARDINAL;             (*--loop index over vertices *)
  VAR   e : Edge;                 (*--loop index over edges being copied *)
  VAR   fromVertex: Vertex;   (*--vertex in target graph *)
  VAR   newEdge   : Edge;         (*--new edge for target graph *)
  VAR   lastEdge  : Edge;         (*--last edge inserted into new list of edges *)
  VAR   assignItem: AssignProc; (*--attribute assignment procedure *)

(*
TailInsert adds newEdge to the end of the edge list given pointers to the first
and last elements of the list. Complexity O(1)
*)

    PROCEDURE TailInsert (VAR first   : Edge (*--inout*);
                                                  VAR last    : Edge (*--inout*));
    BEGIN
      IF (first = NullEdge) THEN
            first := newEdge;
          ELSE
            last^.next := newEdge;
          END (*--if*);
          last := newEdge;
    END TailInsert;

  BEGIN
        assignItem := AssignOf(theGraph^.attrType);
        v := theGraph^.firstVertex;
    WHILE (v # 0) DO
          lastEdge := NullEdge;
          WITH theGraph^ DO
            e := vertices[v].edges;
            fromVertex := VertexInMap(ADR(vertices[v]));
          END (*--with*);
          WHILE (e # NullEdge) DO
            newEdge := NewEdge(fromVertex,
                                                   VertexInMap(e^.final),
                                                   assignItem(e^.weight),
                                                   assign);
                IF (newEdge = NullEdge) THEN
                  RETURN;
                END (*--if*);

                TailInsert(fromVertex^.edges, lastEdge);
                INC(toGraph^.numEdges);
                e := e^.next;
          END (*--while*);
          v := theGraph^.vertices[v].next;
        END (*--while*);
  END CopyEdges;

BEGIN (*-- Assign --*)
  graphError := noerr;
  IF RecreateTarget() & CopyVertices() THEN
        CopyEdges;
        DestroyVertexMap;
  END (*--if*);
END Assign;
(*-------------------------*)

(*
11.2.5  Vertex Constructors

Insert adds a vertex to the given graph labeling the vertex with the
given item.  If there are no available vertices in the free list the
overflow exception is raised and the Insert operation aborted. Complexity O(1).
*)

PROCEDURE Insert   (VAR theGraph   : Graph     (*--inout*);
                                        theItem    : Label     (*--in   *);
                                        VAR theVertex  : Vertex    (*--out  *));

VAR   theIndex : CARDINAL; (*-- vertex index into the adjacency list *)

BEGIN
  graphError := noerr;
  theVertex  := NullVertex;

  IF (theGraph = NullGraph) THEN
    RaiseErrIn(insert, undefined);
  ELSIF (theGraph^.available = 0) THEN
    RaiseErrIn(insert, overflow);
  ELSE
    WITH theGraph^ DO
          theIndex := available;
          available := vertices[available].next;
          WITH vertices[theIndex] DO
            inGraph  := theGraph;
                data     := theItem;
                indegree := 0;
                next     := firstVertex;
                edges    := NullEdge;
          END (*--with*);
          firstVertex := theIndex;
          INC(numVertices);
          theVertex := ADR(vertices[theIndex]);
        END (*--with*);
  END (*--if*);
END Insert;
(*-------------------------*)

(*
Remove deletes the given vertex from the specified graph. If no such vertex
can be found in the graph the novertex exception is raised and the routine
aborted. Deleting a vertex that is the head of an edge would leave dangling
edges (pointing to a non-existent vertex), and so, if the vertex is referenced
by an edge (other than a self-loop) the exception references is raised and
Remove is aborted. After we have checked that no exceptions can occur we remove
all edges leaving the vertex, remove the vertex from the adjacency list,
release any dynamically allocated memory used by the vertex label, release the
vertex itself, and update the count of vertices in the graph. Complexity
O(v).
*)

PROCEDURE Remove   (VAR theGraph   : Graph     (*--inout*);
                                    VAR theVertex  : Vertex    (*--inout*));

VAR   theIndex   : CARDINAL; (*-- of theItem to be removed *)
VAR   priorVertex: CARDINAL; (*-- immediate predecessor of theVertex *)

BEGIN
  graphError := noerr;
  IF (theGraph = NullGraph) THEN
    RaiseErrIn(remove, undefined);

  ELSIF (theVertex = NullVertex) THEN
    RaiseErrIn(remove, nullvertex);

  ELSIF (theVertex^.inGraph # theGraph) THEN
    RaiseErrIn(remove, novertex);

  ELSIF (theVertex^.indegree > 0) THEN
        RaiseErrIn(remove, referenced);

  ELSE
        ClearEdges(theVertex);
        FreeLabel(theVertex);

    WITH theGraph^ DO

(*
The following loop searches for the given vertex in the adjacency list array
keeping track of the array index of theVertex's predecessor. This is used
immediately after the loop to update the singly-linked list of vertices for the graph.
*)
      theIndex  := firstVertex;
          priorVertex := 0;
          WHILE (ADR(vertices[theIndex]) # theVertex) DO
            priorVertex := theIndex;
            theIndex    := vertices[theIndex].next;
          END (*--while*);

(*
Remove the vertex from the adjacency list.
*)
          IF (priorVertex = 0) THEN
                firstVertex := vertices[theIndex].next;
          ELSE
                vertices[priorVertex].next := vertices[theIndex].next;
          END (*--if*);

(*
Update the graph component by adding the deleted vertex to the available list and the
count of the number of vertices in the graph. Ensure that the vertex is no longer a
valid member of the graph by clearing the vertexes reference to its enclosing graph.
*)
          vertices[theIndex].next := available;
          vertices[theIndex].inGraph := NullGraph;
          available := theIndex;
          DEC(numVertices);
        END (*--with*);
        theVertex := NullVertex;
  END (*--if*);
END Remove;
(*-------------------------*)

(*
SetLabel assigns a new label to the given vertex of the graph. Prior to
assigning a new vertex label we must release any dynamically allocated memory
used by the old vertex label. Complexity O(1).
*)

PROCEDURE SetLabel (    theVertex  : Vertex    (*--inout*);
                                            theItem    : Label     (*--in   *));
BEGIN
  graphError := noerr;
  IF (theVertex = NullVertex) THEN
    RaiseErrIn(setlabel, nullvertex);
  ELSE
        FreeLabel(theVertex);
    theVertex^.data := theItem;
  END (*--if*);
END SetLabel;
(*-------------------------*)

(*
11.2.6  Edge Constructors

Link adds a directed edge between the from and to vertices labeling the
edge with the given weight attribute. The new edge is linked to the front
of the fromVertex's edge list. Thus, edges appear in reverse order to their
order of insertion. Complexity O(1).
*)

PROCEDURE Link     (VAR theGraph   : Graph     (*--inout*);
                                        fromVertex : Vertex    (*--in   *);
                                        toVertex   : Vertex    (*--in   *);
                                        theWeight  : Attribute (*--in   *);
                                        VAR theEdge    : Edge      (*--out  *));
BEGIN
  graphError := noerr;
  theEdge    := NullEdge;

  IF (theGraph = NullGraph) THEN
    RaiseErrIn(link, undefined);
  ELSIF (fromVertex = NullVertex) OR (toVertex = NullVertex) THEN
    RaiseErrIn(link, nullvertex);
  ELSIF (fromVertex^.inGraph # theGraph) OR
                (toVertex^.inGraph # theGraph) THEN
    RaiseErrIn(link, novertex);
  ELSE

    theEdge := NewEdge(fromVertex, toVertex, theWeight, link);
        IF (theEdge # NullEdge) THEN
          theEdge^.next := fromVertex^.edges;
          fromVertex^.edges := theEdge;
          IF (fromVertex # toVertex) THEN
                INC(toVertex^.indegree);
          END (*--if*);
          INC(theGraph^.numEdges);
        END (*--with*);
  END (*--if*);
END Link;
(*-------------------------*)

(*
Unlink removes a directed edge between the two vertices, fromVertex and
toVertex. Complexity O(d) where d is the out-degree of the fromVertex.
*)

PROCEDURE Unlink   (VAR theGraph   : Graph     (*--inout*);
                                    VAR theEdge    : Edge      (*--inout*));

VAR   e : Edge;   (*-- pointer to edge (v,w), if any *)
VAR   f : Edge;   (*-- pointer to edge preceeding (v,w) in adjacency list *)

BEGIN
  graphError := noerr;

  IF (theGraph = NullGraph) THEN
    RaiseErrIn(unlink, undefined);

  ELSIF (theEdge = NullEdge) THEN
        RaiseErrIn(unlink, nulledge);

  ELSIF (theEdge^.initial^.inGraph # theGraph) THEN
    RaiseErrIn(unlink, noedge);

  ELSE

(*
The following loop searches for the edge being removed in the list of edges
associated with the edges' initial vertex. In addition, we need the prior
edge in the list for the actual deletion of the edge from the list. This is
a standard singly-linked list technique for the deletion of list nodes.
This loop is guaranteed to succeed as Link ensures that the edge is placed in
the initial vertex's list of edges. Complexity O(outdegree(v)).
*)
        e := theEdge^.initial^.edges;
        f := NullEdge;
        WHILE (e # theEdge) DO
          f := e;
          e := e^.next;
        END (*--while*);

        WITH theEdge^ DO

(*
Update the edge list of the initial vertex by removing the edge.
*)
          IF (f = NullEdge) THEN
            initial^.edges := next;
          ELSE
            f^.next := next;
          END (*--if*);

(*
Self-loops are not included in the final vertex's indegree count since such
edges may be freely unlinked and do not effect the removal of the vertex. In
any case, we must maintain the proper count of edges in the graph. As a final
step, the edge attribute and the edge itself may be deallocated. To prevent
clients from successfully accessing copies of an edge, the 'initial' and 'next'
fields are set to empty (and illegal) values. This prevents any copies from
being considered legal edges of the graph even though they have been deleted.
*)
          IF (initial # final) THEN
            DEC(final^.indegree);
          END (*--if*);
          DEC(initial^.inGraph^.numEdges);

      FreeAttribute(theEdge);
          initial := NullVertex;
          next    := NullEdge;
          Deallocate(theEdge, SIZE(theEdge^));
        END (*--with*);
  END (*--if*);
END Unlink;
(*-------------------------*)

(*
SetAttribute assigns a new edge labelling to the given edge. Prior to assigning
a new edge attribute we must release any dynamically allocated memory
used by the old edge attribute. Complexity O(1).
*)

PROCEDURE SetAttribute  (    theEdge    : Edge      (*--inout*);
                                             theWeight  : Attribute (*--in   *));
BEGIN
  graphError := noerr;
  IF (theEdge = NullEdge) THEN
        RaiseErrIn(setattr, nulledge);
  ELSE
    FreeAttribute(theEdge);
    theEdge^.weight := theWeight;
  END (*--if*);
END SetAttribute;
(*-------------------------*)

(*
11.2.7  Graph Selectors

IsDefined verifies to the best of its ability whether theGraph has been
created and is still an active object. Complexity: O(1).
*)

PROCEDURE IsDefined (    theGraph  : Graph       (*--in   *))
                                                                   : BOOLEAN     (*--out  *);
BEGIN
  RETURN (theGraph # NullGraph);
END IsDefined;
(*-------------------------*)

(*
IsEmpty returns True if theGraph is in the empty state, as indicated by
the number of vertices being zero, and False otherwise.  As per the
specification (û9.3) undefined graphs are considered empty. Complexity: O(1).
*)

PROCEDURE IsEmpty   (    theGraph  : Graph       (*--in   *))
                                                                   : BOOLEAN     (*--out  *);
BEGIN
  graphError := noerr;
  IF (theGraph = NullGraph) THEN
    RaiseErrIn(isempty, undefined);
        RETURN TRUE;
  END (*--if*);
  RETURN theGraph^.numVertices = 0;
END IsEmpty;
(*-------------------------*)

(*
TypeOf simply returns the vertex label and edge attribute data type IDs for
the given graph. Undefined graphs, as always, raise the undefined exception
and return a reasonable value, in this case the NullType. Complexity O(1).
*)

PROCEDURE TypeOf    (    theGraph  : Graph       (*--in   *);
                                         VAR labelType : TypeID      (*--out  *);
                                         VAR attrType  : TypeID      (*--out  *));
BEGIN
  graphError := noerr;
  IF (theGraph = NullGraph) THEN
    RaiseErrIn(typeof, undefined);
        labelType := NullType;
        attrType  := NullType;
  ELSE
        labelType := theGraph^.labelType;
        attrType  := theGraph^.attrType;
  END (*--if*);
END TypeOf;
(*-------------------------*)

(*
OrderOf returns the number of vertices in the graph, or zero for an undefined
graph. Complexity O(1).
*)

PROCEDURE OrderOf   (    theGraph  : Graph       (*--in   *))
                                                                   : CARDINAL    (*--out  *);
BEGIN
  graphError := noerr;
  IF (theGraph = NullGraph) THEN
    RaiseErrIn(orderof, undefined);
        RETURN 0;
  END (*--if*);
  RETURN theGraph^.numVertices;
END OrderOf;
(*-------------------------*)

(*
OrderOf returns the number of edges in the graph, or zero for an undefined
graph. Complexity O(1).
*)

PROCEDURE SizeOf    (    theGraph  : Graph       (*--in   *))
                                                                   : CARDINAL    (*--out  *);
BEGIN
  graphError := noerr;
  IF (theGraph = NullGraph) THEN
    RaiseErrIn(sizeof, undefined);
        RETURN 0;
  END (*--if*);
  RETURN theGraph^.numEdges;
END SizeOf;
(*-------------------------*)

(*
MaxOrderOf retuens the maximum number of vertices for the given graph, or zero
for an undefined graph. Essentially, this is the maximum size of the list of
vertices (both used and available). Complexity O(1).
*)

PROCEDURE MaxOrderOf (    theGraph  : Graph       (*--in   *))
                                                                    : CARDINAL    (*--out  *);
BEGIN
  graphError := noerr;
  IF (theGraph = NullGraph) THEN
    RaiseErrIn(maxorderof, undefined);
        RETURN 0;
  END (*--if*);
  RETURN theGraph^.maxVertices;
END MaxOrderOf;
(*-------------------------*)

(*
11.2.8  Vertex Selectors

InDegree returns the number of edges entering the given vertex. Complexity O(1).
*)

PROCEDURE InDegree  (    theVertex : Vertex      (*--in   *))
                                                                   : CARDINAL    (*--out  *);
BEGIN
  graphError := noerr;
  IF (theVertex = NullVertex) THEN
    RaiseErrIn(indegree, nullvertex);
  ELSE
    RETURN theVertex^.indegree;
  END (*--if*);
  RETURN 0;
END InDegree;
(*-------------------------*)

(*
OutDegree returns the number of edges leaving the given vertex. We do this by
simply iterating over the edges of the vertex counting them along the way.
Complexity O(outdegree(v)).
*)

PROCEDURE OutDegree (    theVertex : Vertex      (*--in   *))
                                                                   : CARDINAL    (*--out  *);

VAR   theEdge   : Edge;         (*-- loop index over edges of the vertex *)
VAR   edgeCount : CARDINAL; (*-- running count of edges leaving this vertex *)

BEGIN
  graphError := noerr;
  edgeCount  := 0;

  IF (theVertex = NullVertex) THEN
    RaiseErrIn(outdegree, nullvertex);
  ELSE
    theEdge := theVertex^.edges;
        WHILE (theEdge # NullEdge) DO
          INC(edgeCount);
          theEdge := theEdge^.next;
        END (*--while*);
  END (*--if*);

  RETURN edgeCount;
END OutDegree;
(*-------------------------*)

(*
LabelOf returns the vertex label associated with the given vertex.
If the vertex is undefined the NullItem is returned. Complexity O(1).
Complexity O(1).
*)

PROCEDURE LabelOf   (    theVertex : Vertex      (*--in   *))
                                                                   : Label       (*--out  *);
BEGIN
  graphError := noerr;
  IF (theVertex = NullVertex) THEN
    RaiseErrIn(labelof, nullvertex);
  ELSE
    RETURN theVertex^.data;
  END (*--if*);
  RETURN NullItem;
END LabelOf;
(*-------------------------*)

(*
Since we have stored a copy of the graph object associated with each vertex
as a field of the vertex itself, IsVertex simply needs to compare the given
graph with its own local state. This saves us from having to search the graph.
Complexity O(1).
*)

PROCEDURE IsVertex  (    theGraph  : Graph       (*--in   *);
                                             theVertex : Vertex      (*--in   *))
                                                           : BOOLEAN     (*--out  *);
BEGIN
  graphError := noerr;
  IF (theGraph = NullGraph) THEN
    RaiseErrIn(isvertex, undefined);
  ELSIF (theVertex = NullVertex) THEN
    RaiseErrIn(isvertex, nullvertex);
  ELSE
    RETURN theVertex^.inGraph = theGraph;
  END (*--if*);
  RETURN FALSE;
END IsVertex;
(*-------------------------*)

(*
GraphOf simply returns its copy of the enclosing graph or the NullGraph if the
vertex is undefined. Complexity O(1).
*)

PROCEDURE GraphOf   (    theVertex : Vertex      (*--in   *))
                                                                   : Graph       (*--out  *);
BEGIN
  graphError := noerr;
  IF (theVertex = NullVertex) THEN
    RaiseErrIn(graphof, nullvertex);
  ELSE
    RETURN theVertex^.inGraph;
  END (*--if*);
  RETURN NullGraph;
END GraphOf;
(*-------------------------*)

(*
11.2.9  Edge Selectors

AttributeOf returns the edge attribute associated with the given edge.
If the edge is undefined the NullItem is returned. Complexity O(1).
*)

PROCEDURE AttributeOf (    theEdge   : Edge        (*--in   *))
                                                                 : Attribute   (*--out  *);
BEGIN
  graphError := noerr;
  IF (theEdge = NullEdge) THEN
    RaiseErrIn(attrof, nulledge);
  ELSE
    RETURN theEdge^.weight;
  END (*--if*);
  RETURN NullItem;
END AttributeOf;
(*-------------------------*)

(*
Given an edge, InitialOf returns the vertex that is the origin of
the directed edge or the NullVertex if the edge is undefined. Complexity O(1).
*)

PROCEDURE InitialOf   (    theEdge   : Edge        (*--in   *))
                                                                 : Vertex      (*--out  *);
BEGIN
  graphError := noerr;
  IF (theEdge = NullEdge) THEN
    RaiseErrIn(initialof, nulledge);
  ELSE
    RETURN theEdge^.initial;
  END (*--if*);
  RETURN NullVertex;
END InitialOf;
(*-------------------------*)

(*
Given an edge, FinalOf returns the vertex that is the destination of
the directed edge or the NullVertex if the edge is undefined. Complexity O(1).
*)

PROCEDURE FinalOf     (    theEdge   : Edge        (*--in   *))
                                                                 : Vertex      (*--out  *);
BEGIN
  graphError := noerr;
  IF (theEdge = NullEdge) THEN
    RaiseErrIn(finalof, nulledge);
  ELSE
    RETURN theEdge^.final;
  END (*--if*);
  RETURN NullVertex;
END FinalOf;
(*-------------------------*)

(*
IsEdge returns true if there the given directed edge is an edge of the given
graph and false otherwise. An advantage of having each vertex identify its
enclosing graph object is use of this field in testing whether the edge is
part of a specified graph. This saves use from having to search every edge in
the graph. Complexity O(1).
*)

PROCEDURE IsEdge      (    theGraph  : Graph       (*--in   *);
                                               theEdge   : Edge        (*--in   *))
                                                             : BOOLEAN     (*--out  *);
BEGIN
  graphError := noerr;
  IF (theGraph = NullGraph) THEN
    RaiseErrIn(isedge, undefined);
  ELSIF (theEdge = NullEdge) THEN
    RaiseErrIn(isedge, nulledge);
  ELSIF (theEdge^.initial = NullVertex) THEN
    RaiseErrIn(isedge, nullvertex);
  ELSE
    RETURN theEdge^.initial^.inGraph = theGraph;
  END (*--if*);
  RETURN FALSE;
END IsEdge;
(*-------------------------*)

(*
11.2.10 Passive Iterators

LoopVertices simply iterates over the vertices of the given graph until every
vertex has been examined or the process procedure parameter returns FALSE,
whichever occurs first. Complexity O(v).
*)

PROCEDURE LoopVertices (    theGraph  : Graph          (*--in   *);
                                                        process   : VertexLoopProc (*--in   *));

VAR   theIndex : CARDINAL; (*--loop index over vertices *)

BEGIN
  graphError := noerr;
  IF (theGraph = NullGraph) THEN
    RaiseErrIn(loopvertices, undefined);
  ELSE
    WITH theGraph^ DO
          theIndex := firstVertex;
          WHILE (theIndex # 0) & process(ADR(vertices[theIndex])) DO
            theIndex := vertices[theIndex].next;
          END (*--while*);
        END (*--with*);
  END (*--if*);
END LoopVertices;
(*-------------------------*)

(*
LoopEdges loops over the vertices of the given graph to access the edges associated
with each vertex. Once the process procedure parameter returns FALSE, we exit
both WHILE statements through the use of a RETURN which exits the procedure.
Complexity O(v+e), though the v component will dominate the equation if v >> e.
*)

PROCEDURE LoopEdges    (    theGraph  : Graph          (*--in   *);
                                                        process   : EdgeLoopProc   (*--in   *));

VAR   theIndex  : CARDINAL; (*--loop index over vertices *)
VAR   theEdge   : Edge;   (*--loop index over edges of a vertex *)

BEGIN
  graphError := noerr;
  IF (theGraph = NullGraph) THEN
    RaiseErrIn(loopedges, undefined);
  ELSE
    WITH theGraph^ DO
          theIndex := firstVertex;
          WHILE (theIndex # 0) DO
            theEdge := vertices[theIndex].edges;
            WHILE (theEdge # NullEdge) DO
              IF ~process(theEdge) THEN
                    RETURN;
                  END (*--if*);
                  theEdge := theEdge^.next;
            END (*--while*);
            theIndex := vertices[theIndex].next;
          END (*--with*);
        END (*--while*);
  END (*--if*);
END LoopEdges;
(*-------------------------*)

(*
LoopIterate simply loops over the edges leaving a specified vertex. Complexity
O(outdegree(v)).
*)

PROCEDURE LoopIterate  (    theVertex : Vertex         (*--in   *);
                                                        process   : EdgeLoopProc   (*--in   *));

VAR   theEdge : Edge;   (*--loop index over edges of the vertex *)

BEGIN
  graphError := noerr;
  IF (theVertex = NullVertex) THEN
    RaiseErrIn(loopiterate, nullvertex);
  ELSE
        theEdge := theVertex^.edges;
        WHILE (theEdge # NullEdge) & process(theEdge) DO
          theEdge := theEdge^.next;
        END (*--while*);
  END (*--if*);
END LoopIterate;
(*-------------------------*)

(*
TravVertices simply iterates over every vertex in the graph. Complexity O(v).
*)

PROCEDURE TravVertices (    theGraph  : Graph      (*--in   *);
                                                        process   : VertexProc (*--in   *));

VAR   v : CARDINAL; (*-- loop index over vertices *)

BEGIN
  graphError := noerr;
  IF (theGraph = NullGraph) THEN
    RaiseErrIn(travvertices, undefined);
  ELSE
    WITH theGraph^ DO
          v := firstVertex;
          WHILE (v # 0) DO
            process(ADR(vertices[v]));
                v := vertices[v].next;
          END (*--while*);
        END (*--with*);
  END (*--if*);
END TravVertices;
(*-------------------------*)

(*
TravEdges simply iterates over every edge in the graph. Since the only way
to get at all the edges is through the vertices, we iterate over all the
vertices and over each edge leaving each vertex. Complexity O(v+e).
*)

PROCEDURE TravEdges    (    theGraph  : Graph      (*--in   *);
                                                        process   : EdgeProc   (*--in   *));

VAR   v : CARDINAL; (*-- loop index over vertices *)
VAR   e : Edge;         (*-- loop index over edges of a vertex *)

BEGIN
  graphError := noerr;
  IF (theGraph = NullGraph) THEN
    RaiseErrIn(travedges, undefined);
  ELSE
    WITH theGraph^ DO
          v := firstVertex;
          WHILE (v # 0) DO
                e := vertices[v].edges;
                WHILE (e # NullEdge) DO
              process(e);
                  e := e^.next;
                END (*--while*);
                v := vertices[v].next;
          END (*--while*);
        END (*--with*);
  END (*--if*);
END TravEdges;
(*-------------------------*)

(*
Iterate simply loops over the edges leaving a specified vertex of a graph.
Complexity O(outdegree(v)).
*)

PROCEDURE Iterate      (    theVertex : Vertex     (*--in   *);
                                                        process   : EdgeProc   (*--in   *));

VAR   theEdge : Edge;   (*-- loop index over edges of the vertex *)

BEGIN
  graphError := noerr;
  IF (theVertex = NullVertex) THEN
    RaiseErrIn(iterate, nullvertex);
  ELSE
        theEdge := theVertex^.edges;
        WHILE (theEdge # NullEdge) DO
          process(theEdge);
          theEdge := theEdge^.next;
        END (*--while*);
  END (*--if*);
END Iterate;
(*-------------------------*)

(*
11.2.11 Active Iterators

Each of the active iterators are essentially selectors for the underlying
representation of the adjacency list. FirstVertex returns the abstract vertex
corresponding to the first vertex in the graph's adjacency list. NextVertex
returns the abstract vertex that is the successor to the given vertex in the
graph's adjacency list. FirstEdge returns the edge at the head of the vertexes
list of edges emanating from the given vertex. NextEdge returns the edge
immediately following the given edge in a previosuly given vertexes edge list.
The algorithmic complexity of all four routines is O(1).
*)

PROCEDURE FirstVertex  (    theGraph  : Graph      (*--in   *))
                                                                          : Vertex     (*--out  *);
BEGIN
  graphError := noerr;
  IF (theGraph = NullGraph) THEN
    RaiseErrIn(firstvertex, undefined);
  ELSE
        RETURN ADR(theGraph^.vertices[theGraph^.firstVertex]);
  END (*--if*);
  RETURN NullVertex;
END FirstVertex;
(*-------------------------*)

PROCEDURE NextVertex   (    theVertex : Vertex     (*--in   *))
                                                                          : Vertex     (*--out  *);
BEGIN
  graphError := noerr;
  IF (theVertex = NullVertex) THEN
    RaiseErrIn(nextvertex, nullvertex);
  ELSE
        WITH theVertex^ DO
          IF (next # 0) THEN
                RETURN ADR(inGraph^.vertices[next]);
          END (*--if*);
        END (*--with*);
  END (*--if*);
  RETURN NullVertex;
END NextVertex;
(*-------------------------*)

PROCEDURE FirstEdge    (    theVertex : Vertex     (*--in   *))
                                                                          : Edge       (*--out  *);
BEGIN
  graphError := noerr;
  IF (theVertex = NullVertex) THEN
    RaiseErrIn(firstedge, nullvertex);
  ELSE
    RETURN theVertex^.edges;
  END (*--if*);
  RETURN NullEdge;
END FirstEdge;
(*-------------------------*)

PROCEDURE NextEdge     (    theEdge   : Edge       (*--in   *))
                                                                          : Edge       (*--out  *);
BEGIN
  graphError := noerr;
  IF (theEdge = NullEdge) THEN
    RaiseErrIn(nextedge, nulledge);
  ELSE
    RETURN theEdge^.next;
  END (*--if*);
  RETURN NullEdge;
END NextEdge;
(*-------------------------*)

(*
11.2.12 Module Initialization

The module's local variables are initialized to known states.
graphError is used to fill the handlers array with a routine
that does nothing when an exception is raised (saving the
declaration of a special loop control variable for this purpose).
Applying MIN and MAX to cover all exceptions ensures that this initialization
will be unaffected by any future changes to the number of Exceptions
or their order of declaration within the enumeration.  Since a FOR loop
control variable is undefined following the loop, graphError must be
set to indicate that an error has not yet occurred.
*)

BEGIN
  FOR graphError := MIN(Exceptions) TO MAX(Exceptions) DO
    SetHandler(graphError, NullHandler);
  END (*--for*);
  SetHandler(noerr, NullHandler);
  graphError := noerr;
        NullGraph := NIL;
        NullVertex := NIL;
        NullEdge := NIL;
END DigrSBMI.