INTERFACE GDGraph; (* A representation for directed graphs. *) IMPORT Rd, Wr; TYPE T <: PublicT; (* A data structure describing a directed graph. *) PublicT = OBJECT nV: NAT; (* (READONLY) Number of nodes in graph. *) nE: NAT; (* (READONLY) Number of edges in graph. *) (* An object of this type represents an ordered graph with directed and/or undirected edges, without parallel edges but possibly with `edge stubs' (see below). The nodes of the graph are the integers from 0 to "nV-1". Each node has a fixed number of `incoming slots', `outgoing slots', and `unoriented slots'. Each slot may hold one endpoint of at most one edge of the appropriate kind. Thus a directed edge "(u,v)" begins at an output slot of "u" and ends at an input slot of "v". An undirected edge "{u,v}" begins at an unoriented slot of "u" and ends at an unoriented slot of "v". Undirected loop edges "{u,u}" are not allowed. (Directed loops "(u,u)" are OK.) Between two distinct nodes "u" and "v" one may have at most two directed edges "(u,v)" and "(v,u)", and/or one undirected edge "{u,v}". Any slot may also be `vacant', meaning that no edge is currently connected to it. You may think of a vacant slot as an `edge stub' that is not connected to anything. In the methods below, the parameter "dir" is used to select between the incident edges (slots, neighbors, etc.) of a given node: either incoming ("dir = -1"), outgoing ("dir = +1"), or undirected ("dir = 0"). *) METHODS init(allocNodes: NAT := 20): T; (* Must be called before any other method call. Initializes a newly created graph. The "allocNodes" parameter is just a hint of how many nodes are likely to be created later. Returns the graph itself, properly initialized. *) nbor(u: Node; dir: Dir; k: Slot): Node; (* Returns the other endpoint of the edge that is currently attached to "k"th slot of "u" in the direction "dir". The result may be "NoNode", meaning that the corresponding slot is vacant. For each "dir", all "dir"-neighbors of a node "u" are distinct (except for "NoNode" values). However, a node "v # u" can occur as a neighbor of "u" in all three directions. Also "nbor(u,0,k) # u" for all "k"; but it is possible that "nbor(u,-1,k) = u" or "nbor(u,+1,k) = u"). Moreover, for any "dir", if "nbor(u,dir,k1) = v", and "v" is not "NoNode", then there will be some slot index "k2" such that "nbor(v,-dir,k2) = u". *) nbors(u: Node; dir: Dir; proper: BOOL := FALSE): REF Nodes; (* A list of all the nodes of a graph that are neighbors of "u" in the direction "dir". If "proper = TRUE" the list excludes "NoNode" entries. *) degree(u: Node; dir: Dir; proper: BOOL := FALSE): NAT; degrees(u: Node; proper: BOOL := FALSE): Degrees; (* The number of edge slots of node "u", for each direction. If "proper = TRUE" the count excludes currently vacant slots; i.e. it gives the number of proper neighbors of "u" in each direction. *) findSlot(u: Node; dir: Dir; v: Node): Slot; (* Returns the slot index "k" such that "nbor(u,dir,k) = v". If "v = NoNode", returns the first vacant slot. Returns "NoSlot" if there is no such slot. *) edges(dir: Dir): REF Edges; (* Gathers all the edges of the graph (excluding "NoNode" pairs). If "dir = 0" gathers the undirected edges; otherwise ordered by source node ("dir = +1") or destination node ("dir = -1"), then by slot index. *) addNode(deg: Degrees): Node; (* Adds to the graph a new node with "deg[dir]" edge slots for direction "dir", initially all vacant. The new node will have number "nV". Returns the new node. *) addEdge(dir: Dir; u: Node; ku: Slot; v: Node; kv: Slot); (* Adds a new edge from "u" to "v". The edge will exit "u" through slot number "ku" in direction "dir", and enter "v" through the slot number "kv" in direction "-dir". Both slots must be vacant ("NoNode") at call time; the edge "(u,v)" must not be present in any other slots of "u" and "v"; and, if "dir = 0", the two nodes must be distinct. *) deleteEdge(dir: Dir; u: Node; ku: Slot; v: Node; kv: Slot); (* Deletes the edge "(u,v)", which must be attached to output slot "ku" of "u" and to input slot "kv" of "v". Those slots will become vacant. *) copy(): T; (* Makes a copy of the object, such that calling the original methods will have no effect on the copy, and vice-versa. *) crunch(nKeep: NAT): NodeDict; (* Eliminates all nodes with numbers ">= nKeep" that cannot be reached from nodes "[0..nKeep-1]" by non-directed paths. Then renumbers the nodes that survived, with consecutive numbers. In particular, nodes "[0..nKeep-1]" remain unaffected. Returns the translation tables *) END; TYPE Node = NAT; (* The index of a node in a graph. *) Edge = ARRAY [0..1] OF Node; (* A directed edge from a graph. *) Nodes = ARRAY OF NAT; Edges = ARRAY OF Edge; Slot = NAT; (* Index of an edge slot in a node. *) Dir = [-1..+1]; (* Edge direction *) Degrees = ARRAY Dir OF NAT; (* Number of slots/neighbors in each direction. *) NodeDict = RECORD old, new: REF Nodes END; (* A node mapping table: "old[v]" is the old number of new node "v", "new[u]" is the inverse. *) CONST NoNode = LAST(Node); NoSlot = LAST(Slot); VAR (*CONST*) NoNodes: REF Nodes; (* An empty list of nodes *) TYPE NAT = CARDINAL; BOOL = BOOLEAN; SIGN = [-1..+1]; (* GRAPH COMPARISON *) PROCEDURE Identical(G, H: T): BOOL; (* TRUE if the graphs are identical, including the order of vertices and the numbering of edge slots. *) (* GRAPH I/O *) PROCEDURE Read(rd: Rd.T; allocNodes: NAT := 0): T; (* Reads a graph from "rd", in a specific format. Allocates initially space for at least "allocNodes". *) PROCEDURE Write(wr: Wr.T; G: T; comment: TEXT := ""); (* Writes "G" to "wr" in a format compatible with "Read". *) (* UTILITY PROCEDURES *) PROCEDURE CopyNodes(READONLY uu: Nodes): REF Nodes; (* Copies a list of nodes. *) PROCEDURE ProperNodes(READONLY uu: Nodes): REF Nodes; (* Returns a list conisting of the elements of "uu" that are not "NoNode", preserving their order. *) PROCEDURE FindNode(u: Node; READONLY vv: Nodes): NAT; (* Finds the index of "u" in the (unordered) list of nodes "vv". Returns "LAST(NAT)" if "u" is not there. *) PROCEDURE InsertNode(u: Node; VAR vvR: REF Nodes; VAR n: NAT); (* Adds "u" at the end of the list "vvR^", incrementing "n". Will (re)alocate "vvR^" if necessary. *) PROCEDURE DeleteNode(u: Node; VAR vvR: REF Nodes; VAR n: NAT); (* Deletes "u" FROM the list "vvR^", decrementing "n". Will reallocate "vvR^" if gets too empty. *) TYPE NodeCompareProc = PROCEDURE (u, v: Node): SIGN; EdgeCompareProc = PROCEDURE (u, v: Edge): SIGN; PROCEDURE SortNodes(VAR uu: Nodes; cmp: NodeCompareProc); (* Sorts "uu" so that "cmp(uu[i-1],uu[i]) <= 0" for all "i". *) PROCEDURE ReSortNodes(VAR uu: Nodes; cmp: NodeCompareProc); (* Reorders "uu" so that "cmp(uu[i-1],uu[i]) <= 0" for all "i". Uses insertion sort, so it is good only if "uu" is almost ordered. *) (* VALIDATION *) PROCEDURE VerifyCompleteness(G: T; dir: Dir); (* Verifies that all slots of type "dir" are filled with valid node numbers. *) PROCEDURE VerifySlotInvariants(G: T); (* Verifies that all slots of each vertex "u" and direction "dir" are filled distinct, valid node numbers, different from "u"; and that matching slots exist in the target nodes. *) END GDGraph. (* Last edited on 2000-01-13 10:30:56 by stolfi *)