A Program for Preliminary Analysis of a Complex Network Graph with Localization of Logical Errors

Yu. N. Efimov

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

At present, the automated system of network planning known as PERT [1, 2] is gaining ever wider recognition. The essence of this system consists in a comprehensive study of the technological interdependence of works, the construction of a network graph in the form of a logical sequence of works, and the subsequent analysis of the graph in order to identify areas of potential difficulties. One of the advantages of the system is that individual parts of the graph are compiled directly by the performers of the work. However, when these parts of the network graph are “stitched together” into a single network, logical errors may arise, because of lack of coordination among the individual compilers, in the form of closed circuits and breaks.

For a network graph \(G=(I,\Gamma)\) [3], having some subset of initial \(E i_0\) and terminal \(E i_n\) events, we define a path \(L\) as a sequence of works beginning with some event \(i_0 \in E i_0\).

\[ L=(i_0,\ i_1,\ i_2,\ldots,\ i_k,\ldots). \]

Such paths, in the general case, may be finite or infinite. Obviously, for the last event \(i_n\) of a finite path, \(\Gamma i_n=\varnothing\). We shall call a finite path simple if in it:

a) the last event \(i_n \in E i_n\);

b) no events occur twice.

Logically consistent network graphs have only simple paths. In infinite and finite paths with repeated events, one can always single out a circuit \(\mu\)—a sequence in which the initial event coincides with the terminal one.

\[ \mu=(i_k,\ i_{k+1},\ldots,i_m), \quad \text{where } i_m=i_k. \]

A finite path for which \(i_n \notin E i_n\) has a break of the first kind. If there is at least one event \(i \in I\) for which \(\Gamma^{-1} i=\varnothing\), but \(i \notin E i_0\), then the network graph has a break of the second kind.

Inconsistency of the initial information makes analysis of the network graph difficult and casts doubt on the correctness of the computation results. Certain features of the analysis methods themselves sometimes make it possible to detect logical errors in the initial information. Thus, when calculating time parameters by the iteration method [4] or when find-

of the order function [5], closed circuits in a network graph can be detected by the needlessness of the counting process. Breaks, however, are not detected in this way, but lead to incorrect computation results. The presence of closed circuits leads to “cycling” in programs that use the algorithm of direct analysis (complete enumeration) [6]. Therefore, programs for analyzing network graphs usually include special blocks for interrupting the count and localizing detected errors. After the necessary corrections, the machine analysis often has to be started again from the beginning until the next error is detected, and so on. Such a calculation procedure greatly increases unproductive expenditures of machine time. Naturally, there arises the need to create a special program for localizing all logical errors in a network graph. This program should be used for preliminary analysis of the network graph at the stage of its “stitching together.” At the same time it is desirable to compute also the length of the critical path \((t_p)\), so that, while correcting logical errors, the works can simultaneously be adjusted in time. Let us describe the operating principle of such a program, compiled for the two-address electronic digital computer “Minsk-1.”

The program uses a modified algorithm of direct analysis of a network graph. The initial information (II) for the operation of the program is given in the form of an ordered list of works and their durations [7]. Each work corresponds to an II element occupying one cell of the machine’s operative memory.

\[ i)\ r\ a\ j\ t_{ij}. \]

Before the program begins to operate, the memory cells corresponding to the events \(i_n \notin E^i_n\) are marked with a minus sign. Otherwise these events will be identified as places of breaks of the first kind.

The operation of the program (see the flowchart in Fig. 1) consists of an ordered sequence of steps, called steps to the right and to the left. The first step is made to the right, beginning with the event \(i_0 \in E^i_0\). Steps to the right are performed until an event \(i\) is encountered for which \(I_i=\varnothing\), or until a mark (minus sign) is encountered. In this case the next step to the right is considered impossible, and a step to the left is made. The event to which any step to the left leads is assigned a mark and a time estimate \(t'_n(i)\), computed by the formula

\[ t'_n(i)=\max\,[t'^{*}_n(i);\quad t'_n(j)+t_{ij}],\ \text{where} \]

\(t'_n(i)\) is the greatest length of the path following event \(i\);

\(t'^{*}_n(i)\) is the value of \(t'_n(i)\) obtained by the time of computation.

Each step to the right is recorded by a row in a special path table, characterizing the path traversed and determining the steps to the left. The number of rows in this table, equal to the number of works entering into the path up to the event under consideration, is counted by the counter \(Cr_1\). The contents of \(Cr_1\) are compared with a previously specified value \(\rho \ge \varphi_{\max}(i)\), where \(\varphi_{\max}(i)\) is the maximum value of the order function of the graph being analyzed [5]. When \(|Cr_1|>\rho\), the path table is printed up to the first repeated event \(i_e\). The event \(i_e\) is assigned a mark, and a step to the left is made from it. In this way, circuits are identified from infinite paths.

If, in a step to the right, an event \(i_k\) is encountered for which \(I_{i_k}=\varnothing\), then the path table is printed, i.e., a break of the first kind is localized. The event \(i_k\) receives a mark, and a step to the left is made.

If, in a step to the right, a marked event \(i_m\) is encountered, then the path table is checked to determine whether the path under consideration is the first one.

enters this event. Then a step to the left is made, with the path table printed if \(i_m\) occurs repeatedly, and without printing otherwise. Thus closed contours are isolated from finite paths.

Fig. 1. Flowchart of the program for preliminary analysis of a complex network graph with localization of logical errors

At the \(k\)-th step to the left, the quantity \(t'_n(i)\) is computed for the event \(i_0\), from which the first step to the right is made. \(t'_n(i_0)=t_{\mathrm{cr}}(i_0)\), where \(t_{\mathrm{cr}}(i_0)\) is the maximum length of a path beginning at \(i_0\). The described analysis process is repeated for each \(i_0\in E_{i_0}\).

After correcting the logical errors found, the entire calculation must be repeated in order to check the corrections made and to compute the correct values of \(t'_n(i)\). To localize breaks of the second kind, it is necessary to repeat the analysis for a network graph with the reverse orientation of the operations.

References

1. G. S. Pospelov, A. I. Teiman. Automation of the management processes for the development of large systems or complex aggregates. Izv. AN SSSR, Ser. Tekhn. Kibern., 1963, No. 4.

2. Yu. A. Avdeev, A. P. Nikolaeva. Management of complex developments by the critical-path method. In: Computing Systems, issue II, Novosibirsk, Publishing House of the Institute of Mathematics, Siberian Branch of the USSR Academy of Sciences, 1964.

3. K. Berge. Graph Theory and Its Applications. Moscow, Foreign Literature Publishing House, 1962.

4. A. T. Petrova, N. N. Karnaukhova. On an algorithm for finding the critical path of a network graph. In: Computing Systems, issue II, Novosibirsk, Publishing House of the Institute of Mathematics, Siberian Branch of the USSR Academy of Sciences, 1964.

5. Yu. N. Efimov. An algorithm for finding the order function of a network graph (this collection).

6. G. M. Adelson-Velskii, F. M. Filler. A program for computing network graphs. Zh. Vychisl. Mat. i Mat. Fiz., vol. 5, No. 1, 1965.

7. Yu. N. Efimov, V. I. Kizev, V. M. Razin. On an algorithm for automating computations for the processes of managing the development of complex systems. Izv. TPI, vol. 154, Tomsk State University Publishing House, 1967.