PROGRAM FOR THE ANALYSIS OF COMPLEX SYSTEMS “GRAPH-01”

L. A. Naumov, V. P. Trefilova, E. I. Tsimbalist

(Presented by the scientific seminar of the Department of Radio Engineering)

The article proposes a program for the analysis of complex systems represented by signal graphs, implementing the algorithm set forth in [1]. The flowchart of the program is shown in Fig. 1.

Instructions for the program “Graph-01”

1. The initial data are entered in the form of an array \(A\) and the numbers \(N\) and \(s\).

1.1. \(N\) is the number of rows of the array \(A\), \(s\) is the maximum number of nonzero elements in a row of the adjacency matrix.

1.2. To find the denominator, \(A\) is the table of half-stars of the output of the graph. To find the numerator, \(A\) is the table of half-stars of the output of a part of the graph for given \(i, j\). Each row of the table is supplemented with zeros up to \((s+1)\) elements. The table is entered by rows.

1. The program is written for the “Signal-2” translator, and the implementation of operators on punched cards 3, 4, 7 in the given form is inadmissible. The notation is decoded as follows: let \(N=7\), then

\[ \text{3. switch } l := l_1, l_2, l_3, l_4, l_5, l_6, l_7. \]

1. The array \(\delta\) is printed. The symbol 9 separates contours.

2. If the array \(a\) or \(N, S\) is absent, a stop at the 10th command is possible.

3. The approximate computation time for \(N=6, s=5\) is 35 sec.

Program “Graph-01” [2, 3]

1. begin integer \(d, i, i1, j, k, k1, n, S, q, q1, r1, v, w, w1, h, t,\)
   \(x, x1, y, z, и, ш, ю, я, \alpha, \gamma1, B, C, N, N1, N2, N3, N4;\)

2. integer array \(a[1:N,\,1:N1];\) integer array \(b[1:N,\,1:N2];\)
   integer array \(\gamma[1:N,\,1:N3];\) integer array \(r[1:N];\) integer array
   \(c,\delta[1:N4];\)

3. switch \(l := l1, l2, l3, \ldots, lN;\) switch \(p := p1, p2, p3, \ldots, p(N-2);\)
   go to \(\phi;\)

4. \(l1: x := 1;\) go to \(A2;\) \(l2: x := 2;\) go to \(A2;\) \(\ldots\) \(lN: x := N;\)
   go to \(A2;\)

5. \(p1:\) go to if \(C \ne b[1,k] \land C \ne b[2,k]\) then \(M3\) else \(M4;\)

6. \(p2:\) go to if \(C \ne b[1,k] \land C \ne b[2,k] \land C \ne b[3,k]\) then \(M3\)
   else \(M4;\ \ldots\)

7. \(p(N-2):\) go to if \(C \ne b[1,k] \land C \ne b[2,k] \land \ldots \land C \ne b[N-1,k]\) then \(M3\) else \(M4;\)

1. F: p 0042 (a, N, s);
2. zh 3: N1 := s + 1; begin N2 := 1; q := 1; if N = OV N = 1
   then go to D4;
3. D5: q := q + 1; C := N2; N2 := CXq; go to if q <= N then D5
   else D4; D4: end; N3 := 2×N2; N4 := 2×N;
4. zhO: for i := 1 step1 until N do for k := 1 step 1 until N2 do
   b[i, k] := 0; i := 1; j := 0;
5. M0: k := 1; if a[1, i] = 0 then go to M2;
6. M: go to if a[1, i] != a[2, k] then H1 else H3;
7. H1: j := j + 1; b[1, j] := a[1, i]; b[2, j] := a[2, k];
8. H3: k := k + 1; go to if a[2, k] = 0 then M2 else M;
9. M2: i := i + 1; go to if i <= N1 then M0 else R;
10. R: j := 1; n := 1; i := 3; d := 1;
11. M8: for q := 1 step 1 until N do for q1 := 1 step1 until N3 do
    gamma[q, q1] := 0; ya := 0; B := 0;
12. M7: k1 := 0; k := 1; C := a[i, d]; if C = 0 then go to M9;
13. M5: go to p[j];
14. M3: b[i, k] := C; k1 := k1 + 1;
15. M4: ya := ya + 1; k := k + 1; go to if b[1, k] != 0 then M5 else M6;
16. D1: alpha := alpha + 1; w1 := w1 + 1; go to if b[i, alpha] = a[i, d] then D2
    else D1;
17. M6: gamma1 := k1 + ya − 1;
18. for v := 1 step1 until i do begin w1 := 0; alpha := 1; for w := ya
    step1 until gamma1 do begin;
19. go to if b[i, alpha] != a[i, d] then D1 else D2;
20. D2: w1 := w1 + 1; alpha := alpha + 1; gamma[v, w] := b[v, w1]; end; end;
    B := B + k1; ya := B;
21. M9: d := d + 1; if d <= N1 then go to M7; for u := 1 step1
    until N do for u1 := 1 step1 until N2 do b[u, u1] := 0; i1 := 1;
22. M10: if gamma[1, i1] = 0 then begin i1 := i1 + 1; go to M10 end else
    go to M11;
23. M11: for v := 1 step 1 until i do begin w1 := 0; for w := i1 step 1
    until gamma1 do1 begin if gamma[v, w] = 0 then go to D3 else w1 := w1 + 1;
    b[v, w1] := gamma[v, w]; D3: end; end;
24. n := n + 1; j := j + 1; i := i + 1; d := 1;
25. if n <= N then go to M8;
26. for t := 1 step 1 until N do r[t] := b[t, 1];
27. for i := 1 step 1 until N4 do c[i] := 0; yu := 1; y := 1; h := 1;
    z := 1;
28. zh: j := 1; k := 0;
29. A0: go to if h <= N then l[h] else zh1;
30. A2: go to if b[x, y] != r[z] then A1 else A8;
31. A1: c[j] := r[z]; delta[yu] := c[j]; yu := yu + 1; j := j + 1; c[j] :=
    = b[x, y]; delta[yu] := c[j]; yu := yu + 1;
32. A4: for x1 := 1 step 1 until N do begin if c[j] = r[x1] then
    go to A5 else k := k + 1 end;
33. A5: j := j + 1; c[j] := b[1 + k, y]; delta[yu] := c[j]; yu := yu + 1;
34. if c[1] = c[j] then begin j := j + 1; c[j] := 9; delta[yu] := c[j];
    yu := yu + 1; end else begin k := 0; go to A4 end;
35. A8: z := z + 1; h := h + 1; if z >= N + 1 then go to zh1; for i :=
    = 1 step 1 until yu do begin if r[z] = delta[i] then go to A8; end;
36. for n := 1 step 1 until N4 do c[n] := 0; goto zh;
37. zh1: p1041 (delta); y := y + 1; z := 1; h := 1; yu := 1; for i := 1 step
    1 until N4 do delta[i] := 0;
38. if b[1, y] != 0 then go to zh;
39. p 0042 (a, N, s); go to zh3; end

Fig. 1

Left branch:

• input \((a, N, s)\)
• array \(b = 0\)
• \(a[1,i] = 0\)
• no
• yes
• \(i := i + 1\)
• \(a[1,i] = a[2,k]\)
• no
• yes
• \(k := k + 1\)
• \(a[2,k] = 0\)
• yes
• array \(d = 0\)
• \(a[i,d] = 0\)
• yes
• no
• \(d := d + 1\)
• formation of array \(b\)

Right branch:

• formation of array \(b; d\)
• array \(b = 0\)
• \(b \Rightarrow d\)
• \(n \leq N\)
• yes
• no
• array \(c = 0\)
• formation of array \(c\)
• formation of array \(d\)
• print \((d)\)
• \(y := y + 1\), \(d[y,k] = 0\)
• yes
• no
• stop
• input \((a, N, s)\)

LITERATURE

1. L. A. Naumov, E. I. Tsimbalist. On one proof of the formula for the topological transmission of a graph. In the present collection.

2. R. S. Guter, P. T. Reznikovskii, S. M. Reznik. Programming and Computational Mathematics. Moscow, “Nauka,” 1971.

3. Reference material on the TA-1M translator (Signal-1, Signal-2). Moscow, 1969.