SU1280380A2 - Device for determining the maximum paths in graphs - Google Patents

Abstract

The invention relates to the field of computing, in particular, can be used in the study of the parameters of network graphs and is an improvement of the device for determining the maximum paths in the graphs according to the author. St. No. 862145. The aim of the invention is to expand the field of application of the device by making it possible to study graphs for the presence of loops and loops in them and to increase the accuracy of determining maximum paths. The goal is achieved by the fact that the device according to ed. St. No. 862145 additionally introduces the topology formation unit of the graph under study, the comparison unit, the address generation unit, the switch, the cycle allocation unit, and the firmware control unit. A preliminary study of the graphs for the presence of loops and cycles allows us to avoid calculating the maxi (the maximum paths in the cyclic graphs, which increases the reliability of the device and, consequently, increases the accuracy of determining the maximum paths in the graphs. 14 Fig. O 00 from 00

Description

The invention relates to the field of computer technology and can be used to study the parameters of network diagrams.

The purpose of the invention is to expand the scope of the device by making it possible to study graphs for the presence of cycles and loops in them and to improve the accuracy of determining the maximum paths.

FIG. 1 shows a functional diagram of a device for determining the maximum paths in graphs; in fig. 2 - the algorithm of the microprogram control unit; in Fig. Block diagram of the microprogram control unit; in fig. 4 is a functional diagram of the memory unit of the microprogram control unit; in fig. 5 is a functional diagram of the unit for generating transition signals of the microprogram control unit; in fig. 6 - functional diagram of the unit for generating control signals of the microprogram control unit; in fig. 7 is a functional diagram of a block for forming the topology of the investigated graph; in fig. 8 is a functional diagram of a cycle selection unit; in fig. 9 is a functional diagram of the first memory unit of the cycle allocator; in fig. 10 is a functional diagram of the second memory unit of the cycle allocator; in fig. 11 is a functional diagram of the third memory unit; in fig. 12 is a functional diagram of an address generating unit; Fig. 13 is a functional diagram of a switch; in fig. 14 is a functional block diagram of the comparison unit.

The device for determining the maximum paths in the graphs contains a matrix model 1 of the network, a group of elements / OR-NOT 2, a clock pulse generator 3, an element AND 4, a group of elements AND 5, a group of counters 6 of the arc weights, a group of triggers 7 control, a group of elements And.8, a group of recording counters 9, OR element 10, triggers 11 of the matrix model of the network, block 12 of microprogram control, switch 13, block 14 for forming the topology of the investigated graph, block 15 for forming the address, block 16 for comparison and block 17 for allocating cycles.

The microprogram control unit 12 constitutes a memory unit 18, a transition signal generation unit and a control signal generation unit 20.

The memory node 18 contains the first group of elements OR 21, the second group of elements OR 22, the first group of elements AND 23, the second group of elements AND 24, a group of triggers 25 of the main memory, an input for triggering triggers 26, a group of triggers 27 of an auxiliary memory, an alphabet decoder 28 states, trigger 29 control, element And 30 and generator 31 clock pulses.

Node 19 for generating transition signals consists of the first group of AND elements 32, a group of AND-OR elements 33, a group of OR elements 34, an encoder 35.

Unit 20 for generating control signals is made on OR elements 36.

Block 14 for forming the topology of the investigated graph is formed by a matrix of triggers 37 and a group of elements AND 38.

The block 17 allocating cycles contains the first 39, the second 40 and the third 41 memory nodes, as well as the first group of OR elements 42 and the second group of OR elements 43.

The first memory node 39 consists of an address decoder 44, a first group of AND 45 elements, a group of registers 46, a second group of AND 47 elements, an address counter 48 and a register 49.

The second memory node 40 is formed by the first group of elements AND 50, the second group of elements AND 51, a group of registers 52, address decoder 53, register 54 and counter 55 of the address.

The third memory node 41 contains the first group of elements AND 56, the second group of elements And 57, a group of registers 58, an address decoder 59, 45 a group of OR 60, register 61 and an address counter 62.

The block 15 for generating the address is made on a 63 row counter, a 64 column counter, a counter 65, a buffer register 66, a first group of OR 67 elements, a second group of OR 68 elements, a 69 column decoder, a 70 row decoder, and a third group of 55 ILT elements. 71, a feature trigger 72 and a control trigger 73.

The switch 13 is composed of η groups of η elements And 74 in each and a group of output elements And 75.

Comparison unit 16 contains an OR element 76, a group of AND elements 77 and a comparison trigger 78.

The matrix model of network 1 contains i, j triggers 11 by the number of rows and 5 columns (where i, j = 1, η; η is the number of vertices of the modeled graph), the outputs of which in the rows are connected to the inputs of the corresponding elements OR-NOT 2, the outputs of which connected to the control inputs of the corresponding elements AND 5 of the second group, and the inputs i, j of the triggers 11 in the columns are connected to the outputs of the corresponding counters 6 of the arc weights. The outputs of the elements And 5 15 of the second group are connected to the inputs of the corresponding counters 6 of the arc weights. The number of elements AND 8 of the first group, elements And 5 of the second group, registering counters 9, counters 20, 6 weights of arcs and triggers 7 control is determined by the number of columns of the matrix network model 1. The output of the microprogram control unit 12 is connected to the corresponding inputs 25 of the switch 13, the unit 14 forming the topology of the investigated graph, block 15 forming the address, block 16 of the comparison and block 17 of the selection of cycles. 50

The microprogram control unit 12 (Fig. 3) is used to generate a sequence of control unit signals distributed in time to control the operation from the units of the device. The program of operation of block 12 is shown in FIG. 2.

Node 18 memory (fig. 4) serves to set the alphabet of states of memory C, -C.,.

Node 19 for generating transition signals (Fig. 5) is designed to generate single signals necessary for the transition of the control unit to one of the states of the alphabet of memory states C _o -C _{3 <} .

The control signal generating unit 20 (FIG. 6) is used to generate a control sequence of single signals.

The switch 13 (Fig. 13) provides access to the output of each trigger (cell) 37 _Ί · unit 14 for forming the topology of the investigated graph.

The switch 15 consists of η groups of η elements AND 74 in each (where η is the number of vertices of the graph), each element And 7,4 represents three input elements And and elements J 75 _f 75 _hh according to the number of outputs of elements And 74 ". To access each trigger (cell) 37- ^ of block 14, you must specify the address of the row and column at the intersection of which this cell is located. Therefore, each element And 74 "contains two address and one information inputs. Elements And 75 are used for strobing the outputs of elements And 74. Gating is carried out by a single signal U _{? About} from the control input of the switch.

Block 14 forming the topology of the investigated graph (Fig. 7) records and stores information about the topology of the investigated graph. The block consists of a matrix of triggers (cells) 37 and a group of two-input elements AND 38. Triggers 37 are arc shapers and are set to a single state if there is an arc from the i-th vertex to the j-th vertex, or to a zero state if the vertices of the investigated graph are not connected by an arc. Elements And 38 -38. Serve for strobing the outputs of triggers 37. The strobing is carried out by a single signal U ₂₉ .

Block 15 of the address formation (Fig. 12) provides the generation of the values of the address of the rows ί, -ί ^ and the address · columns g ^ -grt in order to access the output of each trigger (cell) 37 of block 14 through the switch 13.

Comparison unit 16 (Fig. 14) compares the values of the flip-flops (cells) 37 of unit 14 with the value determined by the comparison flip-flop 78, which is set to one state by a single signal.

The cycle allocator 17 serves to store the values of the row counter 63 and the column counter 64 of the address generating unit 15.

The first memory node 39 is designed to store the values of the row counter 63 of the unit 15 registers 46 ₇ 46> j decoder 44 addresses and to access each register 46 ^ -46 ^. To one input of the elements And 45, the value from the output of the decoder address 44 is supplied (sample register by address), and to another single signal U _{27 of} block 12, which allows information to be written into one of the registers 46j-46d. The outputs of the elements And 45 are connected to the inputs that strobe the recording of information into the corresponding register 46 ₄ -64 _p (the address is selected). The value from the output of the decoder 44 of the address (sample of the register by address) is fed to one input of the elements And 47 -47 ^, and to the other - a single signal U _{49 of} block 12, which allows reading information from registers 46 _d -46 _p . The outputs of the AND elements 47 ^ ~ 47 _{n are} connected to the inputs that strobe reading information from the corresponding register 46 ^ -46 _n (whose address is selected). The address counter 48 is used to generate the positional code of the register address from the group of registers 46 _ή -46 _η , register 49 is used to store the current values of the address counter 48.

The second memory unit 40 provides storage of the values of the counter 64 of the columns of the address generating unit 15.

The third memory unit 41 serves to duplicate the second memory unit 40. The assignment of the elements of the memory nodes 40 and 41 is similar to the assignment of the elements of the memory node 39. I

The principle of operation of the proposed device is as follows.

A path in a graph can be defined as a sequence of vertices from a given vertex to the final one, connected by arcs. If any path in the graph contains several identical vertices, then there is a cycle in the graph.

The proposed device, in the absence of cycles in the investigated graphs, operates in two stages. - At the first stage, the graph is investigated for the presence of cycles, and if they are absent, the second stage begins, as a result of which a unit potential is generated, allowing the device to operate.

The graph is described by the adjacency matrix A representing its topology. The matrix has the dimension pdp (where η is the number of vertices in the graph). If there is an arc from the i-th vertex to the j-th vertex of the graph, then one is written at the intersection of the row with the number i (the i-th vertex) and the column with the number j (the j-th vertex of the graph). If there is no arc, zero is recorded.

If there are several ones in the line with the number ϊ (outgoing trains), then several paths go out from the i-th vertex.

If there are several ones in the j-th column (incoming arcs), then the j-th vertex contains several paths in the graph.

To have information about the connections of the i-th vertex, it is necessary to identify the outgoing arcs as a result of scanning the i-th row, and as a result of scanning the column with number j = i to reveal the incoming arcs. If there are no incoming arcs at the i-th vertex (the column with the number j = i is zero), then such a vertex in the paths of the graph cannot be a link of the cycle.

The search for cycles in graphs is performed in the following way.

and) . Sequentially, starting from the first vertex in the graph, by looking at the column of the adjacency matrix A with number j (j = 1, n, where η is the number of vertices in the graph), the connections included in the j-th vertex of the graph are determined. The numbers of these vertices are entered into the one-dimensional array S. As elements S (K1) of the array S are the values of the row numbers, at the intersection with which the unit (S (Kl) = i is written in column j, where K1 = 1 m _f is the number units in the j-th column of the adjacency matrix A).

The maximum value mg is equal to (the number of graph vertices). The technical implementation of the one-dimensional array S is the first memory node 39 of the cycle allocator 17. ...

b). If there are no incoming connections, consider the next vertex for the presence of incoming arcs, go to point (a) and consider the next column, if not, go to point (c).

in) . Check if there is a direct connection from the i-th vertex (i = j) to one of the vertices that are elements of the array S. If such a connection exists, then the element of the adjacency matrix (Afgjmj “1 is equal to one (A, _SI k <) 7 = 1 , where Ki = l, m _e .

d) If at least one equality of item (c) holds, then there is a cycle.

e). If none of the equality in item (c) is satisfied, it is necessary, as a result of viewing the line with the number i "j, to identify the arcs leaving the i-th vertex and fix the numbers of the vertices in the simultaneous array M3. The elements of the M3 array are the values of the numbers of the j columns, in which units are written at the intersection with the i-th row (M3 (K2) = j, K2 = 1, £ ₅ ), where ~ the number of arcs leaving the выход-th vertex. The maximum number is n-n (n is the number of vertices in the graph). The value of the elements of the M3 (K2) array must be rewritten into a similar one-dimensional array M4 (K3) = M3 (K2), where K3 = K2 = 1, £ ₂ .

The technical implementation of the arrays M3 and M4 are respectively the second 40 and the third 41 memory nodes of the cycle allocation unit 17.

e). For each element of the M3 array, it is necessary to check whether there is a direct connection from the vertices with the numbers M3 (K2) where K2 = 1.2 _G to one of the vertices S (KI), K1 = 1, t _g .

'AMZ (K2), S (KI) = 1.

If at least one equality holds, then there is a cycle.

g). If none of the equality of item (e) is fulfilled, it is necessary as a result of viewing the lines with numbers М4 (КЗ), where К3 = 1,1, identify the connections outgoing from these vertices and fix the numbers of the vertices in the one-dimensional array М3, and then after identifying all outgoing arcs' from the vertices with numbers equal to the values of the elements of the M4 array, rewrite the values of the elements of the M3 array into the M4 array. Then they go to point (f), if in point (g) they do not receive a zero array M3 (i.e., they are in the final vertex from which there are no outgoing arcs).

If the M3 array is nonzero, not all the vertices of the graph are scanned for the presence of incoming arcs and no cycles are found in points (c) and (e), go to point (a), otherwise a single signal is generated that the graph does not exist cycles enabling the device to operate. In this case, the second stage of work begins and the calculation of the maximum paths in the graphs.

The microprogram control unit 12 is made in the form of a finite Tzur automaton according to the Wilkes-Stringer model, the structure of which is determined by the structure of the operation algorithm of unit 12. Unit 12 is characterized by the alphabet of input signals P ₄ . -P ₂ (signs),

1280 380 β alphabet of output signals -Y, alphabet of memory states C _o -C ^, function of outputs R and function of transition to $.

c (t) = ί (c (t - 1), p (t)) is the transition function;

y (t) = Hc (t)) - output function. To set the alphabet of memory states from ₀ ~ ₃₁ , marks are included at the inputs of all I-th to 44-th operator and conditional vertices of the block operation algorithm '

12. Symbols Y · written in the operator vertices are the output signals of block 12.

The operation of block 12 is gated by a 3I clock. The clock pulses from the clock pulse generator 31 are supplied together with the alphabet signal of the input signals P ^ -P ^ if it exists. While the sync pulse is in effect, the state of the flip-flops 25 of the main memory does not change, although the state of the flip-flops 27 of the auxiliary memory may change. The state of the main memory flip-flops 25 changes when the sync pulse stops. This ensures the stability of the unit 12, since while the sync pulse is active, the triggers of the main memory 25 do not go into a new state. The alphabet of memory states ^c 0 ~ ^c j <is encoded by a binary code taken from the outputs of triggers 25 of the main memory. The inputs of the auxiliary memory flip-flops 27 are connected to the outputs of the encoder 35, at the outputs of which a binary code is formed, which sets the auxiliary memory flip-flops 27 to a new state of the alphabet of memory states with -c .... The pulses of the generator 31 of such off-the-shelf pulses are fed to the control trigger 29 through the AND element 30, the outputs of which are supplied with information that the unit 12 is in the initial state c0 (set before the start of operation by applying a signal to the input Set 0). To initiate the operation of the control unit, it is necessary to supply a single trigger pulse to the Start input of the memory unit 18 of the block 12. The decoder 28 of the alphabet of memory states converts the positional code at the output of the triggers 25 of the main memory into a unitary code.

Output control signals Y · alphabet of output signals are generated depending on the state (280380 of the alphabet of memory states from ₀ ~ c ^, into which the control unit 12 has passed. If the same signal is generated in different states of the alphabet of states of memory from ₀ ~ c ^ block 12, then the corresponding outputs of the decoder 28 alphabet of memory states must be connected by an OR circuit.

For example, according to the operation algorithm of block 12, a single signal Y _{3 is} generated when block 12 goes into a state with _e or c _{<7 of the} alphabet of memory states. Therefore, the corresponding outputs of the decoder 28 of the alphabet of memory states (with _o and c) are combined with the OR element 36.

Block 12 goes into a new state depending on the state at the previous moment and on the signals of the alphabet of the input signals (P-P ^). The law of transition of block 12 to a new state of the alphabet of memory states is determined by the operation algorithm of the control unit (Fig. 2). For example, to transition to the state C _{g of the} alphabet of memory states, it is necessary to be in the state of the alphabet of memory states. Such a transition is carried out from the state C ₄ at the next cycle of operation of the microprogram control unit 12 in the presence of the alphabet signal of the input signals P. To fulfill the clock condition, it is necessary to combine the output of the decoder 28 of the alphabet of memory states and the input P _{g with the} element AND 32. The signals of the input alphabet are fed to the first and second information inputs of block 12.

Yout element And 32 is designated by the letter by. By connecting the output of the element And 32 with the fifth input of the encoder 35, the positional code 00101 ^ = 5v _{J01 is} obtained at the output of the encoder 35

Comparison unit 16 operates as follows.

Suppose that the output of the OR element 76 of the comparison unit 16 is zero, i.e. the value of the trigger (cell) 37 ^ 1 of block 14 is zero, at the output of the NAND gate 77 there is a value of one '. If the output of the comparison flip-flop 78 is set to one, the output of the NAND gate 77 is zero '. At the output of the NAND gate, there is a value equal to one, therefore, at the output of the NAND gate 72, a value equal to zero appears. P _fi is equal to zero. Suppose that the output of the OR element 20 of the comparison unit 16 has a unit value, i.e. the value of the trigger (cell) 37 of block 14 is equal to one. If a unit value is present at the output of the NAND gate 77, the sign P _g is equal to one.

The proposed device operates in two stages.

Preliminarily, a single signal is sent to the input Set 0 of the memory node 18 of the microprogram control unit 12, setting the auxiliary memory triggers 27 and the main memory triggers 25 to the zero state, setting the block 12 to the initial state of the alphabet of memory states C _o . The same .. signal enters the block 15 of the formation of the address and sets the control flip-flop 73 to zero, setting the control output of the block 15 to zero potential.

At the first stage of the device operation, information about the topology of the investigated graph, displayed by the adjacency matrix A, is entered into block 14 and into the matrix model of network 1. The counts of the weights of arcs 6 contain the numbers of pulses that complement the weights of the vertices to the full capacity of the counters of information that block 12 is located in the initial state (the unit potential at the output C _{o of the} decoder 28 of the alphabet of memory states) is fed to the input C _{o of} the memory node 18 of block 12. With the appearance of a single trigger signal at the Start input of the memory node 18 of the I2 block, the operation of the device begins. The operation of the block 12 is synchronized by the generator 31 of clock pulses, the clock pulses of which are determined by the maximum possible response time of the circuit elements of the device and through the element AND 30 in the presence of single potentials at the inputs Start and C are fed to the trigger 29 of the control, controlling the operation of the microprogram control unit 12. We will trace the operation of the device according to the algorithm of the device.

I. In the first cycle of the clock 31, block 12 moves to state C * alphabet memory states, and at the same time produces a sequence of unit sig11 1,280,380 catch Y _d, and Y ^ _((operator 1). A signal Vg is passed to block 15 and sets the counter 65 to the zero state.

The signal Y ₂₉ enters the comparison unit 16 and sets the comparison flip-flop 78 to a single state.

Signal Ud ₄ enters block 17. and zeroes the registers 46 of the memory node 39, registers 58 of the memory node 40, registers 50 ₄ -50 _{Ii of} the memory node 41.

2. The microprogram control unit 12 goes into the state C ^ of the alphabet of memory states, and at the same time a sequence of single signals U45, ^U 38 ' ^U <o' VW is generated (operator 2) ..

The signal Y _<0 enters block 15 at counter 65 and increases its value by one (CT ^ +1).

The signal Y, _{and is} fed to the block 15 to the trigger 72 of the sign, setting the sign Pj. to the zero state.

Signals Y _<? , Udd, U _go arrive: block 17 and reset the counter 62 of the address of the memory node 41 (CT ^ g = 0), the counter 55 of the address of the node, 40 of the memory (ST ₅₅ = 0) and the counter 48 of the address of the node 39 of the memory (CT _4g = ABOUT).

Signal Y enters block 15, resetting the value of the 63 line counter (CT _2g = 0).

3. Block 12 goes into state Sd ', and at the same time a sequence of single signals U ₂ ,. U _I , U ₈ (operator 3) is generated.

The signal U ₂ enters block 15 at the 63 line counter, 'increasing its value by one (CT _{? E} = CTj _a +1)

Y _<4 enters block 15, counter output 65.

Signal gating

U ₈ Enters block 15, the input of the counter is 64 columns.

Signal gating

With the simultaneous generation of signals Y., Y, the counter 64 of the columns β η is assigned the value of the counter 65 of block 15 (CT ^ = CT _J0 ).

4. On the next cycle, block 12 goes into the state Cd of the alphabet of memory states, the signals Ud, Y ₇ , Y ^, Y, _{0 are generated} (operator 4)

Signal gating

Gating signal. ° and at the same time generate a sequence of unity

7c '

Ud enters the output of the counter Y enters the output of the counter block 15, lines. 15 block, 64 post 55 block 17 gating I7 gating block

Signals Y _<9 , Y ₂₀ enter block 15, strobing the outputs of decoders 70 and 69, respectively.

The signal Y ₃ 0 goes to the switch 13, strobing its output.

The signal Y, _d enters block 14, strobing the outputs of the flip-flops 37.

Thus, with the simultaneous generation of signals in the register from the group of registers 46 of the first memory unit 39 of the unit 17, the value of the row counter 63 of the unit 15 is recorded according to the value of the address of the first memory unit 39 (address counter 48).

8 * On the next clock cycle, block 12 goes into state C _g , and at the same time single signals are generated (operator 8).

The signal U _2E enters the first memory node 39, the output of the address counter 42.

The signal Y _{2 <} enters the first memory node 39, register input 49.

With the simultaneous generation of signals, the value of the address counter 48 (RG ₄₃ ^{= st} ; ₂ ) is written into register 49 of block 17 of the first memory node 39

9. At the next, block 12 also enters the next state of the alphabet of memory states, depending on the signal value of the alphabet of the input signals.

If the feature generated in block 15 (the value of the row counter 63 is equal to n) is zero, go to step 3, if not, go to step 10.

10. Block 12 (operator 10) goes into the next state depending on the signal of the alphabet of the input signals.

If the sign P _? generated in block 17 (the value of the address counter 48 45 is equal to zero) is equal to zero, go to step 2, in another case to step 11.

In paragraphs 2-10, the column of the adjacency matrix A (technical implementation of the adjacency matrix block 14) with a number determined by counter 65 of block 15- is scanned, and links are identified that enter the vertex with a number determined by counter 65. The numbers of these vertices are entered into a one-dimensional array S (the technical implementation of the array S is the first memory node 39 of block 17). To ensure that each register 46 can be accessed in order to store the vertex numbers of the first memory node 39, an address counter 48, an address decoder 74 and a register 49 for operatively storing the values of the address counter 48 are introduced into it.

Counter 48 address is a technical implementation of the variable K1.

When the entire column has been scanned ξ, = 1 (the value of the row counter 63 of block 15 is equal to n), in registers 40 ₄ -40 ^ of the first node 39 of the memory of block 17 there is information about all the connections included in the vertex with the number - determined by the counter 65 of the block 15, and register 49 contains a value characterizing the number of elements in the array S.

... The microprogram control unit 12 goes into the following state U _and , U ₄₃ and at the same time a sequence of single signals U _n , U ₍₃ (operator 11) is generated.

The signal Y _<h enters block 15, strobing the output of the counter 65.

The signal U. enters block 15, strobing the input of the buffer register 6o.

With the simultaneous generation of these signals, the value of the counter 65 of block 15 is written to the buffer register 66.

12. Block 12 goes over to state C of the alphabet of memory states, and at the same time a sequence of single signals Y ^ is generated (operator 12).

The signal Yj enters block 15, strobing the input of the line counter 63.

The signal U _4D enters block 15, strobing the output of the buffer register 66.

With the simultaneous generation of signals, the value of the buffer register 66 is written into the row counter 63 of the address forming unit 15.

13. On the next cycle, the microprogram control unit 12 goes into the state C _{<0 of the} alphabet of memory states, and at the same time a sequence of single signals y _j3 , y _2g , Y _<5 , Y & is generated (operator 13).

The signal Y _2r enters the cycle allocation unit 17 to the first memory node 39, strobing the output of the address counter 48.

Signal Y ₂₆ enters block 17 at the first memory node 39, strobing the output of the address decoder 74.

The signal enters the block 15 of the formation of the address, strobing the input of the counter 64 columns. The signal Y _<9 strobes the output of the decoder 70 lines.

Thus, with the simultaneous generation of signals, the value of the register 46 of the first memory node 39 of the block 17 (according to the address generated by the address counter 48) is sent to the block 15 to the column counter 64.

14. Block 12 goes into state C.0 of the alphabet of memory states and at the same time a sequence of single signals ^U 4 » ^U 19> ^U 2C> U _{zo is} generated (operator 14).

The operator's action is similar to that of the operator in point 4 (the value of the trigger (cell) 37 of the topology formation unit 14 (according to the address) is sent to the comparison unit 16).

15. On the next clock cycle (operator 15), block 12 goes into the next state of the alphabet of memory states, depending on the value of the signal of the alphabet of input signals.

If the sign P ^ (the sign of the operation of the comparison unit for equality, i.e. the value of the cell 23yj of the block 14 is equal to one) is equal to zero, go to point 16, otherwise - to point 30.

16. Block I2 goes into the state of the alphabet of memory states (operator 16) and at the same time a single signal is generated (operator 16), which is fed to block 17 to the address counter 48 of the first memory node 39 and decrements the value of the address counter 48 by one.

17. On the next one there is also a transition on a complex condition.

If the sign P _? (generated in the first node 39 of the memory of the block I7 and characterizes the zero state of the counter of the address 48 of the block) is equal to zero, go to step 14, if not to item I8.

18. If the sign P _g (generated in the second memory node 40 of the block I7 and characterizes the zero value of the counter of the address 55 of the block) is equal to zero, go to step 43, in another case - to step 19.

19. If the sign (generated in block 15 by trigger 72; the sign P ₅ = 0 can be characterized as a sign of the start of work, that is, viewing a new vertex for the presence of incoming arcs) is equal to zero, go to step 22, if not, go to step 20.

In points 11-18, ¹ next action takes place.

In the buffer register 66 of block 15 5, either the value of the counter 65 is written, which characterizes the number of the next vertex examined for the presence of input arcs, or the value of the M3 array (technical implementation of the M3 - Yu array, the second node 40 of the memory of block 17) and is checked according to item 15, whether direct connection from the vertex with the number, characterized by the value of the buffer, register 66 with one of the 15 vertices of the array S (the first memory node 39) of block 17. Let's denote the buffer register 66 conditionally by the letter m.

The next check occurs.

The value of the element of the adjacency matrix20 is one.

According to clause 12, the value of the buffer register 66 is written into the row counter 63 of block 15, according to clause 13, the next value of the element of the array S 35 (the content of one of the registers 46 of the first node 39 of the memory of block 17) according to the value of the counter 48 of the address of block 17 (K1) is written into the counter 64 column block 15.50

According to paragraph 14, according to the values of the counters of rows 63 and columns 64 of block 15, the value of the trigger (cells) 32 of block 14 is selected, which is supplied to the comparison block 16. 35

If such a relationship exists (sign P = 1), therefore, there is a cycle (point 15), if not, decrease the value of the address counter 48 by one and repeat the checks until 40 until they have scanned the entire array S. The sign of this is the value equal to zero counter 48 of the address of the first node 39 of the memory of block 17 (P _? = 1). ... 45

Check P _t of feature occurs in step 17.

If the elements of the M3 array (second memory node 40 of block 17) are written to the buffer register 66, then the criterion for enumerating all the elements of the M3 array is the equality to zero of the value of the address counter 55 of the second memory node 40. This characterizes feature 55 R ₈ (paragraph 18).

20. Block 12 goes into the state C ^ _{3 of the} alphabet of memory states, and at the same time is generated sequentially.

the sequence of single signals 5 ^, ^ 2 '(operator 20).

The Ude signal enters block 17 at the third memory node 41, strobing the output of the address counter 62.

The signal enters block 17 at the third memory node 41, strobing the output of the address decoder 59.

The signal enters block 17 on the third memory node 41, allowing reading information from registers 58m

The signal enters block 15, strobing the input of the buffer register 66.

Thus, with the simultaneous generation of a sequence of signals, the value of the register 58 of the third memory node 41 of the block 17 according to the address generated by the address counter 62 is sent to the buffer register 66 of the block 15.

21. On the next cycle, the control unit goes into the state C ^ of the alphabet of memory states. At the same time, a signal Y is generated (operator 21), which enters block 17 at the third memory node 41 and decreases the value of the counter 49 of address 49 by one.

22. Block 12 goes into the state of the alphabet of memory states, and at the same time a single signal U ₅ (operator 22) is generated, which is fed to block 15 and reset the counter 64 of the columns.

23. Block 12 goes into the state C ,,, of the alphabet of memory states, and at the same time a single signal Y _£ (operator 23) is generated, entering block 15 and increasing the value of the counter of columns 64 of block 15 by one.

24. Block 12 goes into state C., alphabet of memory states, and one

7, a sequence of single signals Y is simultaneously generated (operator 24).

The signal Y * enters block 15, strobing the input of the counter 63 lines.

The signal Y ^ enters block * 15, strobing the output of the buffer register 66 of the block.

Thus, the value of the buffer register 66 of block 15 is written to the line counter 63.

25. Block 12 goes into the state

C ^ _{6 of the} alphabet of memory states and at the same time a sequence of single signals V ^, V ₇ , ήϊβ ' ^V 1 ₉ » ^V 20' ^V zo (operator '25) is generated. The action of operator 25 is similar to the action of operator 14 (point 14) (the value of the trigger (cell) 37 of block 14 according to the address) is sent to the comparison block 16.

26. Block 12 goes to the next state.

If the sign (is generated in the block 16 comparison and is a curve-

280380 18 of the second memory node 40 of the block 17 is written to the register 54 of the block.

)

Block 12 goes into the state ,, 5 while the sequences of single signals are not generated.

Block 12 goes to the next state of the alphabet of memory states depending on the signals of the input alphabet.

by the time the comparison unit is triggered for equality) is equal to one (the value of the trigger (cell) 37 of block 14 is equal to one), go to paragraph 27, in another case - to paragraph 30.

27. 'Block 12 goes into the state, and at the same time a single signal Y ^ d (operator 27) is generated, which enters block 17 on the second memory node 40 and increases by one the value of the counter of the address 55 of the block.

28. Block 12 goes into state C, _e , and at the same time a sequence of single signals Y „, ν _3ί , Y ₃ 5, Y-, -

The signal U _{41 is} fed to the second memory node 40 of the unit 17, strobing the output of the address counter 55.

The signal U _{35 is} fed to the second memory node 40 of the unit 17 by strobing the output of the address decoder 53.

The signal goes to the second memory node 40, allowing information to be written to registers 52.

Signal U ₇ enters block 15, strobing the output of the counter 64 columns.

Thus, with the simultaneous generation of such a sequence in the register from the group of registers 52 of the second memory node 40 of the block 17 according to the address CT 55 (the value of the address counter 55 serves as the address of the selected register) the value of the column counter 64 of the block 15 is written.

29. Block 12 goes into state C ^ j, and at the same time a sequence of single signals U ₄₁ , U is generated.

The signal goes to the second memory node 40 of block 17, strobing the output of the address counter 55.

The signal Y ^ _£ arrives at the second memory node 40 of block 17, strobing the input of register 54.

With the simultaneous generation of signals, the value of the counter 55 addresses

If the sign P? (generated in block 15 and says that the value 'of the column counter 64 of block 15 is equal to n) is equal to zero, go to 15, paragraph 23, if not, go to paragraph 31.

31. If the sign Pg is generated in block 15 (trigger 72) and is characterized as a sign of the start of work, i.e. viewing the new vertex for the presence of incoming arcs) is equal to zero, go to step 32, if not, go to step 33.

32. Block 12 goes into state C ₂₂ , and at the same time a single signal is generated, supplied to block 15 by flip-flop 72 and setting the flip-flop 77 to the single state P = 1, go to step 34.

33. If the sign Pj (generated in block 17 in the third memory node 41 and informs that the value of the counter of address 62 is equal to zero) is zero, go to step 20, in another case - to step 34.

34. If the sign (generated in the second memory node 40 of block 17 and informs that the value of the address counter 55 is equal to zero) is zero, go to step 35, if not, go to step 36.

35. The block 12 moves to state C _24, and simultaneously produces a sequence of unit signa45 ^fishing 7o> V

The signal y _{j7 is} fed to the second memory node 40 of block 17, strobing the output of register 54.

The signal Y _{? About} arrives at the third node ed 41 of the memory of block 17, strobing the input of register 61.

With the simultaneous generation of signals y _j? , Y ₅ 0 in register 61 of block 17 (the third memory node is written the value of register 54 (second memory node 40).

37. Block 12 goes into state C ₂ j of the alphabet of states, and at the same time a sequence of single signals is generated, Y ^ (operator 37).

The Ud-r signal enters block 17 at the third memory node 41, strobing the input of the address counter 62.

The signal Y ^ (enters block 17 at the third node 4) of the memory, strobing the output of register 61.

39. The block 12 moves to state C _2g, and simultaneously generated single sequence ^{of signals} ~ 48 '52'^'Y44' 35 ^'Wu (operator 39 Torr).

The signal y ^ j enters block 17 at the third node 41 of memory 41, strobing the output of the address counter 62.

Signal ^U 52 strobes the output of the address decoder of the third memory node 41.

Signal U43 allows writing information to registers 58 of block 17 (third memory node 41)

The signal ^Y 4 <enters block 17 at the second memory node 40, strobing the output of the address counter 55.

The signal enters block 17 at the second memory node 40, strobing the output of the address decoder 53.

Signal ^Y 34 enters block 17 on the second memory node 40 and allows reading information from registers 52.

With the simultaneous generation of this sequence in one of the registers 58 of the third memory node 41 of the block 17 according to the counter address 61 - ·. address (the value of the counter 61 serves as the address of the selectable register), the value of one register 52 is written according to the counter address of address 55 (the value of the counter 55 is the address of the selectable register).

40. Block 12 goes into the state of the alphabet of states, and at the same time a sequence of single signals U., ^U 49 'is generated

Signal ^ 2 arrives at the second memory node 40 of block 17, decreasing the value of the counter of address 55 by one.

The signal, U _{49 is} fed to the third memory node 41 of the unit 17 and decreases the value of the address counter 62 by one.

41. Block 12 goes into the following state depending on the signal of the input alphabet.

"

If the sign P _d (generated in the second memory node 40 of block 17 and informs that the value of the counter of address 55 is zero) is zero, go to step 39, if not, go to step 42.

42. The control automaton goes into the state С _2е , and at the same time a sequence of single signals is generated,, Y ^.

The Yjy signal enters block 17 at the second memory node 40, strobing the output of register 72.

The signal Y _<0 enters block 17 at the second memory node 40, strobing the input of the address counter 55.

Signal Y ,. enters block 17 at the third memory node 41, strobing the output of register 61.

The signal Y * ₇ enters block 17 at the third memory node 41, strobing the input of the address counter 62.

With the simultaneous generation of such a sequence of signals, the value of register 54 is written to the counter of address 55 of the second memory node 40 of block 17, and the value of register 61 is written to the counter 62 of the address of the third node 41 of the memory of block 17 ..

43. Block 12 goes into state C ^ ₃ , and at the same time a sequence of single signals Y, Y, Y, Y is generated (operator

I

The signal Y ,, enters block 17 at the second memory node 40, strobing the output of the address counter 55.

The signal enters block 17 at the second memory node 40, strobing the output of the address decoder 53.

The signal Y ^ enters block 17 at the second memory node 40, allowing information to be read from registers 52.

Signal ^ 5 enters block 15, strobing the input of buffer register 66.

Thus, with the simultaneous generation of this sequence of signals, the value of one of the registers 52 of the second memory unit 40 of the unit 17 is written into the buffer register 66 of the unit 15 according to the address of the selected register, which is taken as the value of the address counter 55.

44. Block 12 goes into state C ^ ₄ , and at the same time a sequence of single signals VVV '/ 22' K is generated;

The signal decreases the value of the address counter 55 in the second memory node 40 of block 17 by one.

The signal enters block 17 at the first memory node 39, and strobing the input of the address counter 48.

The signal enters block 17 to the first memory node 39, and strobing the output of register 49.

Thus, with the simultaneous generation of signals, the value of the address counter 55 of the second memory node 40 of block 17 decreases by one and the value of register 49 in block 17 is written to the address counter 48; go to point 12.

36. The control automaton goes into the following state.

If the sign Pj (generated in block 15 and informs that the value of the counter 65 is equal to n) is zero, go to step 2, if not - to step 38.

38. Block 12 goes into the state; Cj _ft and at the same time a single signal Y _<? entering block 15 and setting the control trigger 73 to a single state.

The block 12 is transferred to the next state and the operation of the control unit ends (the cycle detection process is over). This completes the first stage of the device. If there are no cycles in the graph, then as a result of the first stage of operation of the device, the control trigger is set to a single state and the single potential at the output of the control trigger 73 serves as a trigger signal at the input of the AND element 4. The second stage of operation of the device begins, in which, in the case of the absence of cycles, the maximum paths are calculated using a known device. If the cycles exist and the control flip-flop 73 of the unit 15 is not set to a single state and the second stage of operation is absent, i.e. in cyclic graphs, maximum paths are not computed.

In paragraphs 19-30, the following happens.

If no cycles were found before point 19 (point 15), it is necessary to identify outgoing links (arcs) from the i-th vertex.

If the P _$ sign (item 19) is equal to zero, then the next vertex is considered for the presence of incoming arcs (the beginning of a new stage of information processing). In this case, the M4 array has not yet been formed (the technical implementation of the M4 array is the third node U 41 of the memory of block 17) and the value of the counter 65 of block 15 is taken as the number (w) of the i-th vertex. If the M4 array is formed (sign P = 1), so it is necessary to view all the values of the M4 array as number 15 of the i-th vertex. To do this, in paragraph 20, the next value of the element of the M4 array (one of the registers 58) according to the counter address of address 49 (SC) is written20 into the buffer register 66 (t) of block 15. Then the viewing of the row of the adjacency matrix begins (technical implementation - block 14 of topology formation of the investigated graph).

in paragraph 21, the value of the counter of address 62 (short circuit) is reduced by one.

It is necessary to view the lines with the number ta (the value of m 30 is the value of register 65 of block 15 or the value of an element of the array M4 (third node 41 of the memory of block 17).

For this, counter 64 of columns 3 $ of block 15 is reset to zero in paragraph 22, and in paragraph 23 the value of counter 64 of columns of block 15 is increased.

In paragraphs 24-26, the value of the trigger (cells) 40 of the 37-block 14 is sampled, and in the comparison block 16, the value of the cell 37-fj is compared with the single value of the trigger 78 of the comparison of the block 16.

If the value of the trigger (cell) 45 37, -j of block 14 is equal to one (found the next arc) going out of the vertex), the next element of the M3 array is filled. To do this, in step 27, a new value of the address counter 55 (K2) is set, according to this value of address 55, the value of the counter 64 columns of block 15 (item 28) is written into a single register 52, and in step 29 the value 55 of the counter 55 of the address of the second memory node 40 block 17 is written to block register 54. If the entire line is scanned (sign P ₂ ) is equal to one operator 30), register 54 of the second memory block contains the number of links emerging from the i-th vertex (the number of elements of the array M3).

The operation of viewing the lines continues depending on the number of elements of the M4 array (the elements of the M4 array serve as line numbering) or one line with a number equal to the value RG ^ _{0 of} block 15 is scanned, if the sign P ₅ is equal to zero. If all elements of the array are scanned (sign = 0 ), i.e. the SC value is zero (address counter 62), which means that a new array M3 has been formed (second memory node 40 of block 17). If the newly formed array M3 is zero, the links identified leaving the i-th vertex come to the final one, and, therefore, if not all vertices in the graph are examined for the presence of incoming arcs (sign Pd = O (item 36), go to step 2 and the process If the M3 array is nonzero, its values are rewritten into the M4 array (second memory node 40 of block 17) in steps 35-41 and after the necessary auxiliary operations 42-44 go to step 12.

Claims (4)

14) 11 The invention relates to the field of computer technology and can be used to study the parameters of network graphics.  The purpose of the invention is to expand the field of application of the device by providing the possibility of examining the graphs for the presence of cycles and loops in them and improving the accuracy of determining the maximum paths.  FIG.  1 shows a functional diagram of the device for determining the maximum paths in the graphs; in fig.  2 - algorithm of operation of the firmware control unit; in fig. The structural circuit diagram of the firmware is a lot of control; in fig.  4 is a functional diagram of the memory assembly of the firmware control unit; in fig.  5 is a functional diagram of a node for forming a transition signal of a firmware control unit; in fig.  6 is a functional diagram of a control signal generation unit of a microprogram control unit; in fig.  7 is a functional block diagram of the formation of the topology of the graph under study; in fig.  8 is a functional block allocation circuit; in fig.  9 is a functional diagram of the first memory node of the cycle allocation unit; in fig.  10 is a functional diagram of a second memory node of a cycle allocation unit; in fig.  11 is a functional diagram of the third memory node in FIG.  12 is a functional diagram of an address generation unit; in fig. 13 is a functional switch circuit; in fig.  14 is a functional block diagram of the comparison.  The device for determining maximum paths in the graphs contains a matrix model of 1 network, a group of elements OR-NOT 2, a generator of 3 clocks, an element of AND 4, a group of elements of AND 5, a group of counters 6 arc weights, a group of trigger trigger 7 controls, a group of elements of I. 8, a group of registering counters 9, an element of RSHI 10, triggers 11 of the matrix model of the network, microprogram control unit 12, switch 13, block 14 for shaping the topology of the graph under study, block 15 for creating the address, block 16 for comparing and block 17 for segmenting loops.  The firmware control unit 12 constitutes a memory unit 18, a transition signal generation unit 0 19 and a control signal generation unit 20.  Memory node 18 contains the first group of elements OR 21, the second group of elements OR 22, the first group of elements 23, the second group of elements AND 24, the group of triggers 25 of the main memory, the trigger trigger input 26, the group of triggers 27 auxiliary memory, the decoder 28 of the alphabet states, control trigger 29, element 30 and clock generator 31.  The node 19 of the formation of the signal transition consists of the first group of elements AND 32, the group of elements AND-OR 33, the group of elements OR 34, the encoder 35.  The control signal generation unit 20 is configured on OR 36 elements.  Block 14 of forming the topology of the graph under study form a matrix of triggers 37 and a group of elements 38.  Block 17 throughout the cycle contains the first 39, second 40 and third 41 memory nodes, as well as the first group of elements OR 42 and the second group of elements SH 43.  The first memory node 39 consists of the address decoder 44, the first group of elements And 45, the group of registers 46, the second group of elements And 47, the counter 48 of the address and the register 49.  The second memory node 40 consists of the first group of elements And 50, the second group of elements And 51, the group of registers 52, the decoder 53 of the address, the register 54 and the counter 55 of the address.  The third memory node 41 contains the first group of elements AND 56, the second group of elements AND 57, the group of registers 58, the decoder 59 of the address, the group of elements OR 60, the register 61 and the counter 62 of the address.  The address generation unit 15 is executed on a counter 63 lines, a counter 64 columns, a counter 65, a buffer register 66, a first group of elements OR 67, a second group of elements OR 68, a decoder 69 columns, a decoder 70 lines, a third group 55 elements LII 71, trigger 72 sign and trigger 73 control, the switch 13 consists of n groups of n elements And 74 in each and a group of output elements And 75.  Comparison unit 16 contains an OR element 76, an AND 77 group of elements and a comparison trigger 78.  The matrix model of network 1 contains i, j triggers 1I by the number of rows and columns (where i, jl, n; n is the number of vertices of the simulated graph), the outputs of which in the lines are connected to the inputs of the corresponding elements OR NOT 2, the outputs of which are connected to the control The inputs of the corresponding elements And 5 of the second group, and the inputs i, j of three generators 11 in the columns are connected to the outputs of the corresponding counters of 6 arc weights.  The outputs of the elements And 5 of the second group are connected to the inputs of the corresponding | 1x counters 6 arc weights.  The number of elements AND 8 of the first group, elements AND 5 of the second group of register counters 9, counters 6 arc weights and control triggers 7 is determined by the number of columns of the matrix model of network 1.  The output of the firmware control unit 12 is connected to the corresponding inputs of the switch I3, the topology shaping unit I4 of the studied graph, the address shaping unit 15, the comparison unit 16 and the cycle extracting unit 17.  Microprogram control unit 12 (FIG.  3) serves to generate a sequence of control single signals distributed in time to control the operation of the blocks of the device.  The program of operation of block 12 is shown in FIG.  2   Memory node 18 (FIG.  4) serves to set the alphabet of the states of the memory C –C j.  The transition signal generation unit 19 (FIG.  5) is designed to generate single signals necessary for the control unit to go to one of the states of the alphabet of memory states C, -C.  The control signal generation unit 20 (FIG.  6) i is used to generate a sequence of single signal control.  Switch 13 (FIG.  13) provides access to the output of each trigger (cell) of the topology formation unit 14 of the graph under study. Switch 15 consists of n groups of n elements And 74 in each (where n is the number of graph vertices), each element 7.4 represents three 12 04 input element And and elements And 75, according to the number of outputs of elements And 74.  .  To access each trigger (cell) of block 14, it is necessary to specify the address of the row and column at the intersection of which the given cell is located.  Therefore, each element And 74 contains two address and one information inputs.  Elements And 75 serve for gating the outputs of the elements and 74.  Gating is performed by a single signal Yjg from the control input of the switch. The topology formation unit 14 of the graph under study (FIG.  7) records and stores information about the topology of the graph under study.  The block consists of a matrix of triggers (cells) 37 and a group of two-input elements And 38.  Triggers 37 are an arc former and are set to a single state if there is an arc from the i-th vertex to the j-th vertex, or to the zero state if the vertices of the graph under study are not connected by an arc.  Items 38 to 38 serve to gate the trigger outputs 37.  The gating is performed by a single signal Yj.  The address generation unit 15 (FIG.  12) provides the generation of values of the address of the rows and address columns g; (- gri in order to access the output of each trigger (cell) 37 of block 14 through the switch 13.  Comparison unit 16 (FIG.  14) compares the values of the triggers (cells) 37 of the block 14 with the value determined by the comparison trigger 78, which is set to a single state by a single signal.  The loop extracting unit 17 serves to store the values of the row counter 63 and the column counter 64 of the address generation unit 15.  The first memory node 39 is designed to store the values of the row counter 63 of the block 15, the registers 46, the address decoder 44 and to access each register. To one input of the elements 45 there is fed a value from the output of the address decoder 44 (sample of the address register), and another single signal At block 12, allowing the recording of information in one of the registers 46f-46.  The outputs of the terminals and 45 are connected to the inputs gating the recording of information in the corresponding register (select the address quickly.  One input of the And 47 7 elements is supplied with the value from the output of the address decoder 44 (sample of the register by the address), and the other - a single signal of the block 12 allowing reading information from the registers 46d-46 |.  The outputs of the elements And 47 are connected to the inputs that block the reading of information from the corresponding register 46 (n (the address of which is chosen).  The address 48 counter is used to generate the position address code of the register from the register group, the register 49 to store the current values of the address counter 48.  The second memory node 40 stores the values of the counter 64 columns of the address generation unit 15.  The third memory node 41 serves to duplicate the second memory node 40. The assignment of the elements of the memory nodes 40 and 41 is similar to the assignment of the elements of the memory node 39.  I The principle of operation of the proposed device is as follows.  A path in a graph can be defined as a sequence of vertices from a given vertex to a final vertex connected by arcs.  If a path in the graph contains several identical vertices, then there is a cycle in the graph.  The proposed device in the absence of cycles in the studied graph works in two stages. “At the first stage, the graph is examined for the presence of cycles, and in the case of their absence, the second stage begins, as a result of which a single potential is developed that permits operation of the device.  The graph is described by the adjacency matrix A mapping its topology.  The matrix has the dimension pdp (where n is the number of vertices in the graph).  If there is an arc from the i-th vertex to the j-th vertex of the graph, then at the intersection of row i (i-vertex) and column j (j-vertex r) there is one record.  If there is no arc, zero is written.  If there are several units in the row with number i (outgoing 806 trains), then there are several paths from the i-th vertex.  If there are several ones in the column with the number j (incoming arcs), then the j-th vertex includes several paths in the graph.  In order to have information about the connection of the i-th vertex, it is necessary as a result of viewing the i-th row to extract the output of the arc and, as a result of viewing the column with the number, to enter the incoming arcs.  If the i-th vertex has no incoming arcs (the column with the number is zero), then such a vertex in the paths of the graph cannot be a link of a cycle.  The search for cycles in graphs is performed as follows.  but).  Sequentially, starting from the first vertex in the graph by looking at the column of the adjacency matrix A with the number j (j l, n, where n is the number of vertices of the graph), the links entering the jth vertex are determined.  The numbers of these vertices are inserted into a one-dimensional array S.  The elements S (K1) of the array S are the values of the row numbers, at the intersection with which in the column with the number j the unit is written (S (Kl) i, where, is the number of units in the J-th column of the adjacency matrix A).  The maximum m11 m equals (the number of vertices of the graph).  The technical implementation of the one-dimensional array S is the first memory node 39 of the cycle allocation unit 17.  .  b).  If there are no incoming links, consider the next vertex for the presence of incoming arcs, go to step (a) and consider the next column, if not, go to step (c).  at).  Whether there is a direct connection from the i-th vertex () to one of the vertices that are elements of the array S.  If such a relationship exists, then the element of the adjacency matrix (A, g {, (, j 1 is equal to the unit CA, -stK,), where K1 1, t.  d).  If at least one equality of clause (c) is satisfied, then there is a cycle.  d).  If no equality of clause (c) is fulfilled, it is necessary, as a result of viewing the row number, to extract the arcs from the i-th vertex and to fix the vertex numbers in the simultaneous array of MVs.  The array elements of the MV are the values of the j column numbers, in which at the intersection with the i-th row there are units (M3 (K2) j, Γ), where t is the number of arcs leaving the i-th vertex.  The maximum number / j.  equal (n - the number of vertices in the graph).  The value of the elements of the array MZ (K2) must be rewritten into a similar one-dimensional M4 (KZ) Yu (K2), where.  The technical implementation of arrays MZ and M4 are, respectively, the second 40 and third 41 memory nodes of the cycle allocator 17.  e).  For Each element of the MV array must be checked to see if there is a direct connection from the vertices with the numerals of the MV (K2) where K2H, f to one of the vertices S (K1),, mg.   AM3 (K2), S (K1) 1.  If at least one equality holds, then there is a cycle.  g)  If none of the equality of clause (e) is necessary as a result of viewing the lines with the numbers M4 (FB), where, 1, identify the connections coming out of these vertices and fix the vertex numbers in the one-dimensional MOH array, and then after detection of all outgoing arcs from vertices with numbers equal to the values of the elements of the array M4, rewrite the values of the elements of the array MZ to the array M4.  Then go to item (e), if in item (g) do not get the zero array MOH (t. e.  are at a finite vertex from which no outgoing arcs exist).  If the MZ array is nonzero, not all vertices of the graph are examined for the presence of incoming arcs and no cycles are detected in points (c) and (e), go to point (a), in another case a single signal is generated that the column does not exist cycles, allowing the operation of the device.  In this case, the second stage of the work begins and the calculation of the maximum paths in the graphs.  Microprogram control unit 12 is designed as a finite automaton according to the Wilkes-Stringer model, the structure of which is determined by the structure of the block 12 operation algorithm. Block 12 is characterized by the alphabet of input signals P.  -P (features), 808 by the alphabet of the output signals by the alphabet of the states of the memory, the function of the outputs L and the function of the outputs of: c (t) (c (t-l), p (t)) is a transition function; Y (t) (c (t)) is a function of the outputs.  To set the alphabet of the states of the memory Cp-c, j, enter the marks at the inputs of all from the 1st to the 44th operator and conditional vertices of the algorithm of operation of the block 1 2.  The symbols Y, written to the operator vertices are output 12.  block signals The operation of block 12 is gated with a clock pulse generator 31.  Clock pulses from the clock pulse generator 31 come along with the alphabet signal of the input signals P-P.  if it exists.  While valid.  the clock pulse, the state of the main memory flip-flops 25 does not change, although the state of the flip-flops 27 of the auxiliary memory may vary.  The state of the main memory flip-flops 25 changes when the clock pulse ceases.  This ensures the stability of the operation of block 12, as long as the sync pulse is in effect, the triggers of the main memory 25 do not transition to a new state.  The alphabet of memory states is encoded by a binary code taken from the outputs of the main memory trigger 25.  The inputs of the auxiliary memory flip-flops 27 are associated with the outputs of the encoder 35, at the outputs of which a binary code is formed that sets the auxiliary memory flip-flops 27 to a new state of the alphabet of memory states with -C-.  The pulses of the clock generator 31 arrive at the control trigger 29 through the element 30, the outputs of which provide information that the block 12 is in the initial state c (set before starting operation by applying a signal to the input of Set. O) - In order to initiate the operation of the control unit, a single starting impulse is required at the input. Starting the memory unit 18 of the unit 12.  Decoder 28 of the alphabet of states of the memory converts the positional code at the output of the main memory flip-flops 25 into a unitary code.  The output control signals of the Walphabet output signals are generated depending on the state of the alphabet of memory states, into which control unit 12 has passed.  If the same signal is produced in different states of the alphabets of the Cd-s memory states.  block 12, then the corresponding outputs of the decoder 28 of the alphabet of memory states must be connected by an OR circuit.  For example, according to the algorithm of operation of block 2, a single signal Yj is generated when block 12 goes into state c.  or from the alphabet of states of memory.  Therefore, the corresponding outputs of the decoder 28 of the memory interconnection alphabet (SD and N are the element OR 36.  Block 12 enters a new state depending on the state at the pre-instant of time and on the signals of the alphabet of input signals (P-P-).  The law of transition of the block 12 to the new state of the alphabet of memory states is determined by the operation algorithm of the control unit (Fig.  2).  For example, to go to the Cg state of the memory states alphabet, it is necessary to be in the C state, the memory states alphabet.  Such a transition is carried out from state C at the next cycle of operation of microprogram control unit 12 in the presence of an alphabet signal from the input signals P. .  To complete the clock condition, you need to combine output C.  a decoder 28 of the alphabet of states of memory and an input P by an element And 32.  Signals of the input alphabet are received by the first and second informational entry of block 1 2.  The output element And 32 is denoted by the letter b ,. .  By connecting the output of the element 32 and the fifth input of the encoder 35, position code 00101, is obtained at the output of the encoder 35.  5y ,, Qi Comparison unit 16 operates as follows.  Suppose that at the output of the OR element 76 of the comparison block 16, there is zero, t. e.  trigger value (cells) 37. j block 14 is equal to zero, at the output of the element AND-NOT 77 there is a value of one.  If the output of the comparison trigger 78 is set to one, the output of the element 77 is a zero value.  At the output of the NAND element, there is a value equal to one, therefore, at the output of the NAND 72 element, a value equal to zero appears.  Sign P is zero.  Suppose that at the output of the element OR 20 of the comparison unit 16 there is a single value, t. e.  the value of the trigger (cell) 37 of block 14 is equal to one.  If at the output of the element IS-NOT 77 there is a single value, the sign P, is equal to one.  The operation of the proposed device is carried out in two stages. Pre-entry Set About node 18.  The memory of the firmware control unit 12 is supplied with a single signal that sets the auxiliary memory triggers 27 and the main memory triggers 25 to the zero state, setting the unit 2 to the initial state of the alphabet of memory states. The same. . the signal enters the address generation unit 15 and sets the control trigger 73 to the zero state, setting zero potential at the control output of the unit 15.  At the first stage of operation of the device, in block 14 and in the matrix model of network 1, information is entered about the topologies of the graph under study, mapped by the adjacency matrix A.  The impulse weights are entered into the weights of the arcs of the arcs 6, adding the weights of the vertices to the full capacity of the counters that block 12 is in the initial state (the unit potential at output C, decoder 28 of the state alphabet) 8 memory blocks 2. With the appearance of a single trigger signal at the input of the start of the node 8 of the memory of the I2 unit, operation of the device begins. The operation of block 12 is synchronized with a clock pulse generator 31, the clock pulses of which are determined by the maximum possible response time of the device’s circuit elements and through the element 30 in the presence of single potentials at the Start and C inputs go to control trigger 29, controlling the operation of the firmware module 12. Operation of the device trace the algorithm of the device. 1. At the first clock of the clock pulse generator 31, block I2 enters the state C. of the alphabet of memory states, and at the same time a sequence of single signals Ud, Yg is generated. , W. (operator 1). C, U. enters unit 15 and sets counter 65 to the zero state. The ur signal arrives at comparison unit 16 and sets the comparison trigger 78 to one state. The signal Y arrives at block 17. and sets the registers 46 of memory node 39, registers 58 of memory node 40, registers 50–50 41 memories. 2, Firmware control unit 12 enters state C of the alphabet of memory states, and a sequence of single signals Y (operator 2) is simultaneously generated. At Ss-le M d d enters unit 15 Signal X at counter 65 and increases its value by one (ST). The signal y, j enters the block 15n trigger 72 of the sign, setting the sign P ,. to zero state. ; Signals, U ,. , a block 17 arrives and sets, respectively, the counter 62 of the address of the memory node 41 (CT. d 0), the counter 55 of the address of the host. 40 memory (CTjj 0) and the counter 48 of the address of the memory node 39 (). The signal U. arrives at block 15, flashing the value of the 63 row counter (). 3 Block 12 enters state C ,, and simultaneously a sequence of single signals Y, is exhausted. Y, UY (operator 3).  The signal U2 goes to block 15 at the counter of 63 lines, increasing its value by one (CTg CTjg + l). The signal Y goes to block 15, gating the output of counter 65.  The signal Ud enters unit 15, gating the counter input 64 columns. At the same time generating signals U.  , Y ,, the counter 64 columns 8 k is assigned the value of the counter b5 of the block 15 ().  4, In the next cycle, block 12 enters the state C of the alphabet of state memory, and at one time a sequence of single signals V 20 –OR y, g is developed (operator 4) The signal V enters unit 15, gating the output of the counter 63 lines, The signal Xj enters block 15, gating the output of the counter 64 columns.   The signals Y, are received in block 15, gating respectively the outputs of the decoders 70 and 69.  The signal arrives at the switch 13, gating its output.  The signal enters the block 14, gating the outputs of the triggers 37.  Thus, when simultaneously generating signals in the register from the register group 46 of the first memory node 39 of the block 17, the value of the 63 row counter of the block 15 is recorded according to the address value of the first memory 39 node (the address counter 48).  8 In the next cycle, block 12 enters state C. , and simultaneously generated single signals (operator 8).  The signal enters block 17 at the first memory node 39, gating the output of the address counter 42.  The ultrasonic signal goes to block 17 on the first memory node 39, gating the input of register 49.  When signals are simultaneously processed, the register 49 of the block 17 of the first memory node 39 records the value of the address counter 48 (CT ,,).  9.  In the following, block 12 also enters the next state of the alphabet of memory states, depending on the value of the signal of the alphabet of input signals.  If the sign P, generated in block 15 (the value of the row counter 63 is equal to n), is zero, go to step 3, if not, go to step 10.  ten.  Block 12 (operator 10) enters the next state depending on the alphabet signal of the input signals.  If the sign P generated in block 17 (the value of the counter 48 of the address is zero) is equal to zero, go to step 2, in the other case to step 11.  In paragraphs 2-10, the column of the adjacency matrix A is viewed (the technical implementation of the adjacency matrix is block 14) with the number determined by the counter 65 of block 15. and the discovery of connections entering a vertex with a number determined by counter 65.  The numbers of THESE vertices are brought into a one-dimensional array S (the technical implementation of array S is the first memory node 39 of block 17).  In order to enable each register 46 to store the vertex numbers of the first memory node 39, an address counter 48, an address decoder 74, and a register 49 for storing the values of the address counter 48 are entered into it.  The address counter 48 is a technical implementation of the variable K1.  When the entire column is viewed (the value of the row counter 63 of block 15 is n), in the registers of the first node 39 of memory block 17 there is information about all connections entering the node with a number — determined by counter 65 of block 15, and Register 49 contains a value characterizing the number of elements in array S.  i1.  The firmware control unit 12 enters the next state and at the same time the generation of the sequence one is performed. , (operator 11).  signal Y, the signal Y enters the block 15, gating the output of the counter 65.  The signal enters the block 15, gating the input of the buffer register 6. At the same time generating these signals, the value of the counter 65 of the block 15 is written into the buffer register 66.  12. Block 12, go to state C of the alphabet of memory states, and at the same time a sequence of single signals Y / (operator 12) is generated.  The signal Y, arrives at block 15, gating the input of the row counter 63.  The signal Y enters block 15, gating the output of the buffer register 66.  With the simultaneous generation of signals, the value of the buffer register 66 is written to the line counter 63 of the address generation block 15, 13. On the next cycle, the firmware control unit 12 enters the state C of the alphabet of states of the memory and at the same time the sequence of the single unit is generated (special signals 13).  Signal at ,, ,, | enters the loop allocator 17 at the first memory node 39, gating the output of the address counter 48.  block 17 The signal Y 2g arrives at the first memory node 39, gating the output of the address decoder 74.  The signal X enters the address generation block 15, gating the input of the counter of 64 columns.  The signal U gates the output of the decoder 70 lines.  Thus, at simultaneous signal processing, the value of register 46 of the first node 39 of memory of block 17 (according to the address generated by address counter 48) is sent to block 15 at a counter of 64 columns.  14. Block 12 enters state C of the alphabet of memory states and, at the same time, a sequence of 4 t single signals is generated.  av  Y, 9 V RCD (operator 14).  The action of the operator is similar to that of the operator of step 4 (the trigger value (cell) 37 of the topology shaping unit 14 (according to the address) is sent to the comparison block 16).  15. At the next clock (operator 15), block 12 moves to the next state of the alphabet of memory states depending on the value of the signal of the alphabet of input signals.  If the sign is P (the sign of the operation of the equality comparison block, t. e.  the value of the cell of block 14 is equal to one) is equal to zero, go to paragraph 16, otherwise - to paragraph 30.  sixteen. Block 12 enters the state of the memory states alphabet (operator 16) and simultaneously produces a single signal (operator 16), which arrives at block 17 at address 48 of the first memory node 39 and decreases the value of address counter 48 by one.  17 On the next one there is a transition by a complicated condition.  If the sign P (expired in the first memory node 39 of block 17 and characterizes the zero state of the block 48 address counter) is zero, go to step 14, if not 18.  18, If the sign P (generated in the second memory node 40 of block 17 and characterizes the zero value of the block 55 address counter) is equal to zero, go to step 43, in the other case - to step 19.   nineteen.  If the sign (is blocked in block 15 by trigger 72; the sign Pg О can be characterized as a sign of the beginning of work, t. e. -view of a new vertex for the presence of incoming arcs is zero, go to item 22, if not - to item 20.  In the 11-18 npoHcxoAH punts, the following action.  In the buffer register 66 of block 15, either the value of the counter 65 characterizing the number of the next vertex examined for the presence of arcs, or the value of the MV array (technical implementation of the MV array of the second memory block 40 of the block 17) is recorded and checked in clause 15 whether direct communication from the vertex with the number characterized by the value of the buffer register 66 with one of the vertices of the array S (first node 39 of the m) of block 17.  Denote the buffer register 66 arbitrarily by the letter t.  The following check occurs.  The value of s (tn} adjacency matrix is one.  Under item 12, the value of the buffer register 66 is written to the row counter 63 of block 15, under item 13, the next value of the element S of the array (the contents of one of the registers 46 of the first memory node 39 of block 17) according to the value of the counter 48 of block 17 (K1) is written to A bill of 64 columns of block 15.  According to item 14, according to the value of row counters 63 and columns 64 of block 15, the trigger value (cell) 32 of block 14 is selected, which enters block 16 of comparison.  If such a connection exists (with P1), then there is a cycle (clause 15), if not, decrease the value of the address 48 counter by one and repeat the checks until the entire array S is viewed.  A sign of this is that the value 48 of the address of the first memory node 39 of block 17 is equal to zero (P Checking sign P occurs in clause 17.  If elements of the MOH array (second memory node 40 of block 17) are written to the buffer register 66, then the criterion for iterating over all the elements of the MOH array is. equal to zero the value of the counter 55 of the address of the second memory node 40.  This characterizes the sign P- (paragraph 18).  20.  Block 12 enters state C, the alphabet of memory states, and at the same time a sequence of single signals is generated, Y, Y (operator 20).  The signal g enters block 17 at the third memory node 41, gating the output of the address counter 62.  The signal enters block 17 at the third memory node 41, gating the output of the address decoder 59.  The signal Y enters block 17 at the third memory node 41, permitting the reading of information from registers 58. .  The signal enters the block 15, gating the input of the buffer register 66.  Thus, while simultaneously generating a sequence of signals, the value of the register 58 of the third memory node 41 of the block 17 according to the address generated by the address counter 62 is sent to the buffer register 66 of the block 15.  21.  In the next cycle, the control unit enters the state of the alphabet of memory states.  At the same time, the Y signal is generated. , (operator 21), arriving at block 17 at the third memory node 41 and decreasing the value of the counter 49 of the address 49 by one.  22  The block enters state C,. j-alphabet of memory states, and at the same time a single signal Y is produced (operator 22), which enters block 15 and resets a counter of 64 columns.  23. Block 12 enters state C.  the alphabet of states of the memory, and at the same time a single signal Y is generated (operator 23), which enters block 15 and increases the value of the counter of columns 64 of block 15 by one.  24 Block 12 enters state C of the alphabet of memory states, and simultaneously a sequence of single signals Y, (operator 24) is generated.  The signal Y enters block 15, gating the input of the counter for 63 lines.  The signal Y ,, enters block 15, gating the output of the buffer register 66 of the block.  Thus, the value of the buffer register 66 of block 15 is written to the counter of 63 rows.  25  Block 12 enters the state of the alphabet of memory states and, at the same time, generates a sequence of single signals Y, Y, 17 Y (operator 25).   On the 19th 30th of the operator 25, similarly to the action of the operator 14 (paragraph 14) (the trigger value (cell) 37 of the block 14 is assigned to the address) is sent to the comparison block 16.  26, Block 12 enters the next state.  If the sign P- (generated in the comparison block 16 and is the criterion of the comparison block for equality) is equal to one (the trigger value (cell) 37 block 14 is equal to one), go to paragraph 27, in the other case - to 30 27. . Block 12 enters state C, -, and simultaneously generates a single signal (operator 2 which enters unit 17 at the second memory node 40 and increments the value of the block 55 address counter.  28  Block 12 enters the Cjg state, and at the same time a sequence of single signals is generated. 33 Fishing Y ,, UOS, U ,, Y 41 3S The signal Y goes to the second memory node 40 of block 17, gating the output of the counter 55 of the address.  The signal Uz5 is supplied to the second memory node 40 of block 17, by strobing the output of the address decoder 53.  The signal Y arrives at the second memory node 40, permitting the recording of information in registers 52.  The signal UT enters the block 15, gating the output of the counter 64 columns.  Thus, while simultaneously developing such a sequence, the value of the column counter 64 of the block 15 is recorded in the register from the group of registers 52 of the second node 40 of memory block 17 according to the address ST 55 (the counter value 55 of the address serves as the address of the selected register).  29.  Block 12 goes into states, and at the same time a sequence of single signals Y, Y, is generated.  The signal Y arrives at the second memory node 40 of block 17, gates the output of counter 55, address a.  The signal U.  arrives at the second node 40 of memory block 17, gating the input of register 54.  With simultaneous generation of signals, the value of the counter 55 of the address 0 of the second node 40 of the memory of block 17 is written to the register 54 of the block.  Block 12 enters a state C, wherein a sequence of single signals is not generated.  Block 12 enters the next state of the memory states alphabet depending on the input alphabet signals.  If the sign P (expired in block 15 and indicates that the value of the counter of columns 64 of block 15 is equal to n) is equal to zero, go to step 23, if not, go to step 31.  31. If the sign Pg is generated in block 15 (trigger 72) and is characterized as a sign of the start of work, t. e.  viewing a new vertex for the presence of leaving arcs) is zero, go to point 32, if not to point 33.  32. Block 12 enters a state of 2g, and at the same time a single signal y is output.  g, entering block 15 on trigger 72 and setting trigger 77 to the unit state P 1, goes to step 34.  33.  If a sign of R.  (generated in block 17 in the third memory node 41 and informs that the value of the address 62 counter is zero) is zero, goes to step 20, in the other case - to step 34.  34  If the sign P (outlined in the second memory node 40 of block 17 and informs that the value of the address counter 55 is zero) is zero, go to step 35, if not, go to step 36.  .  35  Block 12 enters the SD state, and a sequence of single signals, Y, is simultaneously built.  The signal Y goes to the second node 40 of the memory of block I7, gating the output of register 54.  The signal arrives at the third memory node 41 of block 17, gating the input of register 61.  With simultaneous generation of signals Y ,,, the register 61 of block 17 (the third memory node records the value of the register 54 (second memory node 40)).  37.  Block 12 transition - "g to state C. jj of the alphabet of states, and at the same time a sequence of single signals Y, is generated (operator 37).  The signal enters block 17 at the third memory node 41, gating the input of the address counter 62.  The signal Y enters block 17 at the third memory node 4), gating the output of register 61.  39  Block 12 goes into the state of C- ,, and at the same time 6 sequence of single signals is generated, Y, Y, U, UZ (operator 39).  Signal y. j enters block 17 at the third node 41 of memory 41, the gate output of the counter 62 of the address.  The signal U2 gates the output of the decoder of the address of the third memory node 41.  The signal permits the recording of information in the registers 58 of block 17 (the third memory node 41). The signal Y arrives at block 17 at the second memory node 40, gating the output of the address counter 55.  The signal U-1C enters unit 17 at the second memory node 40, gating the output of the address decoder 53.  The signal Y enters block 17 at the second memory node 40 and permits reading of information from registers 52.  The simultaneous generation of this sequence into one of the registers 58 of the third memory node 4 of block 17 according to the address of the address counter 61 (the value of the counter 61 serves as the address of a selectable register) the value of one register 5 is recorded according to the address of the address counter 55 (the value of the counter 55 serves the address of the selected pe1 isstra).  40 Block 12 enters state C of the alphabet of states, and simultaneously a sequence of single signals Y is produced. The signal arrives at the second memory node 40 of block i 7, reducing the value of the address counter 55 by one.  Signal.  enters the third memory node 41 of block 17 and decreases the value of the address counter 62 by one.  41 Block 12 enters the next state, depending on the input signal.  8020 If the sign Pd (generated in the second memory node 40 of block 17 and informs that the value of the address counter 55 is zero) is zero, go to step 39, if not, go to step 42.  42  The controlling automaton goes into a state, and at the same time a sequence of single signals is generated,, Y,.  The signal Udou enters unit 17 at the second memory node 40, gating the output of register 72.  The signal enters block 17 at the second memory node 40, gating the input of counter 55 of the address.  Signal DC  enters block 17 at the third memory node 41, gating the output of register 61.  The signal enters block 17 at the third memory node 41, gating the input of the address counter 62.  With the simultaneous generation of such a sequence of signals, the value of register 54 is recorded in the address counter 55 of the second memory node 40 of block 17, and the value of register 61 is recorded in the address counter 62 of the third memory node 41 of block 17. 43  Block 12 enters a state, and simultaneously a sequence of single signals Y is being produced.  , Y, Y, Y (operator 43).    L5 l} The signal U ,, enters block 17 at the second memory node 40, gating the output of the address counter 55.  The signal enters block 17 at the second memory node 40, gating the output of address decoder 53.  The signal Y, from, enters block 17 at the second memory node 40, enabling reading of information from registers 52.  The signal U |, enters the block 15, gating the input of the buffer register 66.  Thus, while simultaneously developing the sequence of signals, the buffer register 66 of block I5 records the value of one of the registers 52 of the second memory node 40 of block 17 according to the address of the selectable register, which is the value of the counter 55 of the address.  44.  Block 12 enters the state Cj, and at the same time a sequence of single signals is generated. A signal Y. The value of the address counter 55 in the second node is reduced by 40 units of block 17 per unit.  The Y-, 2 signal arrives at block 17 at the first memory node 39, and gates the input of the address counter 48.  The signal enters block 17 at the first memory node 39, and gates the output of register 49.  Thus, with the simultaneous generation of signals, the value of the counter 55 of the address of the second node 40 of the memory block 17 is reduced by one and the register counter 48 of the address records the value of register 49 in block 17; Go to paragraph 12.  36  The controlling automatic switch to the next state.  If the sign Pj (generated in block 15 and informs that the value of the counter 65 is equal to n) is zero, go to step 2, and if not, go to step 38.  38  Block 12 goes into states and at the same time a single signal Y is produced, which enters block 15 and sets the control trigger 73 to one state. Block 12 goes to the next state and the control block ends (the process of detecting the cycles is finished).  This completes the first stage of operation of the device.  If there are no cycles in the graph, then as a result of the first stage of operation of the device, the control trigger is set to a single state and the single potential at the output of the three control wheels 73 serves as a trigger signal at the input of the AND element 4. The second stage of the device operation begins, in which, in the absence of cycles, the maximum paths are calculated using a known device. If cycles exist, and the control trigger 73 of the block 15 is not set to one and the second stage of operation is absent, i.e. in cyclic graphs, maximum paths are not calculated. In paragraphs I9-30, the following occurs. If up to clause 19 (clause 15) no cycles were detected, you need to go 0-22 times outgoing links (arcs) from the i-th vertex. If the sign P (clause 19) is equal to zero, then the next vertex is considered for the presence of incoming arcs (the beginning of a new stage of information processing). In this case, the array M4 is still unformed (the technical implementation of the array M4 is the third memory node 41 of block 17) and the value of the counter 65 of block 15 is taken as the number (t) of the i-th vertex. If the array M4 is formed (sign P 1 ) then it is necessary to look at all the values of the M4 array as the number of the i-th vertex. For this, in step 20, the next value of the element of the M4 array (one of the registers 58) according to the address of the address counter 49 (FB) is written into the buffer register 66 (t) of block 15. Then, the viewing of the row of the adjacency matrix starts (technical implementation — block 14 of the formation of the topology Count). In paragraph 21, the scoring value of the address 62 (SC) by one is reduced. It is necessary to look at the rows with that number (the value of m is the value of register 65 of block 15 or the value of an element of array m4 (third memory node 41 of block 17). For this counter, 64 columns of block 15 are null in step 22, and in step 23 the counter value is 64 columns of block 15. In paragraphs 24-26, the trigger value (cell) of block 14 is sampled, and in comparison block 16, the value of 37ij cell is compared with the unit value of comparative trigger 78 78 of block 16. If the trigger value (cell) is 37, -j block 14 is equal to one one arc), coming out of the vertex), the next element of the array M3 is filled. For this, in paragraph 27 a new value of the counter 55 of the address (K2) is set, according to this value of the address 55 in the Zdin register 52 the value of the counter of 64 columns of block 15 is recorded (paragraph 28), and in paragraph 29 the value of the counter 55 of the address of the second node 40 of the block 17 is written to block register 54. If the entire string is scanned (sign P) is equal to one, operator 30), and register 54 of the second 23 memory block records the number of links leaving the i-th vertex (the number of elements in the MV array). The line scan operation continues depending on the number of elements in the M4 array (the elements of the M4 array are numbered lines) or one line is scanned with a number equal to the RG value of block 15 if the P attribute is zero. If all the array elements are viewed (P flag 0) i.e. the value of the fault is equal to zero (address counter 62), which means that a new MZ array was formed (the second memory node 40 of block 17). If the newly formed MZ array is zero, the outgoing outgoing from the i-th vertex of the communication comes to the final one, and, therefore, if not all the vertices in the graph are examined for the presence of incoming arcs (feature (item 36), go to item 2 and the process is repeated. If the array MZ is nonzero, its values are rewritten into array M4 (second memory node 40 of block 17) in paragraphs 35-41 and, after the necessary auxiliary operations 42-44, go to step 12. determine the maximum paths in the graphs on the autor.St. No. 862145, characterized by then, in order to expand the field of application of the device by enabling the study of graphs for the presence of cycles and loops in them and improving the accuracy of determining the maximum paths, a comparison block, an address generation unit, a switch, a cycle allocation block and a microprogram control unit, and a topology shaping unit are introduced into it the graph under study, containing the AND group of elements and the trigger matrix, the cycle selection block contains three memory nodes and two OR groups of elements, the installation inputs of the triggers are set ochnymi input devices, each input i-ro matrix connected to the first latch row WMOs i-ro AND element group forming the topology of the graph of the test unit where {2,. . . , p p), the outputs of the elements AND groups of the formation unit of the topology of the graph under study are connected to the corresponding information 8024 inputs of the first switch group, the second input of each i-ro element AND group of the formation block of the topology of the graph under study is connected to the i-th output of the output group of the microprogram block control, information inputs of the first and second memory nodes are combined and connected to the output of the array of vertex numbers of the address generation unit, the first and second information outputs of the second memory node are connected Respectively to the first and second information inputs of the third memory node, write resolution of all the memory nodes are combined and connected to the output of micro-operations of the microprogram control unit, each i-th output of the output group of the first memory node is connected to the first input of the i-ro element OR first groups of the cycle selection block, each i-th output of the second group of information outputs of the second memory node is connected to the first input of the i-ro element AND the second group of the cycle selection block,. the second input of which is connected to the i-th output of the group of outputs of the third memory node, the output of each i-ro element OR of the second group of the cycle locking unit is connected to the second input of the i-ro element OR of the first group of the cycle selection block, the output of which is connected to the same input of the group information inputs of the address shaping unit whose output of the address shaping is connected to the second information input of the switch, the controlling output of which is connected to the output of the micro-operations of the microprogram control unit, the output of the switch connected to the first information input of the comparison unit, the second information input of which is connected to the output of the microoperations of the microprogram control unit; the output of the comparison unit is connected to the input of the logic condition of the microprogrammed control unit whose input is connected to the output of the formation of the sign of the address generation unit whose input of microcommands is connected to the output microoperations of the firmware control block, the output of the formation of the trigger signal of the address generation block is connected to the third I. course element // y // / Y / y . / J JDR BUT. //// U /. / f / yV. /// MNP / 7 / Jl © @one . IPuf.5 7 Phie. 3