ALGORITHM FOR ORDERED RECODING OF GRAPH VERTICES

Yu. N. Efimov, P. A. Sedelnikov

(Presented by the scientific seminar of the UVL)

At the present time, a wide class of problems solved on digital computers is formulated in terms of graph theory. In doing so, contradictory requirements arise for the coding of the vertices of a graph (network). For network designers it is convenient to use multi-digit decimal codes that have a meaningful interpretation; however, from the point of view of the convenience of machine processing, continuous numbering of the vertices is desirable. It makes it possible to record the topology of the graph and other information arrays more compactly and simplifies the processes of sorting and searching. However, known recoding algorithms are very labor-consuming, since they require repeated scanning of the topology and a large number of comparisons of unrecoded codes with an ever increasing array, in magnitude, of recoded vertex codes [2].

On the other hand, it is often convenient, and sometimes necessary, to represent a graph in the form of layers arranged in the order of increasing order function \(\varphi\) of its vertices, where \(\varphi = 0, 1, 2, \ldots, k, \ldots, n\) [1]. The process of finding the order function without preliminary recoding of the vertices is labor-consuming. If such recoding has been performed, then ordering the topology by increasing order function makes repeated recoding necessary [2].

In this paper an algorithm is proposed for ordered recoding of the vertices of a graph, which is a modification of Kahn’s algorithm [3]. It makes it possible simultaneously to order the topology of a graph by increasing function \(\varphi\) and to carry out continuous numbering of its vertices in direct or reverse order with a minimal number of comparisons of unrecoded codes with the recoded vertex codes of the layer identified during the preceding scan of the topology.

Let a graph \(G\) be given by a set of vertices \(I\) and their direct or inverse mapping \(\Gamma_i\) [4], i.e.

\[ G = (I, \Gamma_i). \]

According to the value of the order function, it is divided into layers \(I_{\varphi_k}\), which are subsets of the set \(I\) and consist of vertices \(i\) with identical order functions.

\[ I_{\varphi_k} = \{ i \mid \Gamma_i \subseteq (\bigcup_{\varphi=0}^{k-1} I_\varphi) \}. \]

A set of vertices of the graph \(I\), distributed by layers, can be put into a one-to-one correspondence with an equipotent set of natural numbers, i.e.,

\[ |I| \sim |N|, \]

which yields an ordered recoding of the vertices.

The ordered recoding is carried out in \(n+2\) scans of the initial topology of the graph, during which a correspondence table (CT) is compiled between the codes of the vertices and the numbers of the natural sequence.

At each scan of the initial topology, in the next layer those vertices are singled out for which all elements of the mapping onto the preceding layers, i.e., all links, have been recoded.

At the first scan, the layer with \(\varphi=0\) (the zero layer) is singled out; its vertices have no links, i.e., \(\Gamma_i=\varnothing\). The codes of the vertices of the zero layer are entered in the CT. In the initial topology they are replaced by the corresponding numbers of the natural sequence and marked with flags. In addition, the vertices of the zero layer are entered into the topology array with ordered recoding.

At the second scan of the topology, those mapping elements \(j\) of the vertices of the graph \(i\) for which \(j \in (\Gamma_i \cap I_{\varphi_0})\) are recoded and marked with flags, i.e., all links present in the graph from vertices of subsequent layers to vertices of the zero layer are recoded. If, for some vertex, \(\Gamma_i \subseteq I_{\varphi_0}\), i.e., all links have been recoded, then its code is entered in the CT; in the initial topology recoding is performed and a flag is set. The vertex and its mappings are entered into the recoded-topology array. After a complete scan of the topology, the CT will contain the codes of all vertices of the first layer; in the initial topology, all mapping elements of vertices of subsequent layers to the zero layer will have been recoded. Therefore the CT codes of the vertices of the zero layer do not take part in the recoding during subsequent scans of the topology. Vertices and elements of their mappings that are marked in the topology by flags also do not take part in the further process of recoding.

At the \(k\)-th scan, those mapping elements of graph vertices for which

\[ j \in (\Gamma_i \cap I_{\varphi_{k-1}}). \]

are recoded and marked with flags.

Into the \(k\)-th layer are selected, entered in the CT, recoded, marked with flags in the initial topology, and written into the recoded topology those vertices for which

\[ \Gamma i \subseteq \left(\bigcup_{\varphi=0}^{k-1} I_\varphi\right). \]

If, during the next scan of the topology, not a single vertex has been recoded, then the process of ordered recoding ends. The presence in the initial topology of unre-coded vertex codes and elements of their mappings indicates the existence in the graph of contours and breaks. In this case, such vertices and elements of their mappings have no flags, which makes it possible to localize them quickly.

As is clear from the description of the algorithm, when the graph is specified directly, sinks will be located in the zero layer of the ordered topology, and when it is specified inversely, sources will be located there. The order of numbering the vertices in the ordered topology (direct or inverse) is determined by the order of numbering the codes in the CT. By additionally sorting the ordered topology in decreasing order of the ordinal function, one can obtain, at the beginning of the topology record, sources for the direct specification of the graph, and sinks for the inverse specification. Consequently, there are 8 operating modes of the algorithm.

The advantages of the algorithm considered include the following.

1. The combination, in a single algorithm, of two labor-intensive processes: ordering a graph by layers and recoding its vertices.
2. Minimization of the number of comparisons between the codes of the elements of the vertex mapping and the codes of the recoded vertices.
3. The possibility of more rational use of the RAM of the computer, since there is no need to store the entire TS in main memory.
4. Invariance of the algorithm with respect to the method of specifying the graph (direct or inverse).

The proposed algorithm was implemented on the Ural-11B computer. The program contains about 400 commands. The running time of the program for a graph having 1000 vertices and a complexity coefficient of about 2 turned out to be 55 sec. The topology of the graph was entirely accommodated in the machine’s main memory. For a graph with 400 vertices and a complexity coefficient of about 5, the running time of the program was 29 min. The topology array occupied about 90 zones of 256 words each. The main share of the program’s running time is spent searching in the TS for the codes of the elements of the vertex mapping by means of successive comparisons.

REFERENCES

1. Yu. N. Efimov. Algorithm for finding the order function of a network graph. Izv. TPI, vol. 168. TSU Press, 1968.
2. Yu. N. Efimov. Application of small computers in automated planning and control systems. Candidate’s dissertation, Tomsk, 1968.
3. A. V. Kahn. Topological Sorting of large Networks. Communication of the ACM, No. 1, 1962.
4. K. Berge. Graph Theory and Its Applications. Moscow, Foreign Literature Publishing House, 1962.