On an Algorithm for Transforming the Form of Representation of a Graph

Yu. N. Efimov, P. A. Sedelnikov

(Presented by the scientific seminar of the Department of Computer Engineering of the Scientific Research Institute of Automated Control Systems)

Thanks to advances in computing technology, the range of applied problems using network models and formulated in terms of graph theory has expanded considerably. It is known that, in doing so, three equivalent forms of representing the topology of a graph may be used [1]:

1. \(G=(I,\Gamma)\) — a list of vertices and their direct mappings.
2. \(G=(I,\Gamma^{-1})\) — a list of vertices and their inverse mappings.
3. \(G=(I,U)\) — a list of vertices and arcs.

Usually, algorithms for analyzing network models require a definite form for specifying the topology, which often may not coincide with the initial form of representation determined by established forms of documents, traditions, or simply by convenience of formation. For example, in ASUP-Tomsk [2], when calculating launch plans, the network model must be represented in form 1, while when forming the completion statement it must be represented in form 2. Moreover, the initial topology, in turn, may be represented in form 1 or 2, depending on the forms of design documentation used for its compilation (summary or unit specifications of the product).

In this connection, the problem arises of algorithmically transforming the form of representation of a graph. The transition from forms 1 and 2 of specification to form 3, and from form 3 to forms 1 and 2, is trivial and will not be considered further. The more complex case is the transformation of form 1 into form 2 and conversely.

Let us describe the second problem of transforming the form of representation of a graph, which arises in automated management systems using network models compiled on the basis of design documentation for products [2]. To simplify and speed up computations when forming launch plans, it is desirable to have only a consolidated network model for several commercial products that have many common products (instruments, assemblies, parts, etc.). However, the difficulties of compiling consolidated network models, due to the forms of design documentation existing at an enterprise, create the need to develop an algorithm for machine “stitching” (merging) the partial networks of commercial products into the consolidated network of an order. The availability of such an algorithm makes it possible for individual topology arrays to be formed by different executors independently of one another, which increases the reliability of the input information. Since the problem described is more general and includes the first problem as a special case, we shall give a more detailed description of its solution.

In terms of graph theory [1], the problem of “stitching” network models may be formulated as follows:

Given \(n\) graphs \(G_1=(I_1,U_1), \ldots, G_k=(I_k,U_k), \ldots, G_n=(I_n,U_n)\), where:

\(I_k\) is the set of vertices of the graph \(G_k\),

\(U_k\) is the set of arcs of the graph \(G_k\), \(\prod U_k \ne \varnothing\).

To each arc \((i_k,j_k)\in U_k\) there is assigned a certain aggregate of parameters \(M_{i_k,j_k}\). It is required to find a graph \(G=(I,U)\), where

\[ I=\bigcup_{k=1}^{n} I_k,\quad U=\bigcup_{k=1}^{n} U_k, \]

and each arc \((i,j)\in U\) must retain the corresponding parameters \(M_{ij}\).

To solve the stated problem one may apply the operation of union of the sets of arcs \(U_k\) \((k=1,\ldots,n)\). For this, regarding the arcs of all initial graphs as numbers composed of the codes of the initial and terminal vertices of each arc, it is necessary to order them in increasing (or decreasing) order, after which the repeated ones are to be excluded from the complete set of arcs. However, implementation of such an algorithm on a computer will lead to large expenditures of machine time because of the considerable volumes of initial information and the inefficiency of existing [3] algorithms for external sorting.

Taking into account the above, as well as the representation of the initial graphs in the form of a set of vertices \(J_k\) and their direct mappings \(\Gamma_{ik}\) (form 1), we propose the following stitching algorithm, consisting of 4 main stages.

At the first stage, information on the topologies of all the “stitched” networks is scanned and the set

\[ I=\bigcup_{k=1}^{n} I_k \]

is formed, to which the set \(W\) is put in correspondence. Each element \(w_k\in W\) determines the local degree [4] \(\rho_{ik}\) of the vertex \(i_k\in J\) of a certain graph \(G^*=(J,\Gamma)\), where

\[ I=\bigcup_{k=1}^{n} I_k,\quad \Gamma=\{\Gamma_1,\Gamma_2,\ldots,\Gamma_n\}. \]

The procedure for constructing the sets \(I\) and \(W\) is performed in one scan of the initial information.

At the second stage, the set \(J\) is ordered in increasing order of the values of its elements, which makes it possible to accelerate the process of excluding repeated vertex ciphers in the initial set. When sorting \(J\), transformations in \(W\) are also necessary so that the one-to-one correspondence between these two sets is not disturbed. Since the size of \([J]\) is much smaller in comparison with the volume of the initial data, the information being sorted usually fits into the machine’s main memory, and efficient internal-sorting algorithms can be applied (for example, the radix-sorting algorithm). After sorting \(J\), we recode the vertices \(i\in J\) in the initial information. The recoding consists in replacing the decimal ciphers in the first lines of the records \((i_{10})\) by certain of their octal equivalents \((i_8)\). It is convenient to take as the octal cipher \(i_8\) of the vertex \(i_{10}\in J\) its ordinal number in the sorted array \(J\). As a result, we obtain continuous numbering of the vertices (starting from one) in the octal number system. Recoding is also performed in one scan of the initial information.

At the third stage of the algorithm, the graph \(G^*\) is formed. This is the principal and most laborious (in terms of machine-time expenditure) stage of the computations, proposed instead of the usual procedure of external sorting. Let us explain it in somewhat greater detail.

Divide the ordered set \(J\) into subsets.

\[ I^1=\{i_1,i_2,\ldots,i_\alpha\},\ I^2=\{i_{\alpha+1},\ldots,i_\beta\},\ldots,\ I^k=\{i_{\mu+1},\ldots,i_\nu\},\ldots,\ I^m=\{i_{\nu+1},\ldots,i_n\}, \]

such that

\[ \bigcup_{k=1}^{m} I^k=I,\quad I^k \cap I^l=\varnothing \quad \text{for } k\ne l. \]

Fig. 1. Distribution of main memory at the third stage of operation of the “stitching” algorithm. \(P\) — the working program; \(A\) — an array of relative addresses (variable); \(M_G\) — an array for storing information about subgraphs; \(G^{**}\), \(W=\{w_i/i\in I\}\); \(L\) — a field for reading information from magnetic tape; \(D\) — the dispatcher program.

Let, at each step of operation of the algorithm (the 3rd stage), the amount \(M_G\) of main memory (Fig. 1) make it possible to place all records for vertices \(i\in J^k\), that is, to form the subgraph \(G_{*k}\subseteq G_*\). Then the process of forming the subgraph \(G^{**}\) can be carried out in one scan of the initial information in the following way.

To each vertex \(i\in J^k\) we assign an element \(a_i\in A\), which is the relative address of the placement in main memory of the record for this vertex. The elements \(a_i\) are not difficult to compute, using the recurrence relation:

\[ a_{i_{\mu+k+1}}=a_{i_{\mu+k}}+w_{i_{\mu+k}}+1. \]

For the first element in order \(i_\mu\in J^k\) we have \(a_{i_\mu}=0\).

Now, scanning the initial information, for vertices \(i\in J^k\) we copy the records into the field in accordance with the addresses \(a_i\in A\). As a result, in one scan of the initial information the subgraph \(G^{*k}\) will be formed and, after sorting the elements within each record, it can be copied to magnetic tape. It is obvious that after carrying out such a procedure with each of the subsets \(J^k\) \((k=1,\ldots,m)\), the graph \(G^*\) will be formed.

Since after recoding we obtain a continuous numbering of vertices, when forming the subsets \(J_k\) it is sufficient to remember only their initial \(i_{\mathrm{n}}^k\) and final \(i_{\mathrm{k}}^k\) elements.

In general, the work of the third stage of the algorithm reduces to the following. Set \(A=\varnothing\), \(M_G=\mathrm{const}\). Form \(i_{\mathrm{n}}^1=1\) for \(J^1\). For each element \(i_l\) introduced into \(J^1\), the condition must be satisfied:

\[ w_i+1\leq M_G. \]

If for some element \(i_l\) this condition is not satisfied, then \(i_{\mathrm{k}}^1=i_{l-1}\), and \(i_{\mathrm{n}}^2=i_l\). When the condition is satisfied, the element is assigned to \(J^1\), the corresponding relative address is entered into \(A\), and the value of \(M_G\) is changed:

\[ M_G:=M_G-(w_i+1)-1. \]

After \(J^1\) has been obtained, the corresponding subgraph is formed, then the subset \(J^2\), for which the initial element has already been obtained, and so on, until the last subgraph \(G^{*m}\) is formed. It is not difficult to see that, in carrying out the third stage, \(m\) scans of the initial information are required. We also note that the number of elements in \(J^k\) may vary. However, if all records have constant length, then, owing to the fields \(A\) and \(M_G\), which are variable in size, the proposed algorithm ensures

\[ |J^k|\leq |J^{k+1}|, \]

which increases the speed.

At the fourth stage, \(G^*\) is examined and repeated arcs are removed from it. Moreover, only those arcs for which the corresponding parameters \(M_{ij}\) are equal are removed. Otherwise it is necessary to print information about an admissible error in one of the “spliced” topologies. The proposed algorithm is invariant with respect to forms 1 and 2 of representing the topology.

To solve the first problem (transforming the first form into the second, and conversely), an algorithm is proposed that uses the idea of the general problem and consists of two stages. Let the initial topology be given in form 1; then, at the first stage, the set \(W\) is formed, each element of which, \(w_j \in W\), is equal to the number of arcs entering the vertex \(j \in J\) (i.e., to the number of elements \(i \in \Gamma_j^{-1}\)). The formation of the set \(W\) consists in examining all records of the initial information and performing \(w_j := w_j + 1\) for every \(j\) entering the \(i\)-th record. At the second stage the graph \(G = (J, \Gamma^{-1})\) is formed. For this purpose the set \(J\) is likewise divided into intersecting subsets \(J^k\) \((k = 1, \ldots, m)\). During each examination of the initial information, a subgraph \(G^k = (J^k, \Gamma^{-1k})\) is formed, including records only for vertices \(j \in J^k\), where \(k\) is the ordinal number of the examination.

It should be noted that the proposed algorithm is also invariant with respect to the first two forms of representing the topology of a graph.

The algorithms set forth above were implemented on the Ural-11B computer and showed sufficiently high efficiency. The proposed method can also be applied to external sorting of variable-length records.

REFERENCES

1. C. Berge. Graph Theory and Its Applications. Moscow, IL Publishing House, 1962.

2. Yu. N. Efimov, V. I. Kizeev, V. I. Nevraev, F. I. Peregudov, P. A. Sedelnikov. Basic principles of the construction and functioning of ASUP-Tomsk. (The present collection.)

3. S. B. Potebinsky, L. S. Lozinsky. On the problem of sorting information using magnetic tapes. Kibernetika, No. 2, 1965.

4. O. Ore. Graph Theory. Moscow, Nauka, 1968.