language-Modula2-0.1: examples/Modula-2_Libraries/C.-Lins_Modula-2_Software_Component_Library/Vol3/GRAPHS/GRAFSBMI.MOD
(*
14.2 Graph - Sequential Bounded Managed Iterator
In this section we provide the implementation module corresponding to
the interface given above in û12.1. The following scheme is used in
organizing this section:
* 14.2.1 Internal Representation
* 14.2.2 Exception Handling
* 14.2.3 Local Routines
* 14.2.4 Graph Constructors
* 14.2.5 Vertex Constructors
* 14.2.6 Edge Constructors
* 14.2.7 Graph Selectors
* 14.2.8 Vertex Selectors
* 14.2.9 Edge Selectors
* 14.2.10 Passive Iterators
* 14.2.11 Active Iterators
* 14.2.12 Module Initialization
*)
IMPLEMENTATION MODULE GrafSBMI;
(*==============================================================
Version : V2.01 08 December 1989.
Compiler : JPI TopSpeed Modula-2
Code size: 7492 bytes
Component: Graph - Sequential Bounded Managed Iterator
REVISION HISTORY
v1.00 17 Feb 1989 C. Lins:
Initial implementation based on unbounded graph module.
v1.01 10 Apr 1989 C. Lins:
Corrected initialization of handlers array.
v1.02 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;
(*-------------------------*)
(*
14.2.1 Internal Representation
The internal representation of an unbounded directed graph uses a variant of the
adjacency list structure used in Chapter 10 for the directed graph (shown below
in Figure 12.1). In this representation, the set of vertices for a graph is given
by a linear list. Since a bounded graph has a fixed number of vertices (maximum)
the module manages its own 'heap' of vertex nodes. This heap is hidden from
clients through the opaque definition of a vertex as an address which is really
the address of an item in the array.
Secondly, each vertex is associated with the set of undirected edges incident on
the vertex. The set of all edges of the graph is thus the union of all the sets
of edges for each of the graph's vertices.
This is the same conceptual model used in representing the unbounded directed graph
of Chapter 10. In that chapter we were able to easily implement this model directly.
Often, undirected graphs are represented using the directed graph model where each
undirected edge, {v, w}, is presented as two directed edges, (v, w) and (w, v).
Though such an approach could be taken with this implementation, we consider it
unsatisfactory for two reasons:
1. iteration over the edges would cause each edge to be processed twice making
the implementation structure visible to client modules; and
2. the selector SetAttribute would have to deallocate and assign the weight
attribute in two edge nodes in order to keep them in sync.
The solution used here keeps only a single edge node for each edge while the edge
lists of the vertices contain references to the 'real' edge nodes. These real edges
are stored in a doubly-linked list the head of which is kept in the descriptor of
the graph itself. The edge references are also held in doubly-linked lists and each
vertex has a reference to the head of their list of edges.
_Figure 12.1_
Following the figure is a description of the various TYPEs used for our internal
representation including the component fields of each record structure. One
aspect of this representation that may cause some confusion is that the abstract
edge entity is in reality an edge reference. Since are two of these for each edge,
the reader may wonder which reference is used by client modules for the edge
selectors. This potential problem is resolved by the convention that client modules
are never aware of more than one of the two edge references, the second edge
reference is only used internally. Furthermore, when edges are added to a graph
the reference given back to the client is always for the directed edge reference
(v, w) where v is the first vertex of the pair of vertices to which the edge is
linked.
EdgePtr: defines a reference to a dynamically allocated undirected edge node.
Edge: completes the opaque definition as a reference to a dynamically
allocated directed edge node.
Vertex: completes the opaque definition as a reference to a dynamically
allocated vertex node.
VertexNode: defines the information requirements for a single vertex of a
graph.
data: contains the label data item associated with a vertex.
next: link to the next vertex in the set of vertices for a graph. The
last vertex of the list has a 'next' of NullVertex indicating
the end of the list.
prior: link to the previous vertex in the set of vertices for a graph. The
first vertex of the list has a 'prior' of NullVertex indicating
the front 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.
degree: is used in maintaining a count of the number of edges incident on this
vertex as its destination excluding self-loops (which are edges
whose first and second vertices are the same). This count
is maintained by the constructors Link, Unlink and Assign. It
is used to make the selector DegreeOf an O(1) algorithm instead
of an O(Degree(v)) algorithm. The alternative technique for would be
a complete traversal of all the edges associated with a vertex.
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 an undirected edge of a graph.
first: contains a reference to the first vertex of the edge.
second: contains a reference to the second vertex of the edge.
edgeRef1: contains a reference to the directed edge (first, second) in the
first vertexes edge list corresponding to this undirected edge.
edgeRef2: contains a reference to the directed edge (second, first) in the
second vertexes edge list corresponding to this undirected edge.
weight: contains the attribute of the edge.
next: contains the link to the next edge in the graph.
The last edge of this list contains the NullRef as its value
indicating the end of the list.
prior: contains the link to the prior edge in the linked list of edges
in the graph. The first edge of this list contains the NullRef as
its value indicating the front of the list.
EdgeRefNode: defines the information requirements for a directed edge of a graph.
There are two such nodes for every EdgeNode.
realEdge: contains a reference to the actual undirected edge corresponding
to this directed edge.
next: contains a link to the next directed edge in a vertexes edge list.
The last edge in an edge list contains a value of NullEdge indicating
the end of the list.
prior: contains a link to the previous directed edge in a vertexes edge list.
The first edge in an edge list contains a value of NullEdge indicating
the front 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: reference to the first vertex in the adjacency list for a graph.
firstEdge: reference to the first edge in the set of all edges for a graph.
*)
TYPE EdgePtr = POINTER TO EdgeNode;
TYPE Edge = POINTER TO EdgeRefNode;
TYPE Vertex = POINTER TO VertexNode;
CONST NullRef = NIL;
TYPE EdgeRefNode = RECORD
realEdge : EdgePtr; (*--link to the actual edge node *)
prior : Edge; (*--prior edge in this edge list *)
next : Edge; (*--next edge in this edge list *)
END (*--EdgeRefNode *);
TYPE VertexNode = RECORD
inGraph : Graph; (*--graph in which this vertex is a member *)
data : Label; (*--data item (label) for this vertex *)
degree : CARDINAL;(*--degree of this vertex *)
prior : Vertex; (*--prior vertex in adjacency list *)
next : Vertex; (*--next vertex in adjacency list *)
edges : Edge; (*--link to first edge of this vertex *)
END (*--VertexNode *);
TYPE EdgeNode = RECORD
first : Vertex; (*--first vertex for this edge *)
second : Vertex; (*--second vertex for this edge *)
weight : Attribute;(*--weight/attribute for this edge *)
edgeRef1: Edge; (*--link to edge in 1st vertex edge list *)
edgeRef2: Edge; (*--link to edge in 2nd vertex edge list *)
prior : EdgePtr; (*--prior edge in the set of all edges *)
next : EdgePtr; (*--next edge in the set of all edges *)
END (*--EdgeNode *);
CONST maxVertex = 1480;
TYPE VertexIndex = [1..maxVertex];
TYPE Vertices = 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: Vertex; (*--first vertex in adjacency list *)
available : Vertex; (*--first vertex in available list *)
firstEdge : EdgePtr; (*--first edge in edge set *)
vertices : Vertices; (*--bounded adjacency list *)
END (*--BoundedGraph *);
TYPE Graph = POINTER TO BoundedGraph;
(*-------------------------*)
(*
14.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 handlers array.
GetHandler returns the current exception handler for theError from the
handlers array.
*)
VAR graphError : Exceptions;
VAR handlers : ARRAY Exceptions OF HandlerProc;
PROCEDURE GraphError () : Exceptions;
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;
(*-------------------------*)
(*
14.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 : EdgePtr (*--inout*));
VAR free : DisposeProc; (*-- attribute disposal routine, if any *)
BEGIN
WITH theEdge^ DO
free := DisposeOf(first^.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 : Vertex (*--in *));
BEGIN
WITH theNode DO
inGraph := NullGraph;
data := NullItem;
degree := 0;
prior := NullVertex;
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], ADR(vertices[v+1]));
END (*--for*);
InitVertex(vertices[maxVertices], NullVertex);
numVertices := 0;
firstVertex := NullVertex;
available := ADR(vertices[MIN(VertexIndex)]);
END (*--with*);
END InitFreeList;
(*-------------------------*)
(*
NewVertex retrievs a new, empty, vertex node from the list of available nodes.
The vertex field
inGraph is set to the proper value (its enclosing graph object) while indegree,
edges, and next are initialized to an empty state. The caller is responsible for
adding the vertex to the adjacency list for the graph. The routine also automatically
raises the overflow exception with the appropriate parameters, if necessary. As
noted in Volume 1, the version of Allocate used here sets theVertex to NIL if the
allocation fails. Thus, we ensure that theVertex returned is the NullVertex in
case of a memory management failure. Complexity O(1).
*)
PROCEDURE NewVertex ( theGraph : Graph (*--in *);
theItem : Label (*--in *);
theRoutine : Operations (*--in *))
: Vertex (*--out *);
VAR newVertex : Vertex; (*-- newly created vertex *)
BEGIN
IF (theGraph^.numVertices = theGraph^.maxVertices) THEN
RaiseErrIn(theRoutine, overflow);
ELSE
WITH theGraph^ DO
newVertex := available;
available := newVertex^.next;
END (*--with*);
WITH newVertex^ DO
inGraph := theGraph;
data := theItem;
degree := 0;
edges := NullEdge;
prior := NullVertex;
next := NullVertex;
END (*--with*);
END (*--if*);
RETURN newVertex;
END NewVertex;
(*-------------------------*)
(*
AddVertex adds theVertex to theGraph's set of all vertices. The vertex
is placed at the front of the doubly-linked list used to represent this
set. Complexity O(1)
*)
PROCEDURE AddVertex ( theGraph : Graph (*--inout*);
theVertex : Vertex (*--inout*));
BEGIN
WITH theGraph^ DO
IF (firstVertex # NullVertex) THEN
firstVertex^.prior := theVertex;
END (*--if*);
theVertex^.next := firstVertex;
firstVertex := theVertex;
INC(numVertices);
END (*--with*);
END AddVertex;
(*-------------------------*)
(*
FreeVertex removes theVertex from theGraph's set of all vertices.
This routine uses a standard doubly-linked list removal
algorithm giving a constant time complexity of O(1).
*)
PROCEDURE FreeVertex ( theGraph : Graph (*--inout*);
VAR theVertex : Vertex (*--inout*));
BEGIN
WITH theVertex^ DO
IF (prior = NullVertex) THEN
theGraph^.firstVertex := next;
ELSE
prior^.next := next;
END (*--if*);
IF (next # NullVertex) THEN
next^.prior := prior;
END (*--if*);
END (*--with*);
FreeLabel(theVertex);
WITH theGraph^ DO
DEC(numVertices);
theVertex^.next := available;
available := theVertex;
END (*--with*);
theVertex := NullVertex;
END FreeVertex;
(*-------------------------*)
(*
NewEdge simply 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. Complexity O(1).
*)
PROCEDURE NewEdge ( vertex1 : Vertex (*--in *);
vertex2 : Vertex (*--in *);
theWeight : Attribute (*--in *);
theRoutine : Operations (*--in *))
: EdgePtr (*--out *);
VAR newEdgeRef : EdgePtr; (*--new edge being created *)
BEGIN
Allocate(newEdgeRef, SIZE(EdgeNode));
IF (newEdgeRef = NullRef) THEN
RaiseErrIn(theRoutine, overflow);
ELSE
WITH newEdgeRef^ DO
first := vertex1;
second := vertex2;
weight := theWeight;
edgeRef1 := NullEdge;
edgeRef2 := NullEdge;
next := NullRef;
prior := NullRef;
END (*--with*);
END (*--if*);
RETURN newEdgeRef;
END NewEdge;
(*-------------------------*)
(*
AddEdge adds theEdge to theGraph's set of all edges. The edge is placed
at the front of the doubly-linked list used to represent this set. Complexity O(1)
*)
PROCEDURE AddEdge ( theGraph : Graph (*--inout*);
theEdge : EdgePtr (*--inout*));
BEGIN
WITH theGraph^ DO
IF (firstEdge # NullRef) THEN
firstEdge^.prior := theEdge;
END (*--if*);
theEdge^.next := firstEdge;
firstEdge := theEdge;
INC(numEdges);
END (*--with*);
END AddEdge;
(*-------------------------*)
(*
FreeEdge removes theEdge from theGraph's set of all edges.
This routine uses a standard doubly-linked list removal
algorithm giving a constant time complexity of O(1).
*)
PROCEDURE FreeEdge ( theGraph : Graph (*--inout*);
VAR theEdge : EdgePtr (*--inout*));
BEGIN
WITH theEdge^ DO
IF (prior = NullRef) THEN
theGraph^.firstEdge := next;
ELSE
prior^.next := next;
END (*--if*);
IF (next # NullRef) THEN
next^.prior := prior;
END (*--if*);
END (*--with*);
DEC(theGraph^.numEdges);
FreeAttribute(theEdge);
Deallocate(theEdge, SIZE(theEdge^));
END FreeEdge;
(*-------------------------*)
(*
NewRef constructs a new edge reference node. The node is linked to its
associated EdgeNode while the links into a vertexes edge list are set to
the empty state. Complexity O(1).
*)
PROCEDURE NewEdgeRef ( theEdgePtr : EdgePtr (*--in *);
theRoutine : Operations (*--in *))
: Edge (*--out *);
VAR newEdge : Edge; (*--new edge reference being created *)
BEGIN
Allocate(newEdge, SIZE(EdgeRefNode));
IF (newEdge = NullEdge) THEN
RaiseErrIn(theRoutine, overflow);
ELSE
WITH newEdge^ DO
realEdge := theEdgePtr;
next := NullEdge;
prior := NullEdge;
END (*--with*);
END (*--if*);
RETURN newEdge;
END NewEdgeRef;
(*-------------------------*)
(*
AddEdgeRef adds theEdge to theVertex's set of edges incident on theVertex.
The edge is placed at the front of the doubly-linked list used to
represent this set. Complexity O(1)
*)
PROCEDURE AddEdgeRef ( theVertex : Vertex (*--inout*);
theEdge : Edge (*--inout*));
BEGIN
WITH theVertex^ DO
IF (edges # NullEdge) THEN
edges^.prior := theEdge;
END (*--if*);
theEdge^.next := edges;
edges := theEdge;
INC(degree);
END (*--with*);
END AddEdgeRef;
(*-------------------------*)
(*
FreeEdgeRef removes theEdge from theVertex's set of edges incident on
theVertex. This routine uses a standard doubly-linked list removal
algorithm giving a constant time complexity of O(1).
*)
PROCEDURE FreeEdgeRef ( theVertex : Vertex (*--inout*);
VAR theEdge : Edge (*--inout*));
BEGIN
WITH theEdge^ DO
IF (prior = NullEdge) THEN
theVertex^.edges := next;
ELSE
prior^.next := next;
END (*--if*);
IF (next # NullEdge) THEN
next^.prior := prior;
END (*--if*);
END (*--with*);
DEC(theVertex^.degree);
Deallocate(theEdge, SIZE(theEdge^));
END FreeEdgeRef;
(*-------------------------*)
(*
ClearEdgeRefs removes all directed edge referencess from a given vertexes edge list.
O(outdegree(v))
*)
PROCEDURE ClearEdgeRefs (VAR theVertex : Vertex (*--inout*));
VAR theEdge : Edge; (*--edge reference being removed *)
BEGIN
WITH theVertex^ DO
WHILE (edges # NIL) DO
theEdge := edges;
edges := edges^.next;
DEC(degree);
Deallocate(theEdge, SIZE(theEdge^));
END (*--while*);
END (*--with*);
END ClearEdgeRefs;
(*-------------------------*)
(*
14.2.4 Graph Constructors
Create attempts to form a new, empty graph object with the given vertex
label and edge label data types. First, the graph descriptor is allocated and the vertex
and edge data type IDs are stored there. The number of vertices and edges are
initialized to zero. The pointer to the head of the adjacency list (firstVertex)
is initialized to the empty state (NIL). If the descriptor allocation
fails the overflow exception is raised and the NullGraph is returned,
otherwise we return the newly allocated graph. Complexity O(1).
*)
CONST baseSize = SIZE(BoundedGraph) - SIZE(Vertices);
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;
numVertices := 0;
numEdges := 0;
firstEdge := NullRef;
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. Complexity O(|V|+|E|).
*)
PROCEDURE Clear ( theGraph : Graph (*--inout *));
PROCEDURE ClearEdges (VAR theGraph : Graph (*--inout *));
VAR theEdge : EdgePtr; (*--edge to be removed *)
BEGIN
WITH theGraph^ DO
WHILE (firstEdge # NullRef) DO
theEdge := firstEdge;
firstEdge := firstEdge^.next;
DEC(numEdges);
FreeAttribute(theEdge);
Deallocate(theEdge, SIZE(theEdge^));
END (*--while*);
END (*--with*);
END ClearEdges;
(*-------------------------*)
VAR theVertex : Vertex; (*--loop index over vertices *)
VAR oldVertex : Vertex; (*--vertex to deallocate *)
BEGIN
graphError := noerr;
IF (theGraph = NullGraph) THEN
RaiseErrIn(clear, undefined);
ELSE
ClearEdges(theGraph);
WITH theGraph^ DO
theVertex := firstVertex;
WHILE (theVertex # NullVertex) DO
ClearEdgeRefs(theVertex);
FreeLabel(theVertex);
oldVertex := theVertex;
theVertex := theVertex^.next;
oldVertex^.next := available;
available := oldVertex;
oldVertex^.inGraph := NullGraph;
END (*--while*);
firstVertex := NullVertex;
numVertices := 0;
END (*--with*);
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;
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; (*-- loop index over mapping entries *)
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 the
graph assignment operation continues 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
of 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 : Vertex; (*--loop index over vertices being copied *)
VAR newVertex : Vertex; (*--new vertex in target graph *)
VAR lastVertex: Vertex; (*--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 : Vertex (*--inout *);
VAR last : Vertex (*--inout *));
BEGIN
IF (first = NullVertex) THEN
first := newVertex;
ELSE
last^.next := newVertex;
END (*--if*);
last := newVertex;
END TailInsert;
BEGIN
CreateVertexMap;
IF (vertexMap = NIL) THEN
RETURN FALSE;
END (*--if*);
assignItem := AssignOf(theGraph^.labelType);
v := theGraph^.firstVertex;
lastVertex := NullVertex;
WHILE (v # NullVertex) DO
newVertex := NewVertex(toGraph, assignItem(v^.data), assign);
IF (newVertex = NullVertex) THEN
DestroyVertexMap;
RETURN FALSE;
END (*--if*);
TailInsert(toGraph^.firstVertex, lastVertex);
INC(toGraph^.numVertices);
AddToVertexMap(v, newVertex);
v := v^.next;
END (*--while*);
RETURN TRUE;
END CopyVertices;
PROCEDURE CopyEdges;
VAR theEdge : EdgePtr; (*--loop index over edges in source graph *)
VAR newEdge : EdgePtr; (*--new edge for target graph *)
VAR lastEdge : EdgePtr; (*--last edge inserted into new list of edges *)
VAR epRef1 : Edge;
VAR epRef2 : Edge;
VAR assignItem: AssignProc; (*--attribute assignment procedure *)
VAR vertex1 : Vertex; (*--first vertex of theEdge in target graph *)
VAR vertex2 : Vertex; (*--second vertex of theEdge in target graph *)
BEGIN
assignItem := AssignOf(theGraph^.attrType);
theEdge := theGraph^.firstEdge;
lastEdge := NullRef;
WHILE (theEdge # NullRef) DO
vertex1 := VertexInMap(theEdge^.first);
vertex2 := VertexInMap(theEdge^.second);
newEdge := NewEdge(vertex1,
vertex2,
assignItem(theEdge^.weight),
assign);
IF (newEdge = NullRef) THEN
RETURN;
END (*--if*);
epRef1 := NewEdgeRef(newEdge, assign);
IF (epRef1 = NullEdge) THEN
Deallocate(newEdge, SIZE(newEdge^));
RETURN;
END (*--if*);
newEdge^.edgeRef1 := epRef1;
IF (vertex1 # vertex2) THEN
epRef2 := NewEdgeRef(newEdge, assign);
IF (epRef2 = NullEdge) THEN
Deallocate(newEdge, SIZE(newEdge^));
Deallocate(epRef1, SIZE(epRef1^));
RETURN;
END (*--if*);
newEdge^.edgeRef2 := epRef2;
AddEdgeRef(vertex2, epRef2);
END (*--if*);
AddEdgeRef(vertex1, epRef1);
AddEdge(toGraph, newEdge);
theEdge := theEdge^.next;
END (*--while*);
END CopyEdges;
BEGIN (*--Assign --*)
graphError := noerr;
IF RecreateTarget() & CopyVertices() THEN
CopyEdges;
DestroyVertexMap;
END (*--if*);
END Assign;
(*-------------------------*)
(*
14.2.5 Vertex Constructors
Insert adds a vertex to the given graph labeling the vertex with the given item.
The first step is to allocate a new vertex node which, if successful,
is followed by adding the vertex at the head of the adjacency list. If we cannot
create a new vertex node 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 *));
BEGIN
graphError := noerr;
theVertex := NullVertex;
IF (theGraph = NullGraph) THEN
RaiseErrIn(insert, undefined);
ELSE
theVertex := NewVertex(theGraph, theItem, insert);
IF (theVertex # NullVertex) THEN
AddVertex(theGraph, theVertex);
END (*--if*);
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. After we have checked that no exceptions can occur we remove
all edges incident on 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(degree(v)).
*)
PROCEDURE Remove (VAR theGraph : Graph (*--inout*);
VAR theVertex : Vertex (*--inout*));
(*
Given a vertex and an edge reference, OtherVertex returns the other
member of the unordered pair of vertices associated with the edge.
For example, given the vertex v and the undirected edge {v, w}
OtherVertex returns the vertex w. Complexity O(1)
*)
PROCEDURE OtherVertex ( theVertex : Vertex (*--in *);
theEdge : Edge (*--in *))
: Vertex (*--out *);
BEGIN
WITH theEdge^.realEdge^ DO
IF (first = theVertex) THEN
RETURN second;
ELSE
RETURN first;
END (*--if*);
END (*--with*);
END OtherVertex;
(*
Given a directed edge reference, OtherEdge returns the
other directed edge used in representing an undirected edge.
Complexity O(1).
*)
PROCEDURE OtherEdge ( theEdge : Edge (*--in *))
: Edge (*--out *);
BEGIN
WITH theEdge^.realEdge^ DO
IF (edgeRef1 = theEdge) THEN
RETURN edgeRef2;
ELSE
RETURN edgeRef1;
END (*--if*);
END (*--with*);
END OtherEdge;
VAR anEdge : Edge; (*--loop index over edges *)
VAR vertex2 : Vertex; (*--other endpoint in anEdge *)
VAR edge2 : Edge; (*--edge in vertex2's edge list *)
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);
ELSE
anEdge := theVertex^.edges;
WHILE (anEdge # NullEdge) DO
vertex2 := OtherVertex(theVertex, anEdge);
edge2 := OtherEdge(anEdge);
FreeEdgeRef(vertex2, edge2);
FreeEdge(theGraph, anEdge^.realEdge);
anEdge := anEdge^.next;
END (*--while*);
ClearEdgeRefs(theVertex);
FreeVertex(theGraph, theVertex);
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) OR (theVertex^.inGraph = NullGraph) THEN
RaiseErrIn(setlabel, nullvertex);
ELSE
FreeLabel(theVertex);
theVertex^.data := theItem;
END (*--if*);
END SetLabel;
(*-------------------------*)
(*
14.2.6 Edge Constructors
Link adds an undirected edge between the from and to vertices labelling the
edge with the given weight attribute. The first step creates a new edge. Secondly,
new references for each vertices edge list are created (only one edge reference
is created when endpoint1 = endpoint2). Lastly, the new edge references and the
edge itself are added to their respective lists. If the memory allocation for
any of the nodes fails, allocations performed prior to the one that failed are
deallocated preventing needless clutter. Complexity O(1).
*)
PROCEDURE Link (VAR theGraph : Graph (*--inout*);
endpoint1 : Vertex (*--in *);
endpoint2 : Vertex (*--in *);
theWeight : Attribute (*--in *);
VAR theEdge : Edge (*--out *));
VAR newEdgePtr : EdgePtr;
VAR newEdge : Edge; (*-- edge ref for {ep2, ep1} *)
BEGIN
graphError := noerr;
theEdge := NullEdge;
IF (theGraph = NullGraph) THEN
RaiseErrIn(link, undefined);
ELSIF (endpoint1 = NullVertex) OR (endpoint2 = NullVertex) THEN
RaiseErrIn(link, nullvertex);
ELSIF (endpoint1^.inGraph # theGraph) OR
(endpoint2^.inGraph # theGraph) THEN
RaiseErrIn(link, novertex);
ELSE
newEdgePtr := NewEdge(endpoint1, endpoint2, theWeight, link);
IF (newEdgePtr = NullRef) THEN
RETURN;
END (*--if*);
theEdge := NewEdgeRef(newEdgePtr, link);
IF (theEdge = NullEdge) THEN
Deallocate(newEdgePtr, SIZE(newEdgePtr^));
RETURN;
END (*--if*);
newEdgePtr^.edgeRef1 := theEdge;
IF (endpoint1 # endpoint2) THEN
newEdge := NewEdgeRef(newEdgePtr, link);
IF (newEdge = NullEdge) THEN
Deallocate(newEdgePtr, SIZE(newEdgePtr^));
Deallocate(theEdge, SIZE(theEdge^));
RETURN;
END (*--if*);
newEdgePtr^.edgeRef2 := newEdge;
AddEdgeRef(endpoint2, newEdge);
END (*--if*);
AddEdge(theGraph, newEdgePtr);
AddEdgeRef(endpoint1, theEdge);
END (*--if*);
END Link;
(*-------------------------*)
(*
Unlink removes an undirected edge between the two vertices, fromVertex and
toVertex. Complexity O(d) where d is the degree of the from vertex.
*)
PROCEDURE Unlink (VAR theGraph : Graph (*--inout*);
VAR theEdge : Edge (*--inout*));
VAR theRealEdge : EdgePtr;
BEGIN
graphError := noerr;
IF (theGraph = NullGraph) THEN
RaiseErrIn(unlink, undefined);
ELSIF (theEdge = NullEdge) THEN
RaiseErrIn(unlink, nulledge);
ELSIF (theEdge^.realEdge^.first = NullVertex) THEN
RaiseErrIn(unlink, nullvertex);
ELSIF (theEdge^.realEdge^.first^.inGraph # theGraph) THEN
RaiseErrIn(unlink, noedge);
ELSE
theRealEdge := theEdge^.realEdge;
WITH theRealEdge^ DO
FreeEdgeRef(first, edgeRef1);
IF (edgeRef2 # NullEdge) THEN
FreeEdgeRef(second, edgeRef2);
END (*--if*);
END (*--with*);
FreeEdge(theGraph, theRealEdge);
theEdge := NullEdge;
END (*--if*);
END Unlink;
(*-------------------------*)
(*
SetAttribute assigns a new edge labeling 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
WITH theEdge^ DO
FreeAttribute(realEdge);
realEdge^.weight := theWeight;
END (*--with*);
END (*--if*);
END SetAttribute;
(*-------------------------*)
(*
14.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;
(*-------------------------*)
(*
SizeOf 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;
(*-------------------------*)
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;
(*-------------------------*)
(*
14.2.8 Vertex Selectors
DegreeOf returns the number of edges incident on the given vertex.
We do this by simply returning the value maintained by Link and Unlink.
Complexity O(1).
*)
PROCEDURE DegreeOf ( theVertex : Vertex (*--in *))
: CARDINAL (*--out *);
BEGIN
graphError := noerr;
IF (theVertex = NullVertex) THEN
RaiseErrIn(degreeof, nullvertex);
RETURN 0;
END (*--if*);
RETURN theVertex^.degree;
END DegreeOf;
(*-------------------------*)
(*
LabelOf returns the vertex label associated with the given vertex.
If the vertex is undefined the NullItem is returned. 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);
RETURN NullGraph;
END (*--if*);
RETURN theVertex^.inGraph;
END GraphOf;
(*-------------------------*)
(*
14.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^.realEdge^.weight;
END (*--if*);
RETURN NullItem;
END AttributeOf;
(*-------------------------*)
(*
Given an edge, FirstOf returns the first vertex in the set of vertices
associated with the given edge or the NullVertex if the edge is undefined.
Complexity O(1).
*)
PROCEDURE FirstOf ( theEdge : Edge (*--in *))
: Vertex (*--out *);
BEGIN
graphError := noerr;
IF (theEdge = NullEdge) THEN
RaiseErrIn(firstof, nulledge);
ELSE
RETURN theEdge^.realEdge^.first;
END (*--if*);
RETURN NullVertex;
END FirstOf;
(*-------------------------*)
(*
Given an edge, SecondOf returns the second vertex in the set of vertices
associated with the given edge or the NullVertex if the edge is undefined.
Complexity O(1).
*)
PROCEDURE SecondOf ( theEdge : Edge (*--in *))
: Vertex (*--out *);
BEGIN
graphError := noerr;
IF (theEdge = NullEdge) THEN
RaiseErrIn(secondof, nulledge);
ELSE
RETURN theEdge^.realEdge^.second;
END (*--if*);
RETURN NullVertex;
END SecondOf;
(*-------------------------*)
(*
IncidentOn is simply a combination of FirstOf and SecondOf.
Complexity O(1).
*)
PROCEDURE IncidentOn ( theEdge : Edge (*--in *);
VAR endpoint1 : Vertex (*--out *);
VAR endpoint2 : Vertex (*--out *));
BEGIN
graphError := noerr;
IF (theEdge = NullEdge) THEN
RaiseErrIn(incidenton, nulledge);
endpoint1 := NullVertex;
endpoint2 := NullVertex;
ELSE
WITH theEdge^.realEdge^ DO
endpoint1 := first;
endpoint2 := second;
END (*--with*);
END (*--if*);
END IncidentOn;
(*-------------------------*)
(*
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^.realEdge^.first = NullVertex) THEN
RaiseErrIn(isedge, nullvertex);
ELSE
RETURN theEdge^.realEdge^.first^.inGraph = theGraph;
END (*--if*);
RETURN FALSE;
END IsEdge;
(*-------------------------*)
(*
14.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 theVertex : Vertex; (*--loop index over vertices *)
BEGIN
graphError := noerr;
IF (theGraph = NullGraph) THEN
RaiseErrIn(loopvertices, undefined);
ELSE
theVertex := theGraph^.firstVertex;
WHILE (theVertex # NullVertex) & process(theVertex) DO
theVertex := theVertex^.next;
END (*--while*);
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(|E|).
*)
PROCEDURE LoopEdges ( theGraph : Graph (*--in *);
process : EdgeLoopProc (*--in *));
VAR theEdge : EdgePtr; (*--loop index over edges of a graph *)
BEGIN
graphError := noerr;
IF (theGraph = NullGraph) THEN
RaiseErrIn(loopedges, undefined);
ELSE
theEdge := theGraph^.firstEdge;
WHILE (theEdge # NullRef) & process(theEdge^.edgeRef1) DO
theEdge := theEdge^.next;
END (*--while*);
END (*--if*);
END LoopEdges;
(*-------------------------*)
(*
LoopIterate simply loops over the edges leaving a specified vertex. Complexity
O(degree(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 theVertex : Vertex; (*--loop index over vertices *)
BEGIN
graphError := noerr;
IF (theGraph = NullGraph) THEN
RaiseErrIn(travvertices, undefined);
ELSE
theVertex := theGraph^.firstVertex;
WHILE (theVertex # NullVertex) DO
process(theVertex);
theVertex := theVertex^.next;
END (*--while*);
END (*--if*);
END TravVertices;
(*-------------------------*)
(*
TravEdges simply iterates over every edge in the graph using the
set of all edges. Complexity O(|E|).
*)
PROCEDURE TravEdges ( theGraph : Graph (*--in *);
process : EdgeProc (*--in *));
VAR theEdge : EdgePtr; (*--loop index over edges *)
BEGIN
graphError := noerr;
IF (theGraph = NullGraph) THEN
RaiseErrIn(travedges, undefined);
ELSE
theEdge := theGraph^.firstEdge;
WHILE (theEdge # NullRef) DO
process(theEdge^.edgeRef1);
theEdge := theEdge^.next;
END (*--while*);
END (*--if*);
END TravEdges;
(*-------------------------*)
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;
(*-------------------------*)
(*
14.2.11 Active Iterators
Each of the active iterators are essentially selectors for the underlying
representation of the adjacency list. Their complexity is O(1).
*)
PROCEDURE FirstVertex ( theGraph : Graph (*--in *))
: Vertex (*--out *);
BEGIN
graphError := noerr;
IF (theGraph = NullGraph) THEN
RaiseErrIn(firstvertex, undefined);
ELSE
RETURN 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
RETURN theVertex^.next;
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;
(*-------------------------*)
(*
14.2.12 Module Initialization
The module's local variables are initialized to known states. graphError is
used to fill the handler 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 GrafSBMI.