home *** CD-ROM | disk | FTP | other *** search
/ Fresh Fish 8 / FreshFishVol8-CD2.bin / bbs / dev / oberon-a-1.4ß.lha / Oberon-A / texts / SymbolFiles.Text < prev    next >
Text File  |  1994-02-09  |  55KB  |  1,367 lines
  1. Departement Informatik
  2. Institut für Computersysteme
  3. Eidgenössische Technische Hochschule
  4. Zürich
  5.  
  6. Robert Griesemer
  7. On the Linearization of Graphs and Writing Symbol Files
  8.  
  9. Cuno Pfister (ed.)
  10. Oberon Technical Notes
  11. Beat Heeb
  12. Josef Templ
  13. March 1991
  14.  
  15. Address of the authors:
  16.   Computersysteme
  17.   ETH-Zentrum
  18.   CH-8092 Zurich, Switzerland
  19.  
  20. e-mail:
  21.   griesemer@inf.ethz.ch
  22.   pfister@inf.ethz.ch
  23.  
  24. Copyright (c) 1991 Departement Informatik, ETH Zürich
  25.  
  26. On the Linearization of Graphs and Writing Symbol Files
  27. Robert Griesemer
  28.  
  29. Abstract
  30.  
  31. The linearization of general graphs represented by pointer and record
  32. data structures is a problem often arising in computer programs.
  33. Whenever a graph has to be stored on or transmitted over a sequentially
  34. organized carrier, a form of linearization is used. A simple algorithm
  35. for this purpose is presented and a special application - the writing of
  36. symbol files as required by modern language compilers - is described in
  37. more detail.
  38.  
  39. Keywords: Linearization, Graphs, Symbol Files.
  40.  
  41. 1. Linearization of Graphs
  42.  
  43. General graphs occur in various forms in computer science, sophisticated
  44. data structures may often be interpreted as graphs. Whenever such a data
  45. structure has to be stored on a file or has to be transmitted over a
  46. network, the linearization problem occurs. For special forms of
  47. non-linear data structures (e.g. trees) well-known solutions exist and
  48. are comprehensively described in the basic literature. Nevertheless, for
  49. more general data structures the wheel has to be reinvented and
  50. literature is difficult to find [ReMö86]. The problem has a twofold
  51. nature: firstly, the graph has to be linearized by means of a write
  52. algorithm , and secondly, it has to be rebuilt out of its linear
  53. description by a read algorithm . In the following, linearization means
  54. writing a graph to a file.
  55.  
  56. 1.1 Preconditions
  57.  
  58. First of all, we remember that every general (undirected) graph may be
  59. represented by a directed graph, by means of having two directed edges
  60. instead of an undirected one. Hence, we concentrate on directed graphs
  61. only. Secondly, we consider only rooted and connected graphs; i.e.
  62. graphs with a special root node and a path from the root to every other
  63. node. Unconnected graphs or graphs with several root nodes are easily
  64. extended such, that they obey the above preconditions. Thirdly, as an
  65. (academic) restriction only finite graphs are considered.
  66.  
  67. In computer programs, graphs may be represented in various forms,
  68. depending on the available notational support (the programming language)
  69. and the way the data structure is used (the program). Here we consider
  70. only graphs described in terms of pointers and records; i.e. every graph
  71. node is represented by a record and every edge is represented by a
  72. pointer. Note that possible information attached to the edges of a graph
  73. ( labeled edges ) may be interpreted as additional node data.
  74.  
  75. The nodes of such a graph may not all have the same type; i.e. the
  76. amount of data in every node may be different and the number of directed
  77. edges to other nodes may vary. It depends on the application and
  78. available language how different nodes are specified. For the sake of
  79. simplicity we identify each node with a positive tag -number (> 0), so
  80. that every node type is clearly determined by its tag and vice versa.
  81. Then, every node contains a certain amount M(tag) of data and (at most)
  82. a certain number N(tag) of directed edges to other nodes. Hence, a
  83. general graph node and its edges may be described in the following way
  84. (written in Oberon [Wi88]):
  85.  
  86. TYPE
  87.   Node = POINTER TO NodeDesc;
  88.  
  89.   NodeDesc = RECORD
  90.     tag: INTEGER;                  (* determines node type; tag > 0 *)
  91.     data: ARRAY M(tag) OF INTEGER; (* M depends on the node type (tag) *)
  92.     link: ARRAY N(tag) OF Node     (* N depends on the node type (tag) *)
  93.   END;
  94.  
  95. Note that any data structure represented in any way in computer memory
  96. may be written to a file by simply writing out sequentially the
  97. corresponding memory area.  Reading requires "only" the data to be read
  98. into the same memory area (otherwise pointers would be incorrect).  But
  99. normally this is an inappropriate solution for several reasons: often
  100. the data structure is distributed over the entire available memory and
  101. writing would lead to an immense waste of space.  For reading, the
  102. destination memory addresses must be specified which is almost never
  103. possible and a file created this way is inherently not portable (to
  104. another computer system).
  105.  
  106. Hence, writing of graphs requires pointers to be transformed into
  107. another form of reference and vice versa for reading.  In addition,
  108. reading and writing should be as efficient as possible considering both
  109. memory and time; e.g. each node description should appear once and only
  110. once on the file.
  111.  
  112. 1.2 The Write Algorithm
  113.  
  114. The write algorithm resembles closely a naive recursive mark-algorithm
  115. for garbage collectors, actually it is nearly the same task to be done:
  116. all nodes have to be traversed and marked; marking is necessary to avoid
  117. a second traversal and to refer to the node's first occurence. While
  118. traversing the graph its structure is written to a file. Hence, the node
  119. data structure has to be extended by a mark field, which initially must
  120. be zero:
  121.  
  122. TYPE
  123.   Node = POINTER TO NodeDesc;
  124.  
  125.   NodeDesc = RECORD
  126.     mark: INTEGER;            (* used for linearization; initially = 0 *)
  127.     tag: INTEGER;                  (* determines node type; tag > 0 *)
  128.     data: ARRAY M(tag) OF INTEGER; (* N depends on the node type (tag) *)
  129.     link: ARRAY N(tag) OF Node     (* M depends on the node type (tag) *)
  130.   END;
  131.  
  132. We say a node q is marked iff q.mark > 0. The WriteNode procedure (see
  133. below) traverses the graph in pre-order, starting with the root node.
  134. Whenever an unmarked node is encountered, the node is numbered and thus
  135. marked (line 4), the node tag and data are written (lines 4 and 5) and
  136. its successor nodes are traversed (line 6). Note that a node must be
  137. numbered before its subtrees are traversed because they may refer to it.
  138. Numbering is done using the counter NofNodes which is one initially and
  139. is then incremented by one with every processed node. Hence, NofNodes is
  140. always greater than zero. Whenever an already marked node is traversed,
  141. only its negative node number is written out as reference number (line
  142. 2). If the node doesn't exist (i.e. q = NIL) zero is written out (line
  143. 1):
  144.  
  145. VAR
  146.   NofNodes: INTEGER; (* node number; initially = 1 *)
  147.  
  148. PROCEDURE WriteNode(q: Node);
  149.   VAR i: INTEGER;
  150. BEGIN
  151. (1) IF q = NIL THEN WriteInt(0)
  152. (2) ELSIF q.mark > 0 THEN (* already marked *) WriteInt(-q.mark)
  153. (3) ELSE (* first occurence *)
  154. (4) WriteInt(q.tag); q.mark := NofNodes; INC(NofNodes);
  155. (5) i := 0; WHILE i < M(tag) DO WriteInt(q.data[i]); INC(i) END;
  156. (6) i := 0; WHILE i < N(tag) DO WriteNode(q.link[i]); INC(i) END
  157. (7) END
  158. END WriteNode;
  159.  
  160. During execution of WriteNode with argument root all nodes are numbered
  161. in the order of their first occurence. References to already written
  162. nodes are the negative node numbers. While reading the file this
  163. information will be used to reconstruct the graph (see 1.3 The Read
  164. Algorithm). Before WriteNode can be called a second time for the same
  165. graph or parts of it, the preconditions have to be established again,
  166. i.e. the nodes must be unmarked. When using time-stamps, no such unmark
  167. pass is necessary (due to an idea of J. Templ, see [PfiHeTe91]: A
  168. Symmetric Solution to the Load/Store Problem ). The WriteNode procedure
  169. leads to the following file structure (in EBNF, terminal symbols are
  170. described in double quotes):
  171.  
  172.   Graph = NodeRef | NoNode | NodeDesc.
  173.  
  174.   NodeRef = "negative node number (< 0)".
  175.  
  176.   NoNode = "0".
  177.  
  178.   NodeDesc = "node tag (> 0)" "node data" {Graph}.
  179.  
  180. It is obvious that the algorithm terminates for all graphs: there is
  181. only a finite number of nodes and every procedure call works on at least
  182. one node. The recursion is stopped when an already marked node and hence
  183. a loop is found (line 2) and the algorithm returns to its predecessor
  184. node. In line 4 the assignment q.mark := NofNodes is executed only if
  185. q.mark = 0, i.e. each node is numbered at most once (because NofNodes >
  186. 0). On the other hand, since after numbering of the node