TIME ANALYSIS OF LARGE NETWORK GRAPHS WITH BLOCK STRUCTURE

Yu. N. Efimov

(Submitted by the scientific seminar of the Department of Computer Engineering, TPI)

Known programs [1–4] for the analysis of network graphs use only the random-access memory (RAM) of electronic machines and process comparatively small networks. The analysis of large network graphs on digital computers with a limited amount of random-access memory is a rather difficult problem, requiring the use of external memory. For the analysis of large networks it is comparatively simple to develop programs that implement the same algorithms and use an external storage device as random-access memory. However, frequent access to a magnetic-tape unit reduces the reliability of the computations and increases machine time to such an extent that time analysis of most graphs becomes unrealistic. The problem therefore arises of developing methods and techniques for the most effective use of RAM so that, in the analysis of large networks, the number of accesses to a magnetic-tape unit is reduced to a minimum. It is obvious that these methods must be based on partitioning the original network into parts and analyzing these parts separately.

Every development being modeled consists of separate, more or less isolated parts, which is also reflected in the model in the form of graphically isolated complexes of activities and events. Each such complex (we shall call it a block) is a subgraph \(G_k=(I_k, U_k)\) of the original network graph \(G=(I, U)\), where \(I_k, U_k\) are, respectively, the set of events and activities of this subgraph, with \(I_k \subset I,\; U_k \subset U\). The problem is posed of constructing, from the known subgraphs \(G_k\), an aggregated (less detailed) network graph \(G^1\) that preserves the basic parameters and interrelations of the original graph \(G\). Obviously, the aggregated graph \(G^1\) will contain a significantly smaller number of activities than the original \(G\), and can be processed by ordinary methods. Thus, it is necessary to develop a system of equivalent transformations by means of which a block can be reduced to one or several activities.

Let us introduce several definitions and notations.

The events of the block \(G_k\) will be denoted by \(i^k, j^k\), where \(k\) is the number of the block. An event \(i_0^k \in I_k\) will be called an initial event of the block \(G_k\) if

\[ \Gamma^{-1} i_0^k \cap I_k \ne \Gamma^{-1} i_0^k . \tag{1} \]

In the general case, a block may have some subset \(E i_0^k\) of initial events. It is obvious that the initial events \(E i_0\) of the graph \(G\) are—

are initial events of the block into which they enter (for them \(\Gamma^{-1} Ei_0 \cap I=\varnothing\)), i.e., we have

\[ Ei_0 \subset Ei_0^\kappa \quad \text{for } Ei_0 \subset I_\kappa . \tag{2} \]

An event \(i_n^\kappa \in I_\kappa\) will be called a terminal event of the block \(G_\kappa\) if

\[ \Gamma i_n^\kappa \cap I_\kappa \ne \Gamma i_n^\kappa . \tag{3} \]

By analogy with initial events, we introduce the concept of the subset \(Ei_n^\kappa\) of terminal events of the block \(G_\kappa\) and obtain the expression

\[ Ei_n \subset Ei_n^\kappa \quad \text{for } Ei_n \subset I_\kappa \;(\text{since } \Gamma Ei_n \cap I=\varnothing). \tag{4} \]

It is obvious that

\[ Ei_n^\kappa \equiv Ei_0^{\kappa+1}. \tag{5} \]

The initial and terminal events of the block \(G_\kappa\) constitute the subset of boundary events \(\overline{I}_\kappa\) of this block,

\[ \overline{I}_\kappa = Ei_0^\kappa \cup Ei_n^\kappa . \tag{6} \]

By the aggregated network graph \(G^1\) of the given graph \(G\) we shall mean a network graph whose events are all the events of the set \(I_s\):

\[ I_s=\bigcup_{\kappa=1}^{m} \overline{I}_\kappa , \tag{7} \]

where \(m\) is the number of blocks in \(G\).

Every activity \((i^s,j^s)\) of length \(t(i^s,j^s)\) will be an activity of the aggregated graph \(G^1\) provided the following conditions are satisfied:

a) \(i^s \subset Ei_0^\kappa,\quad j^s \subset Ei_n^\kappa\);

b) there exists one or several paths leading from \(i^s\) to \(j^s\) in the graph \(G\);

c) the value \(t(i^s,j^s)\) is equal to the length of the longest of these paths.

It is not difficult to show that, for the aggregated graph \(G^1\) constructed in the described manner, the equalities

\[ t_p'(j)=t_p(j), \tag{8} \]

\[ t_n'(j)=t_n(j), \tag{9} \]

hold, where \(t_p'(j), t_n'(j), t_p(j), t_n(j)\) are the early and late occurrence times of event \(j\), respectively, in \(G^1\) and \(G\).

Thus, the basic problem of processing a network model of block structure can be reduced to the following:

a) find in the block the critical paths leading from \(Ei_0^\kappa\) to \(Ei_n^\kappa\);

b) compute the lengths of these paths;

c) form the information about the graph \(G^1\) in the form

\[ (m)i^s j^s t(i^s,j^s), \tag{10} \]

where

\(m\) is the number of the cell in the machine’s RAM,

\(i^s, j^s\) are, respectively, the initial and final events of the activity of the sought graph \(G'\),

\(t(i^s,j^s)\) is the duration of this activity.

To solve the stated problem we shall use the following numbering of the original graph \(G\) (Fig. 1). We divide each event \(i \in I_s\) into three sectors. We number the events of the subset \(I_s\) in order (from

Fig. 1. Network model of a system with event numbering convenient for machine analysis. (The events of the subset \(I_s\) are highlighted)

units onward) in the octal number system, and write the numbers in the upper sector. These will be the (external) numbers of the sought graph \(G'\). Next we number the events \(i^k \in I_k\) within each block, assigning initial numbers to the source events of the block. The resulting internal numbers of the events of a block are written in the right-hand sector for \(i^k \in E i_0^k\) and in the left-hand sector for \(i^k \in E i_n^k\). Thus each event of the original graph \(G\) is numbered, with boundary events having three numbers, and source and terminal events having two numbers each (Fig. 1). In the course of analysis, depending on the system in which the event is considered, one of the three numbers is taken. It should be noted that the proposed event numbering makes it possible to analyze individual blocks independently of one another, considering them in any order.

Let us consider the methodology and the program for analyzing network graphs with the described event numbering on the “Minsk-1” computer.

The initial information about the graph \(G\) is recorded on magnetic tape in the form of separate arrays. Each array contains information about one block, which includes a description of the block and a list of all activities. The description of the block contains lists of the initial and terminal events of the block (their external numbers), as well as the block number and the checksum of the array. The topology of the block and the time characteristics of the activities are specified in the form of a list, each line of which characterizes one activity and has the form

\[ P_2 i^k j^k t(i^k,j^k) P_1, \tag{11} \]

where

\(i^k, j^k\) are the internal numbers of the events defining the activity;

\(t(i^k, j^k)\) is the length of the activity;

$P_1$ — indicator of a terminating activity.

$P_1 > 0$ for activities entering the terminating event of the block, with the value $P_1$ taken equal to the ordinal number of this event in the description of the block under consideration.

$P_1 = 0$ for all other activities of the block.

$P_2 = 1$ only for terminating activities whose terminal events satisfy the condition:

\[ \Gamma Ei_n^k \cap I_k' \ne \Phi . \tag{12} \]

In all other cases $P_2 = 0$. As an example, Table 1 gives a record of information on several activities of block 1 of the network graph shown in Fig. 1.

Text in the flowchart:

• Restoration commands
• Preparation of the working field
• Reading information about the block
• Is the information correct?
• no
• yes
• $C_{\text{err}} : C_{\text{err}} + 1$
• Is this the third failure?
• no
• yes
• Stop 1 (error in writing to tape)
• Print block number
• Recoding the word number
• Has the entire zone been read?
• no
• yes
• Restore word number
• Recoding the zone number
• Preliminary search for the zone
• Block calculation
• Have all blocks been calculated?
• yes
• no
• Stop

Fig. 2. Flowchart of the program for analyzing large network graphs of block structure

Figure 2 presents a flowchart of the program for analyzing large network graphs of block structure. Information about each block is read from magnetic tape into the machine’s RAM. After checking the correctness of the information read, the number of the block being analyzed is printed, a preliminary search is organized for the zone of the magnetic tape containing information about the next block, and then the block is calculated.

Fig. 3. Flowchart of the program for time analysis of blocks

Flowchart labels:

• Restoration commands
• Selection from OB: \(l_0^i \in E_{i0}^{*}\)
• \(l_0^i = 0?\)
• yes
  • Exit to feedback cell
• no
  • \(\alpha := \alpha + 1\)
  • Restoration of the length-storage fields of the paths
  • \([C_4] = 1?\)
  • yes
    • Restoration of path-enumeration commands
  • no
    • Restoration of path-printing commands
  • \(0 \to C_4,\ \alpha \to f\)
  • \(C_4 := C_4 + 1\)
  • Record the path line
  • \(P_1 = 0?\)
  • yes
    • Selection \(j \to f\)
  • no
    • \(P_2 = 0?\)
    • no
      • Restoration of transition to I
    • yes
      • Restoration of transition to II
    • Finding the path length
    • Is the path equal to the corresponding previously stored one?
    • yes
      • Switch
      • print
      • Print paths and form information on \(G\)
    • no, less
      • Store the new path length
    • no, greater
      • Switch
      • I
      • II
      • Finding the boundary line
      • \(\tau = 1?\)
      • no
        • \(a + c \to f\)
      • yes
        • \([C_4] = 0?\)
        • yes
          • Switch
        • no
      • enumeration
      • print
      • Print data on \(G'\) and record them in NM
      • Readdressing of the original event block

Additional branch labels visible in the diagram:

• enumeration
• print
• no
• yes
• less
• greater
• I
• II

Such a procedure is repeated for each \(G_k \subseteq G\). It should be noted that a preliminary search for the zone greatly reduces the total time of the analysis, since practically within the time required to search for the zone a complete calculation of the block is carried out.

For the calculation of individual blocks, a somewhat modified exhaustive-search algorithm [3] is used, adapted for the analysis of network graphs of multipurpose developments. The information on the block is processed in two stages (the flowchart is in Fig. 3), and in each of them the same program sections are used, connected in different ways by means of switches.

Table 1

At the first stage, all possible paths in the block are constructed and \(n\) lengths of maximal paths are stored, respectively for each terminal event of the block (the value of \(n\) is equal to the number of terminal events in the block). At the second stage, the path matrices are constructed again and their lengths are compared with those stored earlier. When the resulting lengths coincide with the corresponding previously stored ones, the path matrices are printed, and information about the graph \(G'\) is formed in the form (10). Information about the graph \(G'\) is output to the perforator or, as it is accumulated, is rewritten onto tape.

As a result of analyzing all blocks, we obtain the initial information about the enlarged graph \(G'\), and a detailed decoding of all its activities in the form of a set of matrices output for printing. It is obvious that, after analyzing the enlarged graph \(G'\), using this decoding, it is easy to construct the critical path in the original graph \(G\).

REFERENCES

1. A. M. Gorlov. Calculation of network graphs by the critical-path method. Gipro-tis. Moscow, 1965.

2. G. M. Adelson-Velsky, F. M. Filler. A program for calculating network graphs. Journal of Computational Mathematics and Mathematical Physics, vol. 5, no. 1. 1965.

3. Yu. N. Efimov. Analysis of network graphs on the “Minsk-1” electronic digital computer. Annotations of programs solved on digital computers. Issue 4. Moscow, 1967.

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