On an Algorithm for Transforming Connected Components

V. K. Pogrebnoy

(Presented by the Scientific and Technical Seminar of the Research Institute of Automated Electric-Modeling at TPI)

The need to develop an algorithm for transforming connected components arises at the stage of tracing wiring connections when solving problems of automating the engineering-design stage in the design of computing devices.

In circuits of computing devices, situations often occur in which a certain set of contacts (elements of a component) must be directly connected. In the case where the number of contacts in such a set exceeds two, the problem arises of minimizing the total length of the wires connecting the contacts of the given set.

In terms of graph theory, the problem under consideration consists in constructing a minimum spanning tree. Exact methods for solving this problem have been developed for the case when the number of edges $\alpha$ incident to a single vertex is not restricted [1], [2]. The use of these methods with restrictions imposed on the number $\alpha$ causes a significant deviation of the total length of the edges of the tree obtained from the corresponding sum in the minimum tree. If, for $\alpha = 3$, such a deviation is to some extent permissible in practical examples of wiring, then for $\alpha = 2$ it increases substantially, which indicates the need to develop a special method for solving this problem.

The problem of constructing a minimum tree with $\alpha = 2$ arises not only in connection with technical restrictions on the number of wires connected to a single contact. More often it arises when sequential chains are present in circuits, or in the case where such chains are formed artificially [3]. As a rule, in such chains the contacts of the beginning and the end are known in advance. If, moreover, the distance between such contacts is small (for example, adjacent contacts of a connector), then the problem arises of finding an actually closed chain with the minimum sum of edge lengths.

Algorithm [4], which takes into account the restriction on the number $\alpha$, is sufficiently effective in constructing chains in which the beginning and the end are not fixed in advance. However, in the presence of this restriction its effectiveness decreases noticeably. In addition, the effectiveness of this algorithm depends substantially on the particular arrangement of the vertices in the graph.

The problem under consideration can also be formulated as a discrete programming problem. However, practice indicates the considerable difficulties that arise when solving such problems in this formulation.

The proposed method for solving this problem makes it possible to obtain a closed chain, as well as an open chain with a prescribed beginning and end, that is close to optimal.

We shall consider a graph with \(n\) vertices and a matrix \(L=\|l_{ij}\|\) of the distances between them. The problem consists in traversing all \(n\) vertices by a closed chain of minimal length (we regard an open chain as a special case of a closed one).

In constructing a closed chain, we shall call a chain of the form \(m—m,\ m\in n\), the initial chain. In the case of constructing an open chain with prescribed initial vertex \(m\) and terminal vertex \(\kappa\), the initial chain has the form \(m—\kappa\). In Fig. 1 the initial chain \(m—m\) is shown schematically. The dots conventionally indicate the places that will be occupied in the final chain by the remaining \(n-1\) vertices.

Let us try to extend this chain, i.e., to include in it one of the remaining vertices. The question arises as to which of the vertices should be included in the given chain first. When some vertex \(\lambda\) is included, the chain \(m—\lambda—m\) is obtained. The vertex \(\lambda\) in such a chain has the possibility of “occupying” one of \(n-1\) places, i.e., it is given the maximum possible opportunity, in the process of including subsequent vertices, to move over all places of the chain \(m—m\).

Fig. 1.

The possibility of moving the \(i\)-th vertex at the \(f\)-th step of inclusion will be expressed by the concept of the degree of freedom \(r_i^f\). Obviously, at the first step

\[ r_i^1 = n-1. \]

At subsequent steps the degree of freedom decreases and is determined by the expression

\[ r_i^f = n-f. \]

Let us compare two vertices \(i\) and \(j\), with \(l_{im}>l_{jm}\). With respect to vertex \(j\) there is greater reason to suppose that in the final chain it will occupy a place closer to vertex \(m\) than vertex \(i\). Vertex \(j\) is “attracted” to vertex \(m\) and therefore possesses less “mobility,” i.e., a smaller degree of freedom. Possessing a greater degree of freedom, vertex \(i\) will interfere less with the inclusion of the remaining vertices in the chain; therefore, when choosing a vertex to include in the chain, it is preferable to vertex \(j\).

In the general case, at each \(f\)-th step, the vertex \(\lambda\) to be included is determined from the condition

\[ \max \sum_{i\in Q_f} l_{\lambda i}, \tag{2} \]

where \(Q_f\) is the set of vertices constituting the initial chain for the \(f\)-th step.

In the case under consideration, after inclusion of the vertex \(\lambda\), the initial chain for the inclusion of the next, for example the \(\kappa\)-th, vertex is the chain \(m—\lambda—m\). In this case \(Q_f=\{m,\lambda\}\). When the \(\kappa\)-th vertex is included, it is immaterial into which link of the chain it will be included. However, at subsequent steps the question arises as to into which link of the chain the next vertex \(\lambda\) must be included. Such a link \(l_{ij}\) is determined at each step from the condition

\[ \min \left|l_{\lambda i}+l_{\lambda j}-l_{ij}\right|. \tag{3} \]

Below is the logical scheme of the algorithm for transforming connected components with the number \(\alpha=2\). The notation adopted in [5] is used.

\[ \begin{aligned} U={}&A_0A_1P_1 \overset{1}{\uparrow} A_2A_3 \overset{4}{\downarrow} A_4 \overset{3}{\downarrow} A_5A_6P_2 \overset{2}{\uparrow} A_7\omega \overset{3}{\uparrow}\overset{1}{\downarrow} A_8\omega \overset{4}{\uparrow}\overset{2}{\downarrow} P_3 \overset{5}{\uparrow} A_{10} \overset{6}{\downarrow} \\ &\overset{6}{\downarrow}\overset{7}{\downarrow} A_{11}A_{12}A_{13}P_4 \overset{5}{\uparrow} A_{14}A_{15}\omega \overset{8}{\uparrow}\overset{5}{\downarrow} A_9\omega \overset{7}{\uparrow}\overset{8}{\downarrow} A_k, \end{aligned} \]

where \(A_0\) is to enter into the digital computer the initial data on the coordinates of the component vertices

\[ \{x_1y_1,\ x_2y_2,\ \ldots,\ x_ny_n\},\ \{m,\ k\}. \]

\(A_1\) — on the set of \(n\) vertices, construct a complete graph and represent it in matrix form. The matrix element \(l_{ij}\) is determined by the formula

\[ l_{ij}=\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}. \]

\(P_1\) — check whether a closed chain or a chain between vertices \(m,\ k\) is determined. If \(P_1=1\), proceed to operator \(A_2\); if \(P_1=0\), proceed to \(A\).

\(A_2\) — select the maximum element \(l_{ij}\) from the matrix.
\(A_3\) — enter the vertex numbers \(i\) and \(j\) into \(RP_1\).
\(A_4\) — sum, row by row, the matrix elements corresponding to the numbers in \(RP_1\), under the condition that the sum of the elements is equal to zero if one of the terms is equal to zero. Enter the sums into \(RP_2\).
\(A_5\) — from the sums obtained in \(RP_2\), select the maximum.
\(A_6\) — enter into \(RP_1\) the number of the vertex corresponding to this sum.
\(P_2\) — check the condition \(Q_f<n\).
If \(P_2=1\), proceed to \(A_7\); if \(P_2=0\), proceed to \(P_3\).
\(A_7\) — sum, row by row, the elements of the matrix column with the number entered in \(RP_1\) by \(A_6\), with the corresponding sums in \(RP_2\). Enter the results into \(RP_2\), having first excluded the preceding sums from it. Transfer control to \(A_5\).
\(A_8\) — enter the vertex numbers \(m\) and \(k\) into \(RP_1\) and transfer control to \(A_4\).
\(A_9\) — write into \(RP_3\) the initial chain \(m—k\) and transfer control to \(A\).
\(P_3\) — check whether a closed chain or a chain between vertices \(m\) and \(k\) is determined. If \(P_3=1\), proceed to \(A_{10}\); if \(P_3=0\), proceed to \(A_9\).
\(A_{10}\) — write into \(RP_3\) the initial chain \(m—m\).
\(A_{11}\) — for each link of the initial chain, determine the value \(l=l_{\lambda i}+l_{\lambda j}-l_{ij}\), where \(\lambda\) is the next number from \(RP_1\) to be included in the initial chain.
\(A_{12}\) — from all values of \(l\), select \(l_{\min}\).
\(A_{13}\) — include the number \(\lambda\) corresponding to \(l_{\min}\) and \(l_{ij}\) in the initial chain between vertices \(i\) and \(j\).
\(P_4\) — check whether all vertex numbers are contained in \(RP_3\). If \(P_4=1\), proceed to \(A_{14}\); if \(P_4=0\), proceed to \(A_{11}\).
\(A_{14}\) — determine the sum of the lengths of the chain links in \(RP_3\).
\(A_{15}\) — print the sequence of vertices of the chain \(RP_3\) and the sum of the lengths of its links.
\(A_k\) — end of the algorithm.

A program for the M-20 machine was compiled according to this algorithm. Analysis of the results of solving a number of practical problems showed the advantage of the proposed algorithm in comparison with known ones.

REFERENCES

1. K. Berge. Graph Theory and Its Applications. Foreign Literature Publishing House, 1962.
2. R. K. Prim. Shortest connecting networks and some generalizations. “Cybernetic Collection,” No. 2. Foreign Literature Publishing House, 1961.
3. Automation of several stages in the design of computing devices. Report on a research topic. Tomsk, TPI, 1969.
4. M. E. Shtein, V. S. Gaydaenko, V. S. On problems of routing mounting connections. In: The Use of Computers for the Design of Digital Devices. “Soviet Radio,” Moscow, 1968.
5. Synthesis of Discrete Automata and Control Devices. “Nauka,” Moscow, 1968.