Vol. 243

1972

SOME QUESTIONS OF GENERATING GRAPHS ON A COMPUTER

Yu. N. EFIMOV

(Presented by the scientific seminar of the Computing Laboratory of TPI)

A large class of problems in applied mathematics can be reduced to problems formulated in terms of graph theory [1]. These are, above all, transportation and combinatorial problems, flow-distribution problems, problems connected with the economical recording and processing of large bodies of information, and also a large group of extremal problems of scheduling theory. Problems of scheduling theory arise when it is necessary to order in time the course of discrete processes carried out with the aid of a limited set of processors. Such problems occur in operational planning and management of enterprises, in controlling the course of development work by means of network methods (PERT systems), in the theory of algorithms, in game theory, and in various other special disciplines.

All the problems listed above are problems of analyzing graphs of large dimension. When solving network problems on a computer, it would apparently be expedient to be able to generate various networks for the simulation of real relations. Generators of random networks may find wide application in the most diverse mathematical investigations that use graph theory.

Programs for the analysis of large graphs on a computer are usually logically complex and create great difficulties in debugging. It is often difficult to determine the limits of applicability of a program that has been developed, so that there is a danger that the program will not satisfy the requirements of some real case. By generating random networks, one can quickly test the program in various modes and establish the limits of applicability.

Exact solutions of extremal network problems of scheduling theory have been found only for exceptionally simplified models, while the principal practical results are based on heuristic considerations. In this situation, in order to estimate the degree of effectiveness of a heuristic algorithm and the limits of its applicability, it is convenient to use the following dependence (by analogy with [2]):

\[ M[K] = f(P), \]

where \(K\) is the coefficient of effectiveness of the algorithm,
\(P\) is a graph parameter.

It is obvious that such a dependence is not difficult to obtain by generating networks with variable \(P\) in the necessary interval.

In the streaming solution of single-type problems in a network formulation by one and the same program, it is necessary to estimate in advance the solution time

each problem. The construction of the function \(t=f(P)\) is also easily carried out with the aid of a graph generator.

In graph theory, a network generator can evidently find effective application for the study of graphs with random topology.

This far from complete list of possible uses of a network generator shows that the development of problems of graph generation may prove very fruitful. However, from the literature sources we know of no instance in which such problems have been posed and solved. In the present work one of the possible algorithms for generating random networks on general-purpose computers is proposed.

Suppose that for a computer we have a programmed sensor (random-number generator), generating integer random numbers \(a_i\), distributed according to some law (for example, uniformly) in the range \(\alpha \div \beta\). We shall call \(\alpha\) and \(\beta\), respectively, the lower \((a_{\mathrm{lg}})\) and upper \((a_{\mathrm{ug}})\) bounds of the numbers \(a_i\).

We shall represent a graph in the form of a set of vertices \(J\) and their mappings \(\Gamma\), so that the record of the information for each vertex \(i\) has the form:

\[ \begin{gathered} i,\ \omega_i\\ j_1,\ p_1\\ j_2,\ p_2\\ \cdot\quad \cdot\quad \cdot\quad \cdot\quad \cdot\\ j_\omega,\ p_\omega, \end{gathered} \]

where \(i, j\) are the numbers of vertices, with \(j \in \Gamma_i\);

\(\omega_i\) is the local degree of vertex \(i\) (the number of arcs leaving \(i\));

\(p\) is some parameter \(p\) (duration, capacity, cost, etc.) assigned to the arc \((i,j)\).

Since many algorithms for graph analysis, especially in automated control systems and in network-planning systems, require preliminary ordering of the initial information about the graph by layers [3], it is desirable that the graph be generated at once ordered in the corresponding manner.

A general idea of the size and topology of a graph is provided by knowledge of the following numerical characteristics:

\[ |\varphi| \text{ — the number of layers;} \]

\[ |\varphi| \text{ — the number of vertices in layer } \varphi; \]

\[ \omega_i \text{ — the number of arcs leaving vertex } i. \]

It is obvious that the above-listed data must serve as the initial information for the computer, on the basis of which the network will be generated. Moreover, for greater flexibility of the network generator, provision should be made for specifying each of these parameters either in the form of corresponding upper and lower bounds, and in each particular case obtaining the parameter with the aid of the random-number generator, or in the form of a specific number. The second method is a special case of the first and is not difficult to implement by assigning some additional functions to the random-number generator. For example, when \(a_{\mathrm{ug}}=0\), implement the output by the random-number generator always of the definite number \(a=a_{\mathrm{lg}}\).

Let us also note that in many cases the zero layer \(\varphi_0\) \((\Gamma|\varphi_0 := \varnothing)\) has certain specific features in comparison with the other layers. For example, it contains a small number of vertices, since these vertices correspond either to commodity items in automated control systems, or to sources in transportation networks, or to final objectives of developments in network schedules of network-planning systems. Therefore we introduce an additional characteristic of the network,

\[ ||\varphi_0|| \text{ — the number of vertices of the zero layer,} \]

which we shall specify analogously to those named earlier.

Taking the foregoing into account, the following algorithm for generating graphs on a computer is proposed:

1. Draw the number of layers \(|\varphi|\); \(C_1 := |\varphi|\).

1. Draw \(|J_{\varphi 0}|\); \(i, R := |J_{\varphi 0}|\); \(E_{i0} := |J_{\varphi 0}|+1\); \(E := 1\).

2. Draw \(|J_{\varphi}|\); \(C_2 := |J_{\varphi}|+1\); \(C_3 := 1\).

3. \(C_3 := C_3 - 1\); \(C_3 = 0\)? Yes. Go to item 9. No. Go to item 5.

4. \(E_{i0} = 0\)? Yes. Go to item 13. No. Go to item 6.

5. \(E_{i0} := E_{i0} - 1\); \(j := E_{i0}\).

6. Draw the parameter \(p_{ij}\).

7. Formation of row \(j, p_{ij}\) in the \(i\)-th record. Go to item 4.

8. \(C := 2\); \(C_2 := C_2 - 1\); \(C_2 = 0\)? Yes, go to item 12. No. Go to item 10.

9. \(i := i + 1\); draw \(\omega_i\), \(C_3 := \omega_i + 1\).

10. Formation of the “header” \((i, \omega_i)\) of the \(i\)-th. Go to item 4.

11. \(E := R + 1\); \(R := i\); \(C_1 := C_1 - 1\); \(C_1 = 0\)? Yes. Stop the machine; the graph has been obtained. No. Go to item 3.

12. \(C := C - 1\); \(C = 0\)? Yes. Go to item 14. No. Go to item 15.

13. \(C := 1\); draw \(j\) for \(j_{\mathrm{ng}} := 1\); \(j_{\mathrm{vg}} = R\); go to item 7.

14. Draw \(j\) for \(j_{\mathrm{ng}} = E\), \(j_{\mathrm{vg}} = R\); go to item 7.

The algorithm described has been implemented on the Ural-11B computer. The program used an RNG with a uniform distribution. As information about the graph accumulated, it was copied onto magnetic tape. The time for generating and recording on the ML network containing 4000 vertices, 10 layers, and \(\omega_i\) in the interval \(2 \div 10\) is 10 minutes. The program was used in debugging certain algorithms developed for ASUP-Tomsk [4]. Experience with its use proves the expediency of developing programs of this kind.

Further research in the area of creating generators of graphs of a specified structure (for example, trees, graphs with closed cycles, planar graphs, etc.), as well as graphs with characteristics produced by various RNGs that differ in their distribution laws, evidently appears advisable.

REFERENCES

1. K. Berge. Theory of Graphs and Its Applications. IL, Moscow, 1962.

2. Yu. N. Efimov. Some questions of the statistical study of network graphs. Izvestiya TPI, vol. 187, Tomsk (in press).

3. Yu. N. Efimov. An algorithm for finding the ordering function of a network graph. Izvestiya TPI, vol. 168, Tomsk, 1969.

4. Yu. N. Efimov, V. I. Kizev, V. I. Nevpaev, F. I. Peregubov, P. A. Sedelnikov. Basic principles of construction and functioning. ASUP-Tomsk. (This collection).