SU798854A1 - Device for simulating network graphs - Google Patents

Description

The invention relates to computing and can be used in the study of the parameters of network graphs. A device is known for determining the critical path in a graph, which contains a network model, a control unit, a pulse generator, an arc wearer, the number of columns of the matrix, the elements OR, AND, triggers l. However, the device only allows the determination of the shortest path, numerically equal to the number of pulses, counted in the control unit. The closest in technical essence to the present invention is a device for simulating network graphs containing a control unit, a pulse input of which is connected to the output of a pulse generator, elements AND according to the number of columns of the matrix network model, chains of successively connected counters and. trigger by the number of rows and columns of the matrix network model. The trigger output of each column is connected to the information input of the AND element of the corresponding column 2. The disadvantage of this device is the low accuracy of the simulation. The purpose of the invention is to improve accuracy. This goal is achieved by the fact that a device for simulating network g) s, containing a matrix of arc weights formers, each of which contains a trigger and a counter, the output of which is connected to the trigger input, the trigger output of the arc shaper matrix, is connected to the information input of the corresponding the element AND of the first group, the clock pulse generator, the output of which is connected to the input of the pulse distributor, are introduced the element, NOT, the group of elements AND, the group of counters, the comparison circuits and the triggers counting in Each one of which is connected to the output of the corresponding comparison circuit, the first inputs of each of which are connected to the first output of the pulse distributor, the second output of which is connected to the first inputs of the elements AND of the second group, the second inputs of which are connected to the outputs of the elements NOT whose output is connected to the outputs corresponding elements And the first group

to the first inputs of the elements of the third group, the outputs of which are connected to the counters moves the corresponding rows of the matrix of the formers of the scales ug and to the first inputs of the elements of the fourth group, the second inputs of which are connected to the third output of the pulse distributor, the fourth output of which is connected to the second inputs of the elements of the third group and to the third inputs of the elements And the second group, the outputs of the elements And the second and fourth groups are connected through appropriate counters with. the second and third inputs of the respective comparison circuits.

, ia the drawing shows a structural diagram of the device.

The device contains ((it matrix matrix 1 network, distributor 2 pulses, generator 3 clock pulses, according to the number of rows and columns of the matrix, formers 4 weights-arcs, including counters 5 and triggers-in, according to the number of columns of the matrix, the first group of elements And 7, He elements 8, the third group of elements And 9, the second group of elements And 10 and the fourth group of elements And 11, a group of counters 12 and 13, comparison schemes 14 and triggers 15.

Model 1 of the network is a matrix of homogeneous cells of the Formers of the weights of arcs with the size of php, where max is the maximum number of nodes of the simulated graph.

The device works in the same way.

In the initial state, all the triggers 15, the counters 12 and 13 are in the zero state. The distributor 2 supplies the enabling signal to the control input of the element 10. Initially, information on the topology of the simulated network graph is entered into model 1. In this case, the triggers b of the formers 4, which simulate the branches of the graph, are set to one. The corresponding shaper 4 is determined by the Line Row with the number equal to the starting node number of the simulated branch and the column with the number equal to the number of its ending node. The counters 5 of the corresponding formers 4 bring in the number of pulses, which add to the duration of the branches to the full capacity of the counters. After entering the initial information at the inputs of the And 7 elements that combine the outputs of the formers 4 in the columns corresponding to the initial nodes of the simulated graph, there will be high potentials. This is due to the fact that in a unidirectional graph without cycles and a loop, the initial nodes do not contain incoming branches, and, consequently, the triggers 6 of the formers 4 that are in this column will be in the zero state (elements

and 7 are connected. by the zero inputs of the triggers 6. The determination of the vertices of the graph forming the critical path is carried out in three stages.

At the first stage, the determination of the most equal moments of the beginning of the occurrence of events for the vertices of the graph under study is carried out. For this, with the appearance of a trigger signal, the distributor 2 permits the passage of pulses from the output of generator 3 to the inputs of all elements 9 and 10. At the same time, the pulses pass to the inputs of those counters 5 whose corresponding columns of matrix 1 simulate the weights of arcs emanating from the initial nodes . These same pulses through the elements And 10 pass to the counters 12 of all the vertices of the graph, except the initial one, since the output of the corresponding element is NOT 8 - a high potential.

By counting the number of pulses proportional to the weight of the simulated arc, the counter 5 of one of the formers overflows, sets the corresponding trigger b to the zero state, and the input from the zero output of this trigger enters the input of the corresponding element And 7. If at the other inputs of this element AND 7 are the resolving potentials, then the resolving signal appears at its output. This indicates that the weights of the arcs included in the node, whose number corresponds to the column number of the drivers 4, united by this element AND -1, are formed. In this case, the resolution is formed, the pulses arriving at the inputs of the counters 5 of the formers 4, which simulate the branches of the graph, coming from the formed node. At the same time, a high potential is supplied to the input of the column element and low from its output, therefore, the supply of pulses to the input of counter 12 through the element 10 stops and the time of the earliest start of the event for the given graph is fixed at the output of counter 12. The computational process continues until high potentials are present at the inputs of all And 7 elements. This indicates that all the nodes in the study of the graph are formed. The distributor 2 at the same time stops the supply of pulses to the inputs of elements And 9 and 10. The number of pulses recorded at the meter 12, corresponds to the moments of the earliest onset of the events. At this point, the first stage of operation of the proposed device ends. /

At the second stage, the determination of the most late moments of the beginning of the accomplishment of events for all vertices of the graph under study is carried out. For this, the distributor 2 recovers the information about the topology of the simulated network graph, and the initial graph is entered into the matrix network model in inverse order, i.e. adjacency matrix of the entered graph is transposed relative to the non-principal diagonal.

With the appearance of the trigger signal, the distributor 2 permits the passage of pulses from the output of the generator 3 to the inputs of all elements AND 9 and further to the inputs of elements AND 11 of the corresponding column and counters 5 of the same row of the matrix. In addition, the distributor 2 delivers the enabling signal to the controlled input of the And 11 elements, so the pulses then go to the counting inputs of counters 13. Having counted the number of pulses proportional to the weight of the simulated arc, the counter 5 of one of the formers overflows and the input of the corresponding And 7 element enters enable signal from this trigger. If at the remaining inputs of the And 7 element there are resolving potentials, then at the output of the I9 element there appear pulsed signals, which are fed to the counters 5 of the same row of the matrix and through the elements 11 to the counters 13, etc. The computational process at the second stage continues until the high potentials are present at the outputs of all elements And 7.

The third stage of operation of the device consists in comparing the readings of the counters 12 and 13, corresponding to the earliest and latest events, by applying the control signal to the comparison circuits 14 by the distributor 2. From the output of the circuits 14, the comparison signal transfers the triggers 15 to a single state. The unit states of the triggers 15- correspond to the vertices of the graph forming the maximum critical path.

Because of the blocks introduced and the connections between them, the accuracy of the simulation is improved.

Claims (2)

1. USSR author's certificate No. 525954, c. C F F 15/20, 1976.. five 2. USSR Author's Certificate No. 491132, class No. F 15/20, 1974 (prototype).