Algorithm for Finding the Ordinal Function of a Network Graph

Yu. N. Efimov

(Presented by the scientific seminar of the computing laboratory of TPI)

In the machine analysis of a complex network graph, which is a dynamic model of a complex of development projects, the problem often arises of the preliminary ordering of events. The essence of ordering reduces to partitioning the set of events of the network graph into separate subsets—classes [1]. Such a partition is useful when it is necessary to introduce new events and activities into the graph, or to delete the network graph or part of it. Preliminary ordering of events by classes also makes it possible to accelerate the process of time analysis of the network graph. Thus, to find the earliest occurrence time of an event \(\{tp(i)\}\) [1, 2, 3], only a single review of the initial information is sufficient.

To partition the events of a network graph into classes, for each event one finds a number called its order. The initial information is then ordered according to the increasing order of the initial events of activities (for computing \(tp(i)\)) or of the terminal events (for \(tn(i)\)). Let us give more rigorous definitions.

Let there be given an acyclic network graph [4] \(G=(I,\Gamma^{-1})\), where \(I\) is a nonempty set of events of the graph, \(I\ne\varnothing\); \(\Gamma^{-1}\) is a mapping of the set \(I\) into \(I\).

Consider some subsets of \(I\):

\[ I(0)=\{i\mid i\Gamma^{-1}=\varnothing\} \]

\[ I(1)=\{i\mid i\Gamma^{-1}\subset I(0)\} \]

\[ \ldots\ldots\ldots\ldots \]

\[ I(k)=\{i\mid i\Gamma^{-1}\subset I(k-1)\}. \]

In the general case,

\[ I(n)=\bigcup_{k=1}^{n} I(k). \]

Obviously, if \(\alpha<\beta\), then \(I(\alpha)\subset I(\beta)\). The order of an event \(i\) of the network graph \(G=(I,\Gamma^{-1})\) will be called the smallest ordinal number \(\alpha\) for which \(i\in I(\alpha)\); \(i\notin I(\beta)\) for all \(\beta<\alpha\). We then set \(z=\varphi(i)\), where \(\varphi(i)\) is the ordinal function of the network graph. Using the mapping \(\Gamma\), inverse to \(\Gamma^{-1}\), one can obtain the subsets

\[ I^{-1}(0)=\{i\mid \Gamma i=\varnothing\} \]

\[ \ldots\ldots\ldots\ldots \]

\[ I^{-1}(k)=\{i\mid \Gamma i\subset I^{-1}(k-1)\}. \]

In the general case,

\[ I^{-1}(n)=\bigcup_{k=0}^{n} I^{-1}(k). \]

Similarly, we obtain the reverse order of the events \(\alpha^{-1}\) and the reverse ordinal function of the network graph \(\varphi^{-1}(i)\). Obviously, there is a one-to-one dependence between the functions \(\varphi(i)\) and \(\varphi^{-1}(i)\):

\[ \varphi^{-1}(i)=\varphi_{\max}(i)-\varphi(i), \quad \text{where} \]

\[ \varphi_{\max}^{-1}(i)=\varphi_{\max}(i), \quad \text{where the maximum} \]

is taken over all events \(i\in I\). Taking the duration of each activity of the network graph to be equal to one, we obtain \(\varphi(i)=t_p(i)\), where \(t_p(i)\) is the earliest time of occurrence of event \(i\).

Thus, in order to find the ordinal function, one may use any algorithm for computing \(t_p(i)\) [1, 3, 5, 6]. Finding \(\varphi(i)\) for the purpose of accelerating the calculation of time parameters (using ordering by classes) makes no sense if the same algorithms are used to compute the ordinal function as for the time analysis. It seems advisable to develop special algorithms that would more fully take into account both the specifics of the problem posed and the advantageous features of the digital computer on which they are implemented.

Let us describe one of the possible variants for solving the problem of finding the ordinal function of a network graph on the two-address computer “Minsk-1.” The initial information \((UU)\) on the network graph is given in the form of a list of activities and their lengths, arranged in any order. We order the activities \(UU\) according to their starting events [6] and obtain information of the form

\[ i)\quad r\ a\ jt_{ij}\varphi(i), \quad \text{where} \]

\(i\) — the number of a memory cell of the machine, equal to the number of the initial event of the activity;

\(j\) — the number of the terminal event of one of the activities leaving event \(i\);

\(r\) — the number of activities leaving event \(i\);

\(a\) — the conditional address of another activity leaving event \(i\).

The actual address is \((a+c)\), where \(c=\text{const}\). Usually \(c\) is taken equal to the largest event number of the network graph.

\(\varphi(i)\) is the ordinal function. For the time being, \(\varphi(i)=0\) for all \(i\in I\).

From the definition of the ordinal function of a network graph it follows that if all events having \(\varphi(i)=\rho\) form a known subset \(I_1(\rho)\subset I\), then all events of the subset \(I_1(\rho+1)=\{i,\ i\in \Gamma I_1(\rho)\}\) take the values \(\varphi(i)=\rho+1\). In this case, if some event of the subset \(I_1(\rho+1)\) already has a computed order function, it should be replaced by the new one. Hence the operation of the algorithm reduces to the following. Assign the initial event \(i_0\) the value \(\varphi(i_0)=0\). At the first step we find the subset of events \(\Gamma i_0\) and assign them the value \(\varphi(i)=1\). For this purpose, from the contents of cell \(i_0\) the quantities \(j\in \Gamma i_0\) and \(a\) are singled out. At address \(j\) the value \(\varphi(j)=1\) is entered, and from the contents of cell \((a+c)\) the quantities \(j\) and \(a\) are again singled out. The process continues until the value \(a=0\) is singled out, which indicates that all events of the subset \(\Gamma i_0\) have been assigned the value \(\varphi(i)=1\). At the second step, for each event \(i\) having \(\varphi(i)=1\), we find the subset \(\Gamma i\) in the manner just described. To each event of the subset \(\Gamma i\) we assign \(\varphi(i)=2\). At the \(k\)-th step, for events having \(\varphi(i)=k\), we find the subsets \(\Gamma i\) and assign the value \(\varphi(i)=k+1\).

The process continues until, at some step, all the subsets found are \(\Gamma_i=\varnothing\). At this point the computation of the ordinal function of the network graph ends. Obviously, the number of the steps described is equal to \(|\varphi_{\max}(i)+1|\). The almost complete absence of arithmetic operations, and also the need to scan at each step only the list of events rather than the general list of jobs, make the algorithm faster in comparison with known algorithms for computing \(tp(i)\) and \(tn(i)\).

Fig. 1. Example of a network graph

Let us consider the described algorithm by means of an example. Suppose that the initial information on the network graph (Fig. 1) is given in Table 1. By the ordering program [6], for \(C=6\) (since 6 is the largest event number) the information is transformed into the form shown in the left-hand part of Table 2. The time estimates and the values of \(r\) are not taken into account, since they do not participate in the operation of the algorithm. The right-hand part of Table 2

Table 1

gives the values of \(\varphi(i)\) computed at each step. Empty cells mean that the value of \(\varphi(i)\) has remained unchanged. At the first step, from \(i_0=1\) we select \(j=2\) and \(a=4\). In cell 2 we enter \(\varphi(2)=1\), and from cell \(a+c=4+6=12_8\) we select \(j=6\), \(a=0\). In cell 6 we enter \(\varphi(6)=1\), and this completes the first step, since \(a=0\). At the second step, from cell 2 [since \(\varphi(2)=1\)] we select \(j=3\), \(a=1\). We enter \(\varphi(3)=2\). From cell \(a+c=6+1=17_8\) we select \(j=5\), \(a=3\). We enter \(\varphi(5)=2\). From cell \(6+3=11_8\) we select \(j=6\), \(a=0\). We enter \(\varphi(6)=2\). Since, by the time event 6 is considered, it has already changed the value of \(\varphi(6)\) from 1 to 2, we do not find \(\Gamma'_6\) for it (because of this the computation process is somewhat accelerated). Proceeding in this way, we fill in the right-hand part of Table 2. At the fifth step no changes are made in the values of \(\varphi(i)\), since event 4 has no outgoing jobs (\(\Gamma_4=\varnothing\)). The last column of Table 2 contains the resulting values of \(\varphi(i)\).

References

1. K. A. Bagrinovskii, I. B. Rabinovich. Formulation of the problem of analyzing 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.

2. G. S. Pospelov, A. I. Teiman. Automation of control processes for the development of large systems or complex systems. Publishing House of the USSR Academy of Sciences, series Technical Cybernetics, no. 4, 1963.

3. L. R. Ford. Network flow-theory, Rand Corp. paper, P-923, 1956.

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

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

6. Yu. N. Efimov, V. I. Kizev, V. M. Razin. On an algorithm for automating calculations for control processes in the development of complex systems. Proceedings of TPI, vol. 154, Tomsk State University Publishing House, 1967.