US3735109A - System for discovering a critical path in a network - Google Patents

Abstract

A plurality of node elements are interconnected by link elements together with an appropriate control center for simulating or modelling a network. Three categories of lines interconnect and pass through the node elements. One, a Beta chain conveys signals from node element to node element via respective link elements in a direction through the network. A second, a gamma chain conveys signals in the direction opposite to the direction of the Beta chain. The third, an Beta chain conveys signals in the same direction as the Beta chain and effectively forms a validation in the network-modelling circuit which is necessary for operation of the corresponding Beta chain. Signals are advanced stepwise under supervision of a clock (part of the control center). Energization of the gamma chain is initiated at the end of the advance of the Beta signals. The networkmodelling circuit includes a circuit which is arranged to detect amongst the several link elements connected to each node element the first one, or the last one, or both the first and last ones which are reached by the Beta signal. This detection is employed to progressively validate the gamma line. Loops are detected either by exciting signals in the Alpha chain before Beta excitation from a target point of the network and interrupting the excitation after Alpha signals have progressed as far as they can, or alternatively by artificially rendering all the gamma lines conductive before Beta excitation and exciting the gamma chain from a target point and then interrupting the gamma excitation after gamma signals have progressed as far as they may. In either case the loops and the parts of the circuit downstream of the loops remain capable of passing signals.

Description

United States Berthelemy et al.

atent H 1 [54] SYSTEM FOR DISCOVERING A CRITICAL PATH IN A NETWORK [75] Inventors: Jacques Berthelemy, Thorigny; Pierre Germain R. Boue, Butte Montceau; Jacques Louis Sauvan, Paris, all of France [73] Assignee: Societe Anonyme: Societe Nationale DEtude Et De Construction De Moteurs DAviation, Paris, France [22] Filed: June 1, 1971 [21] Appl. No.: 148,835

[30] Foreign Application Priority Data Primary ExaminerFelix D. Gruber Attorney-Flynn & Frishauf May 22, 1973 [57] ABSTRACT A plurality of node elements are interconnected by link elements together with an appropriate control center for simulating or modelling a network. Three categories of lines interconnect and pass through the node elements. One, a B chain conveys signals from node element to node element via respective link elements in a direction through the network. A second, a 7 chain conveys signals in the direction opposite to the direction of the B chain. The third, an B chain conveys signals in the same direction as the B chain and effectively forms a validation in the network-modelling circuit which is necessary for operation of the corresponding B chain. Signals are advanced stepwise under supervision of a clock (part of the control center). Energization of the 7 chain is initiated at the end of the advance of the B signals. The networkmodelling circuit includes a circuit which is arranged to detect amongst the several link elements connected to each node element the first one, or the last one, or both the first and last ones which are reached by the B signal. This detection is employed to progressively validate the 7 line. Loops are detected either by exciting signals in the a chain before B excitation from a target point of the network and interrupting the excitation after a signals have progressed as far as they can, or alternatively by artificially rendering all the y lines conductive before B excitation and exciting the y chain from a target point and then interrupting the y excitation after -y signals have progressed as far as they may. in either case the loops and the parts of the circuit downstream of the loops remain capable of passing signals.

17 Claims, 10 Drawing Figures 5 3 IH Tjg A4 A E Y 6. H0 CONTROL CENTER "fidfiiiswncnaomo V r L J ORIGIN POINT ,1 2m TARGET pQg T CLOCK [COUNTER Eh N s HoRT PATH RESTART START STOP TARGET PATENTEB M22 [975 3 735 ,109

SHEET 2 (IF 5 T'IqnZ rengrawrmmm PATENTEU MAY 2 2197s SHEET S []F 5 This invention relates to the study and operation of networks represented by, or representative of graphs or data relating to problems in connection with the interaction of the components, and more particularly to problems in which the possibilities of a system changing over from particular states to other states are predetermined. The networks consists of a number of points or nodes or junctions interconnected by vectors or links. The links can be weighted by values representative of steps, or power of advance required to pass from any node to an adjacent node; if this advance or progression is intermittent and stepwise, the weighting given any link indicates the number of steps necessary to progress through the link. The origin of any link will be called the predecessor node and the end of any link will be called the successor node.

Operating a network to solve a problem usually means searching for a path in the network between a starting-point node and a target-point node. Some problems may have more than one starting point and more than one target point. Given any starting point and any target point, there are usually a number of paths between them. Determining the shortest path between these points may be one problem, whereas other problems involve determining the longest path, also called the critical path or maximum path i.e., the path having the greatest number of steps. The latter kind of problem occurs inter alia in programming tasks using PERT (Program Evaluation Research Task) diagrams.

Network-modelling facilities for carrying out minimum and maximum path research or scheduling are known and usually comprise logic circuits grouped in two categories of elements allotted to the network nodes and links and called node elements and link elements respectively and interconnected by lines. Path research comprises simulating the network path by transmitting signals which advance stepwise between consecutive node elements and dwell at each link element for a number of steps equal to the weight of such link element, as disclosed e.g., by U.S. Pat No.

3,558,868, which relates to determination of minimum path, by the present inventors, and assigned to the assignee of the present invention.

In critical (i.e., maximum) path programming, assuming that the signals advance in the direction of link orientation, any node element at which a number of signals gated through different link elements are arriving must gate only the last of such signals i.e., the signal which has had to pass through or acquire the most steps on its way from its starting point to the particular node concerned. To this end, each node element is provided with an AND-gate having )1 inputs, n denoting the number of links leading to the corresponding node. The AND-gate opens only when the n lines extending from the n link elements preceding the node element are excited, whereafter the AND-gate output, which is connected to the p link elements after the node, delivers the signals into such link elements. The node set as target point is therefore reached after a number of steps equal to the number of steps in the critical or maximum path between the starting point and the target point.

To indicate the configuration of the critical path, the link elements have means for detecting the last one of the link elements leading to a given node element which had provided an output signal to the AND-gate of this node element, for only this last link element has any chance of forming part of the critical path.

SUBJECT MATTER OF THE PRESENT INVENTION A network-modelling circuit is provided having a plurality of node elements interconnected by link elements. The link elements provide, with the node elements, three categories of lines interconnecting and passing through the node elements:

a. a first category forming a B chain for conveying signals from node element to node element via respective link elements in a predetermined direction through the network,

b. a second category forming a 'y chain adapted to convey signals in a direction opposite to the said predetermined direction, and

c. a third category forming an a chain adapted to convey signals in the same direction as the B chain and extending through the node elements by way of OR gates and forming in the network a preset condition, or validation necessary for operation of the corresponding B chain.

A control center with a clock for supervising stepwise advance of signals along the B chain has means to initiate energization of the 7 chain at the end of such advance.

The B chain comprises in each node element an AND gate to whose inputs are connected the B lines from the several link elements connected to such node element. The several link elements have associated therewith a circuit adapted to detect and select from the group of such several link elements the one which was the first one reached by a B signal; or the one which was the last one reached by a B signal (which may be termed the limiting link elements) or both the first and last ones reached by a B signal. In response to such detection, an AND gate on the 7 line extending through the link element so selected is energized, or validated. The invention also provides a method of detecting loops in a network by exciting signals in a chain before any starting of the clock by triggering a chain, e.g., the a chain from at least one extreme (target or starting) point of the network and for a. time sufficiently long for the signal to travel as far as the end of the chain; and

thereafter interrupting such excitation by the signals to reveal the loops and those parts of the networkmodelling circuit downstream of the loops by displaying the elements which remain in signal passing condition.

Some of the foregoing explanations and the explanations to be given hereinafter are made with reference to the accompanying drawings, wherein:

FIG. 1 shows a network;

FIG. 2 is a diagram showing critical path finding in the network of FIG. 1;

FIG. 3 shows another network in which critical path finding is difficult;

FIG. 4 shows a network containing a loop;

FIG. 5 shows an embodiment of node elements and link elements of a system according to the invention;

FIG. 6 shows a predecessor node and the links extending therefrom;

FIG. 7 shows an improved mesh or link element of use for loop detection in a network;

FIG. 8 shows a variant of a node element for a special finding problem;

FIG. 9 is a diagram showing how a node element can be adapted to minimum path finding in a network, and

FIG. 10 shows a node element adapted as shown in FIG. 9.

Referring to the network ABCDEF of FIG. 1, where the links are weighted as indicated, the signals going from starting point A to target point D advance in the manner shown in the Table in FIG. 2, where the con secutive pulses of a clock timing the stepwise advance of the signals are plotted along the abscissa and the various links of the network are plotted along the ordinate, their weight i.e., the number of steps which the signals must take to pass through a link being shown on the left, while on the right there can be seen the number of steps which a signal still has to take to leave its link after each clock pulse. A heavy solid line associated with a link passed through by a signal indicates that such link is the last of the links extending to the same node to have been passed through and so may form part of the critical path. Each such link is framed in an oval in FIG. 1.

Starting from A the signal moving along AB reachgs B in one step but cann ot pass therethrough, since EB has not been excited. AB is passed glrough in t wo steps and E transmits the signal both to EF and to EB. At the next step, since EB has bee r passed through, B allows a signal to advance along BC. The signal continues to advance in this way until, having passed through C2, it reaches D at the end of the twelfth clock pulse, FD having been passed through at the end of the seventh clock pulse. As can be gathered from FIG. 1, if it is endeavored, starting from D, to go back along the network in the opposite direction using only links which can form part of the critical path (links in oval framing), the critical path A.E.F.C.D. in the example selected is determined with certainty. One may determine the path of course also be searching from the starting point towards the target point or destination point; this method is equally valid. Progressing from the starting point to the target point, is an arrangement which accords more with common sense and which will be assumed hereinafter to be the method used.

Unfortunately, the system in the aforementioned U.S. Pat. No. 3,558,868 described has disadvantages. If the suggested logic circuit is really going to determine a solution of the problem of determining the maximum, or critical path. The starting point and the target point chosen in the network must be such that the seeking or searching signal travelling back from the target point towards the starting point goes through all such network links as are accessible from the starting point. This is not generally the case, as can readily be gathered from FIG. 3. Let A be the starting point in this network and G the tgrget point. A signal going from G to F along the link FG can never pass through F since the AND-gate within the node element Ii has two inputs, one connected to the link element F6 and the other connected to link element FC, and no signal frgm G can ever return along FC since the links BC and FC are dead-ends as regards paths between A and G. Consequently, the signaLcan never travel back along EF nor, therefore, along AE, and so the circuit cannot provide the longest path between A and G. In the case shown in FIG. I the same difficulty would have arisen if the target point chosen had been a node other than the node D. To determine critical, or maximum path, this system therefore has a serious shortcoming.

Another disadvantage is that the risk of error increases in a complex network. This may require a good deal of debugging time and occasionally the work of more than one systems analyst. Errors often come to light as by the appearance of loops in the network, and searching for a maximum path then becomes nonsensical. One such case is shown in I16. i where 3 signal from F travels along the links CF, BC and EF. The search signal will never travel through E since the sig nal will r iever go back along the link E l nor go through B, for DB will never be passed through. The reason for this is the existence of the loop BDE. Although such loops are nonsensical in critical path programming problems, they often occur in practice in networks and must be detected and eliminated.

This invention is for improvements in or relating to critical path scheduling systems which can inter alia obviate these disadvantages and adapt such systems for the solution of a wide range of problems.

In the drawings, gates marked are OR-gates, and gates marked 9 are AND-gates.

Referring to FIG. 5, a mesh or link element M of a system according to the invention has on one side a predecessor node element N and on the other side a successor node element N Each node element is placed inside a solid-line frame, the element M being indicated by a symbolic arrow and the node elements N N being indicated each by a circle of hatching. Connections between node elements and mesh or link elements can be broken down into three categories B, y and 0: indicated by braces. The 6 connections are responsible for transferring critical path finding signals from the target point back to the starting point; this procedure is known as ,8 backwards finding. Upon the completion thereof the 7 connections are responsible for transferring a signal which originates at the starting point and which travels exclusively via links or meshes previously detected as able to form part of the critical path. The function of the 0: connections will be described hereinafter. The network is therefore embodied by a system comprising node elements, mesh or link elements and B, y and or lines forming what are called B, 'y and a chains.

Each node element has anAND-gate n 1 having n inputs E on the B chain, n denoting the number of meshes or links extending from the particular node concerned. The output of gate 9 I is connected via OR-gate U12 to output S of the node element; the OR- gate U12 can also be energized from input E of the element through which the ,8 signal is applied if such element is the target point of the sought-for path as selected on aprogram switch board 300. As many [3interrogation lines 50 extend fromoutput 8;, as links or meshes adjoin the node. The interrogation lines 50' are connected to the mesh-element inputs E and extend toAND-gate n 3. AND-gate 3 has clock signals from clock 262 applied to input l-Io of the mesh element M whenAND-gate 3 is enabled by its other inputs, the Ho clock signals are applied to abackwards counter D 31 consisting of flip-flops, the transmission depending upon the following conditions being satisfied.

1. The successor node N has transmitted the B signal so that E is energized;

2. The predecessor node Np has still not transmitted the B signal i.e., mesh-element input E, is energized. The latter input is connected by aB setting line 51 to output S of the predecessor node element N Output S is energized over an inverter l 2i provided that ANDgate n 1 of element N is blocked (nonconductive), a condition which is detected at the output of OR-gate U12, and

3. Thebackwards counter D 31 is not in a state in which it must be blocked. AND-gate n 7 whose function will be described in greater detail hereinafter detects the state of thecounter 31 and connects, overinverter l 23 the last energization signal toAND-gate 3.

At the start of the path finding operation,counter D 31 is set at a value equal to the weight allotted to the link, M. A signal is then applied to input E of the node element of the target point and the clock supervising the advance of such signal along the ,8 chain is started. When this signal has passed through AND-gate n l of node element N; of FIG. 5, and assuming that the three conditions just mentioned are met,AND-gate n 3 is open(conductive) and the counter 31counts 1 step backwards at each clock pulse until the value is reached. This 0 state is detected by AND-decoding gate a 4 which is connected tooutput 3 of link element M via OR-gate U11. Of course, exactly the same result would be achieved if, instead of thebackwards counter D 31 being used, a counter were to be used which before the start of finding was set to a value which is the complement of link weight relatively to its capacity. When backwards counterD 31 has returned to 0, input E of AND-gate n l of node element N is energized over output S of the link element con cerned, but the search signal can pass through the element N only if the other inputs E are energized i.e., if the otherbackwards counters D 31 of the elements M connected to N have returned to 0. There must also be provision for detecting the last of the backward counters to return to 0 so that the corresponding mesh or link can be recognized as forming part of the critical path. The network therefore includes a 'y chain which can transfer signals from the starting-point node element to the target-point node element.

The 7 chain is formed of OR-gates 2 receiving at inputs E and 7 lines coming from the link elements extending to the particular node element concerned, each OR-gate 2 having another input E which is energized when a particular node element is to be the starting point.

The y lines enter link elements M via inputs E connected to output S ofOR-gate U 2 of the predecessor elements N 1: leave the element M at S, which are connected to E of the successor node element N The 7 line has an AND-gate n therein which is normally validated by inverters l 22 (whose function will be described hereinafter). AND-gate 5 opens (becomes conductive) only if the output ofdecoding AND-gate n 4 ofbackwards counter D 31 indicates that the same has returned to 0, this condition being transmitted byline 49. A signal applied to the starting-point node element via input E orOR-gate U 2 can travel over the lines of the 'y chain only when the B signal has reached the starting point after having energized the AND-gates 245 of the links along which it has travelled.

However, for any given predecessor node only theAND-gate Q 5 of the last link element M to pass the )8 signal need be validated. This could be achieved by providing such link element with a two-state device delivering the information that itis the last link element to have returned to O. This two-state device need not be provided if thebackwards counters D 31 cease backwards counting not only when they have reached the 0 state but only when the next clock pulse has returned all their two-state devices to the 1 state. This state corresponds to the highest binary number which the backwards counter can represent (2" 1 in the case of n two-state devices). This state will hereinafter be called the 1 state for convenience. AND-gate n 7 detects that all the two-state devices are in the l position and delivers a signal which acts via I 23 to inhibit AND-gate 0 3 and to block thebackwards counter D 31 in this 1 state. Simultaneously the AND-gate n 7 keeps output S energized via OR-gate U 11 (line 71), taking the place of the signal output from AND-gate 244..

Using the 1 state of the backwards counter to memorize the fact that it has passed through 0 reduces the maximum weight which can be allotted to the links by 1. In other words, if thebackwards counter D 31 has n two-state devices, the link can be given a weight of from 1 to 2"--2. The loss of capacity arising from this blocking in the -1 state is therefore very slight.

The basic logic of the system is really based on the three following principles:

Thebackwards counter D 31 of a link element decreases by l at each clock pulse if the following conditions exist:

AND-gate n l of successor node validated AND-gate Q l of predecessor node not validated State of backwards counter other than l;

The ,8 signal passes through anode element Q 1 validated) when all the backwards counters of the links for which it is the predecessor are at either 0 or l;

TheAND-gate n 5 of the 7 line of a link element M is validated only by the 0 state of the backwards counter.

Consideration will now be given by way of example to die case shown inHQ 6 vt here there is a node A and three links or meshes AB, AC, AD, extend therefrom. It will be assumed that the backwards counters t th e se three lin ks reach the 0 state in tl1 e order AB, AC, AD. When AB returns to 0, ATC and AD are in a state othgr than 0, the ,8 signal does not go through A and AB changes to l at th e next clock pulse. When the backwards counter of AC reaches 0, still no signal has gone through A and such backwards counter also becomes blocked in the 1 state. When the backwards counter of AD reaches 0, the backwards counter of the three links from the node A are seen thereby to be either 0 or -l, and so node A transmits via the lines 51 a signal serving to block the threebackwards counters D 31.. This blogking is superfluous for AB and AC but blocks the AD backwards counter in the 0 state. If the y signal subsequently reaches A after the end of the search, such signal will travel along the 7 line of the AD link element, whoseAND-gate n 5 is the only gate validated.

Path length is indicated by the number of steps made by the clock as counted in counter 200 between the start of search and the time at which search is stopped by the appearance of the B signal atoutput 8;, of the node marked as starting point. The clock stops only when the backwards counter of the last link extending from the starting point has returned to 0. When the other backwards counters of the links extending from such starting point change over to 0, the 7 signal travels for one clock signal period along a path other than the longest. The speed of the system is such that this event does not affect a display system controlled from the 'y lines. In other cases, e.g., if it is required to display the path set up, the disadvantage can be obviated if input E ofOR-gate U 2 of the starting-point node element becomes energized only from the time at which the appearance of the B signal atoutput 8;, of such node element has stopped the clock. Consequently, the 7 chain can be energized only when the state of the backwards counters has been finally set.

The system includes acontrol center 201 including the clock 202, the clock pulse counter 200, and connecti'ons for stopping the clock when the B signal has passed through theAND-gate 1 of the startingpoint node element. This stopping can be under the control of an ordinary AND-gate which detects coincidence between the selection of the node considered to be the starting point and the passage of the B signal through such node. The control center has other automatic functions which will be mentioned hereinafter; it is of conventional construction and uses logic circuits and flip-flops. The circuits hereinbefore referred to can be built using any appropriate technology. More particularly in the case of an electronic system, the backwards counter can take the form of master-slave type flipflops which change their state at the end of the clock pulse. Using JK two-state devices or any other flip-flop system would merely require reversal of clock signal polarity.

The critical path indicated by the path of travel of the 7 signal can be recorded or displayed; in the latter event the display can be formed either by the nodeelement outputs or by the link-element outputs or by both on the 7 chain. The display can therefore be obtained by sampling at the outputs S and/or 8,. Link display gives a fuller indication of the critical path, but node display is cheaper than link display since there are fewer nodes than links or meshes in a network.

FIG. 5 also shows a link hierarchy circuit. In B backwards path search two or morebackwards counters D 31 may return to zero simultaneously and also be the last to pass the B signal towards the predecessor node element N,.. .In other words, the two backwards counters remain simultaneously blocked in the state at the end of path finding and do not change over to the l state and so they will validate two AND-gate n on the 7 lines which leave the predecessor node element at S thus giving an indication that there are two critical paths having the same number of steps. The 7 signal will travel via these two paths and cause them to be displayed or recorded. Perhaps just a single critical path is required, in which case a hierarchy system is used for the links extending from each node, comprising the inverter I 22 which validates theAND-gate n 5 of the line 7 if the entry EH of the element M is not energized. Ahierarchy line 61 extends through all the link elements having the same predecessor, entering via input EH and leaving via SH, such link elements being classified along thehierarchy line 61 in a predetermined hierarchic order. The upstream and downstream ends of theline 61 are free. The first link element found going along theline 61 in the downstream direction and whoseAND-gate n 5 gates the 7 signal energizes theline 61 upstream, interrupts, by way of the next inverters I 22, the validations of the AND-gates n 5 of lowerranked links in the hierarchy. This is done very simply by means ofOR-gate U 6 which is provided in each link element on theline 61 and whose other input is connected by aline 62 to the output ofAND-gate n 5.

A link element inhibitor can be used if it is required to study modifications of a network. To inhibit a link element itsbackwards counter D 31 is locked at 1 by the inverter I 24, the same transmitting a signal which blocks all the two-state devices of thebackwards counter D 31 in the 1 position. Such link element validates the corresponding input E2 of the AND-gate 241 of its predecessor node element Np right at the start of the B search. ItsANDgate n 5 in the -y path can never be validated, everything proceeding as if the B signal had passed along such link before passing along any other link.

In practice, and in accordance with the invention, means are provided for automatically inhibiting some link elements in dependence upon problem data and inter alia upon the selected target point and starting point. As previously stated in relation to FIG. 3, for a critical path search system to do its job the B signal must be able to go back from the target point along all the network links accessible from the starting point. This condition does not always exist, andF 16. 5 shows an a chain circuit which, once the starting point and the target point have been selected, automatically selects links suitable for requirements before search starts and inhibits all the other link elements i.e., all such link elements from which the target point is inaccessible.

The output signal ofOR-gate U 8 of a node element drivesAND-gate n 14 in each link element connected to that node element and the output ofAND-gate n 14 feeds an input ofOR-gate U 8 of a predecessor node element to which the link is connected. A second input of ANDgate 0 14 is connected to an input W via which a link element validation signal is normally operative, arbitrary suppression of the latter signal causing the element to be inhibited. When the input W is energized, an a signal arriving at E fromoutput 8,, passes throughAND-gate n 14 and cancels the standing inhibition in which thebackwards counter D 31 is maintained by theinverter 1 24. The a signal continues on to output S and then to an input of aOR-gate U 8 of the predecessor element. Before the backwards counters 31 are set to the value of link weights, an input of theOR-gate U 8 of the node selected as target point can be energized to cancel the inhibition of the link elements from which such node is accessible. Such excitation proceeds from the input E of the node element via which the B signal is injected into the target OR-gate U 12 via theline 81 enteringOR-gate 8. Selectionof all the links from which the target point is accessible therefore occurs automatically as a result of selecting of the target node. The system which includes the OR-gates U 8 of the node elements and the AND-gaten 2414 of the link elements is called the a chain.

Selection from the network links those which form the PERT network leading to the selected goal will now be discussed. In the case of PERT diagrams, the target forms the final goal, and so all the links lead to it since they represent operagons leading thereto. For instance, in FIG. 3 the links BC and PC are inhibited i.e., their backwards counters are blocked at l since the output of theOR-gate U 8 of their successor nodes (node C) does not provide any signal. They therefore do not block nodes B and F however. It may occur that all the links extending from one or more nodes of the network are inhibited either externally (line W at O) or by the a chain (PERT network selection system). This corresponds to inhibition of the actual nodes and of the links leading to them.

FIG. also shows adisplay element 100 of the link element M, theelement 100 being connected to output SV ofOR-gate U 13 having two inputs, one of which is energized by the output of theAND-gate Q 5 on the 7 chain while the other is connected to the output ofAND-gate O 20 which can be externally controlled via its input E, for indicating that the link in the network is selected by the a chain for energization.

In the case shown in FIG. 4, where the links BD, DE and EB form a loop, a B signal starting from F can never pass beyond the nodes E and B for the following reasons:

To pass beyond E a signal must have gone back along EB i.e., the signal must have passed through B, and

To pass through B, a signal n 1ust have gone back along BD and therefore along DE i.e., the signal must have passed through E.

In other words, finding the longest path in a network with a loop is nonsensical since the length of paths comprising one or more links of the loop is indeterminate because they can be lengthened as desired by the loop being passed around more than once. If the starting point and target point in a network of this kind are so chosen that the or each loop is not on any path interconnecting the, no erroneous result occurs, for if the loops are not accessible from the starting point they will not prevent the [3 signal from returning thereto, and if the target point is not accessible from the loops the same are eliminated by the a chain.

The a chain is a means of automatically detecting loops;OR-gate U 8 of the node element of the target point is energized in a loopless network, the signal travels at electronic speed along the a chain. If there is a loop in the network the first node element of the loop to be reached by the a signal receives the same again after it has gone round the loop, with the result that the chain formed by theOR-gate U 8 andAND-gate 14 of the loop nodes and links are self-holding. If the energization of theOR-gate U 8 of the target-point node element is interrupted by disappearance of the signal at E the or element persists along the chain in the loop node and link elements and in those other node and link elements from which the loop is accessible.

To detect the presence of loops disturbing the target point, therefore, theOR-gate U 8 of the target-point node element can be energized in a first phase, hereinafter called the a phase, whereafter this validation can be interrupted. If there is a loop from which the target point is accessible, none of the output signals of the AND-gates Q 14 and OR-gates U 8 cease. If the display facilities are actuated by the outputs of the AND-gate 14, the links forming the or each loop and all the links from which such loop or at least one of such loops is accessible is indicated. TheOR-gate U 13 controls display (output SV) by means of the a signal when theAND-gate Q 20 is validated via input E-,.

It may be required to display only loops and not the routes leading to them, in which event the procedure is as follows:

If a signal coming from the node selected as starting point were to pass freely along the uninhibited links by passing through the OR U gates in each of the node ele ments, such signal would correspond to the a signal in that it would determine all the links accessible from the starting point. If energization of the starting point is interrupted, the signal disappears like or unless the network contains a loop, in which event the signal would be self-holding around the loop and in the nodes and links forming such a loop. To display nothing but loops, the links for which the a chain (selection of the PERT) and this new chain would both give a self-holding signal could be displayed. A chain of this kind is already avail able in the form of the 'y chain if some way can be devised of systematically validating the AND-gates Q 5 of the uninhibited links so that the OR-gates U 2 of the nodes within the network OR-gate a signal applied to thegate U 2 of the starting-point node element along all the accessible loops. The chain of gates which would normally be used just for the 7 phase is therefor used.

To validate the AND-gates Q 5 of the uninhibited links systematically there must be simulation of the 0 state of the backwards counter, the hierarchy must be inhibited and validation of the link must act on AND-gate 0 5 via input W.

FIG. 7 shows a link element meeting all these requirements. The link validation signal arriving via input W now acts also onAND-gate Q 5 vialine 52. This does not disturb normal operation since any link element not receiving the validation W has itsbackwards counter D 31 blocked at l and itsAND-gate Q 4 will never validate AND-gate O S. The hierarchy can be inhibited by AND-gate '0 16 by suppression of a validation normally applied to input IH. The zero state of thebackwards counter D 31 can be imitated for theAND-gate Q 5 byOR-gate U 15 by the application of a signal to input E OR-gates U 17,U 18 and AND- gate .0 l9 serve as means for operating a display system connected to the output SV by means of the following signals:

a a signal (output of AND-gate Q 14) if the input Aa ofAND-gate U 17 is energized; the latter signal will cause indication of the links from which the target point is accessible;

7 signal (output of AND-gate Q 5) if the input A ofOR-gate U 18 is energized; this signal permits read-out inter alia the longest path, and

Both the a and the 'y signals when neither Aa nor A'y are energized; this signal indicates inter alia loops in the network.

The AND-gate O 7 has an extra input E whose function will be described hereinafter.

The elements just described i.e., the node element N,,, N, of FIG. 5 and the link element of FIG. 7 therefore help to solve the following problems in any network. The control center signals enabling these results to be obtained are also indicated. In the first seven problems the ANDgates Q 5 are systematically validated by a signal applied toE 9 and the hierarchy is inhibited by the input II-I being set to 0.

1. Determination and display of all the links from which any node selected as target point is accessible. The corresponding node element must be selected by (energization of E11), the link weights and the inhibitions must be selected and the display is controlled by the a chain (energization of Au).

2. Determination and display of all the links accessible from any node selected as starting point. The cone sponding node element must be selected by energizetion of P the inputs E of all the node elements must be energized to release the general inhibition associated with the inoperative state of the a chain, the link weights and the inhibitions must be set and the display system must be controlled by the 7 signal (energization of A-y).

3. Determination and display of all the paths connecting any starting point to any target point. The starting point (energization of E and the target point (energization of 1111 must be selected, the link weights and the inhibitions must be set and the display must be actuated by the conjunction of signal A and y (Aa and A'y at More than one node can be selected7as a starting point and/or target point. The displayed links are:

' for problem 1: the links from which at least one of the target points is accessible;

for problem 2: the links which are accessible from at least one of the starting points;

for problem 3: the links on any path connecting any starting point to any target point.

4. Determination and display of links forming one or more loops in the network.

Read-in the selection of all nodes as starting points (energization of the E inputs) and as target points (energization of the E inputs), set the link weights and inhibitions, then interrupt the energizations of E and E The or each loop will be displayed upon supply of the a and 7 signal (Aa and A7 at 0).

5. Determination and display of the links forming one or more loops and of the links accessible from at least one such loop.

Same solution as for 4 except that the read-out is by 7 along (energization of A7).

6. Determination and display of the links forming one or more loops and of the links from which at least one such loop is accessible.

Same solution as for 4 except that display is actuated by 0: alone (energization of Au).

7. In 4 above all the nodes were selected as starting points and as target points so that all the loops of the network will be obtained.

If only a single starting point is selected, only the loops accessible from the corresponding node are displayed; if only a single target point is selected, only the loops from which such node is accessible are displayed. If only a single starting point and a single target point are selected, just the loops on any path able to connect the two points concerned are displayed. A check can therefore be made on the question of finding the longest path between a given starting point and a given target point in one direction.

More than one starting and/or target point can be selected, in which event the or each loop accessible from at least one starting point or from which at least one target point is accessible or which is disposed on any path between any starting point and any target point is obtained.

The backwards counters are not used for any of these problems (the only purpose of the link weighting facility is to set the backwards counters of the uninhibited links to a value other than -l). The system operates purely passively and is merely a set of gates. Solving these problems is only a minor feature of the system, its

other node as target point.

After a check has been made as described in 7 to ensure the absence of loops from all possible paths, proceed as follows:

OR-gate U 15 is not now energized via E and soAND-gate Q 5 can continue to operate only if thebackwards counter D 31 is at 0. The starting point and target point are set up normally. Setting-up or selecting the starting point not only energizes the node element input E but also connects itsoutput S 3 to the control center. The link weightings and the inhibitions are se lected, whereafter the clock is started, the whole system being controlled simultaneously by a single interrogation signal. The B signal goes back step by step along all the possible paths, as hereinbefore described, and stops the clock immediately when it appears atoutput S 3 of the starting-point node element. The longest path is immediately set up determined and the number of clock pulses (indicated by counter 200) equals the number of steps in such path.

If there is more than one maximum-length path, either all can be set up simultaneously or just one can be selected, according to the selected hierarchy criterion, by validating the input 11-1 of the AND-gates Q 16.

9. If any one node is taken as starting point and two or more other points are taken as target points, the target point connected to the starting point by the longest path can be determined and the longest path set up. The system is interrogated in just the same way as in 8 except that two or more target points are set up. The path displayed will lead to the furthest target point. Paths which on the way to a target point pass through some other target point are eliminated; this is the usual procedure since the idea behind the problem is to have a goal or aim consisting of two or more target points re quired to be reached as late as possible, and the first element of this aim is the one that counts. For maximum critical path finding in a PERT, all paths must be considered whether or not they go through some other target point or points; in this case the procedure described in 8 must be used, the system being interrogated separately for each target. If two or more target points are equally distant, a selection is made between them if the hierarchy system is validated; if it is inhibited the 2 or n paths are set up.

10. If any single node is taken as target point and more than two other nodes are taken as starting points, the starting point connected to the target point by the longest path can be found and the path displayed.

This is the trickiest problem to solve. The last starting point to be reached by the B signal is by definition the starting point of the longest of the critical paths found between the target point and each starting point. The clock must therefore stop when the [3 signal has reached thegates 1 of all the nodes set up as starting points. However, thegate 0 1 of every starting point reached before the final starting point has been validated. If the input E of theOR-gate U 2 is energized, the critical paths from all the corresponding nodes are set up. The clock pulse counter will therefore indicate the number of steps in the sought-for path but there is no way of knowing the starting point.

There are two ways of getting round this difficulty. The simplest way involves operator action. The control system has provision for blocking the clock whenever the a signal appears at theoutput S 3 of a node element set up as starting point; if the operator releases the clock manually, e.g., by means of a push-button, after each blocking, the critical paths are set up consecutively in order of increasing length at each operation of the button. The final starting point from which a path is displayed on the display panel is the required starting point. Another way is for the control system to have more elaborate provision such that the input E is energized only for the starting point whose AND-gate 241 was the last to have been reached by the B signal. The idea underlying this system is similar to the idea underlying the system of detecting the last link, of those extending from a given predecessor, which gated the B signal. A 3-count backwards counter (2two-state devices) is suitable for the maximum number of nodes required to be set up simultaneously as starting points. A backwards counter is allotted to each starting point by switching. At interrogation these backwards counters are in the 1 state (01). When the finding signal has reached a starting point, its backwards counter changes over to the state (00), and then in the next clock phase to the 1 state (1 1). The control center has a set of gates serving to stop the clock when all the backwards counters to which starting points are allotted are in the O or l state. Consequently, the or each last starting point reached by the finding signal has its backwards counter blocked at 0 whereas the others are blocked at l. If energization of the starting-point inputs B is initiated by the 0 state of the respective backwards counter, the 7 signal can go only from the or each starting point which is the last to have been reached by the search signal.

This system therefore has the advantage of setting up the true longest critical path, and therefor of determining its starting point, without operator action.

If the furthest starting point is the origin of more than one critical path, either all such paths can be set up or just one can be selected on a hierarchy basis.

If there is more than one starting point for equivalent maximum critical paths, all such paths are set up simultaneously whether or not the hierarchy is operative, since the same establishes a priority between links extending from a single node and not between links leading to a single node.

In contrast to what is stated inparagraph 9 about target points, paths which extend from a starting point to a target point by way of one other starting point are not eliminated. To deal with problems where such paths must be eliminated, the required elimination can be provided by extra AND-gates Q 30 and OR-gates U 32 and aninverter 1 26 in the node elements, as shown in FIG. 8. Energizing the input E of a node element to set it up as a starting point has the result (via I 26) of cancelling the validation of AND-gate Q 30 (ifE 8 is at 0). The a chain is therefore interrupted at such node and all the links leading thereto are inhibited by blockage of theirAND-gate Q 14. This system therefore leads to inhibition of all links leading to nodes set up as starting points. N o path extending from a starting point to the target point via some other starting point can be set up since all starting points are inaccessible. By validation viainput E 8, theOR-gate U 32 can restore the continuity of the a chain even though the node has been set up as starting point. This is essential to be able to deal with the problems mentioned inparagraph 2 andparagraph 3 in the case of more than one starting point.

11. Given random nodes taken as starting points and other random nodes taken as target points, what is the starting-point/target point pair with the maximum critical path and what is the setting-up of such path? Proceed exactly as initem 10 except for setting up more than one node as target points. The displayed route is the required path and its ends are likewise displayed.

The system hereinbefore described, with its node elements and its link elements, can be used, if a few minor I additions are made to it, for finding the shortest path between a starting point and a target point in the network or even the starting-point/target-point pair connected by the shortest path in cases in which more than one starting point and more than one target point are set up. The basic idea for this kind of searching is disclosed by US. Pat. No. 3,558,868 and involves a backwards B search in which any predecessor node element blocks all the link elements extending from it immediately the B signal has passed over one of such link elements.

ln shortest-path searching, inhibiting a link element is to prevent it from counting backwards so that itsbackwards counter D 31 never reaches 0. Blocking the backwards counter at 1 has the same effect.

As regards the link elements, only the 0 state of thebackwards counter D 31 must excite the predecessor node element in shortest-path finding. Consequently, to adaptthe link element of FIG. 7 to shortest-path searching, the AND-gate Q 7 must have added to it an input for decoding the -1 state of thebackwards counter D 31. This extra input E, is controlled by a general line from theprogram board 300 whose logic state determines the kind of searching:

0 state:shortest path 1 state: longest path.

With regard to the node elements, each predecessor must gate the B signal of the first link energized thereby and not of the last link energized thereby. For multipurpose use of the element, the AND-gate (l 1 can be replaced by the circuit shown in FIG. 9. There can be seen the normal inputs 42, theoutput 43 and acontrol input 44. If theinput 44 is in the 0 state, the circuit behaves like an AND-gate having an input 42 and anoutput 43, whereas ifinput 44 is energized the circuit is equivalent to an OR-gate.

Theinputs 44 of all the points are connected to a general line whose logic state determines the kind of searching:

0 state:longest path 1 state: shortest path.

FIG. 10 shows a correspondingly modified node element, where theOR-gate U 12 previously used to set up the target point now forms the system output OR- gate. Ifinput E 44 is at 0, the output ofgate U 1b is not used and only the signal of AND-gate la appears atoutput S 3. If E is in the 1 state, a single signal at an input E causes 8,, tobe energized via OR-gate 1b and AND-gate 9 1c (with the output ofOR-gate U 1b, any output from AND-gate 0 1a is merely redundant).

The display system can be lightened or supplemented by display of the nodes through the paths passed. To this end, the node elements can include the circuit of the OR-gates U 17,U 18 andAND-gate Q 19 which prepare the display signal (output SV) in the link elements.OR-gate U 17 always has applied to it the 'y signal which in the node element is the output of OR-gate U 2 (output S andOR-gate U 18 always has applied to its input the a signal which in the node element is the output of OR-gate U 8 (output S This leads to the node elements shown in FIG. 10. The associated link elements are exactly the same as the link elements of FIG. 7, The previous elements are a means of solving and setting up solutions for all the network problems hereinbefore referred to.

What is claimed is:

1. In combination:

a network-modelling circuit having a plurality of node elements (N,,, N,) interconnected by link elements (M), the link elements providing with the node elements three categories of lines interconnecting and passing through the node elements,

a. a first category forming a B chain for conveying signals from node element to node element via respective link elements in a predetermined direction through the network,

b. a second category forming a 7 chain adapted to convey signals in a direction opposite to the said predetermined direction, and

c. a third category forming an a chain adapted to convey signals in the same direction as the B chain and extending through the node elements; OR gates (8) included in the a chain and forming in the network a validation necessary for operation of the corresponding B chain; and a control center (201) comprising a clock (202) for supervising a stepwise advance of signals along the B chain and for initiating energization of the "y chain at the end of such advance;

the B chain comprising in each node element an AND gate (1,) to whose inputs (E2) are connected the B lines (50) from the several link elements (M) connected to such node element, and said several link elements having associated therewith a circuit (3, 31, 4, 7, 11) adapted to detect and select from such several elements, the first one reached by a B signal, or the last one reached by a B signal or both the first and last ones reached by a Bsignal, and adapted, in response to such detection, to validate an AND gate (5) on the 7 chain extending through the link element so selected.

2. A combination according toclaim 1, wherein the control center (201) includes circuit, means for transmitting a signal (E6; 0:) to the a chain for a time sufficient for such signal to travel along all the lines of the a chain which are accessible to the signal.

3. A combination according toclaim 1, wherein each link element comprises a circuit for rendering the -y chain conductive through the respective link element (M) in the absence of energization of the B chain, and wherein the control center (201) includes circuit means for transmitting a signal to the 7 chain for a time sufficient for such signal to travel along all the lines of the 7 chain which are accessible to thesignal 4. A combination according to'claim 3, wherein each of the link elements (M) is provided with an output or .display element (SV) connected both to the a chain and to the 7 chain by way of an AND gate (13; 19).

5. A combination according toclaim 4, .wherein the a chain and the 'y chain are connected to the AND gate (19) via respective OR-gates (17, 18) adapted to be energized in response to external instructions (Aa; Ay).

6. A combination according toclaim 3, wherein each of the node elements (N,,, N is provided with an output or display element (SV) connected both to the a chain and to the y chain by way of an AND gate.

7. A combination according toclaim 6, wherein the a chain and the 7 chain are connected to the AND gate (19) via respective OR-gates (17, 18) adapted to be energized in response to external instructions (Aa, A3

8. A combination according toclaim 1, wherein the B lines effectively define a reverse direction through the network from respective successor node elements (N,) to respective predecessor node elements (N and wherein each B line comprises in each link element an AND gate (3) which is arranged to be validated by the output of the AND gate (1) of the predecessor node element (N periodically by the clock (202; Ho), the output of the said link AND gate (3) being connected to a counter (31) counting for a value corresponding to the weight attributed to the particular link element concerned, and a decoding gate (4) arranged to detect a pretermined count of the counter (31) and having an output (S2) which is connected to the B line of the predecessor node element (N,,) and which is arranged to validate and AND gate (5) in the 7 line.

9. A combination according toclaim 8, wherein a second decoding state (7) is connected to the output side of the counter (31), and is arranged to detect the occurrence of an extra pulse in the backwards counter after its count to the predetermined number to produce an output signal, the output signal being connected to replace the output signal of the first decoding gate (4) at the B input of the predecessor node element (N,,) and being connected to act via an inverter (23) to invalidate the said link AND gate (3).

10. A combination according toclaim 9, wherein said link elements (N) are arranged to be inhibited by blocking of the counter in the extra pulse state by an inverter (24) controlled by the a chain.

11. A combination according toclaim 1, wherein the several link elements (M) connected to a node element (N) form a hierarchy, there being provided a hierarchy line (61, EH, IH) through said several elements and along which the several elements are classified in a predetermined order, the hierarchy line (61) being arranged to act via a respective inverter (22) to close the AND gate (5) of the 7 line of respective link elements when energized, and the hierarchy line comprising respective OR gates (6) connected to the output side of the respective AND gate (5) of the preceding link element.

12. A combination according toclaim 9, wherein each link element (M) is provided with an input for blocking the second decoding gate (7); and wherein each node element comprises an AND gate and an OR gate (1b) which is connected to be interrupted (1c) in response to external instructions (E44), said AND gate (10) and said OR gate (1b) being connected in parallel with the input (E2) of the B chain in the node element.

13. A combination according toclaim 1, wherein the control center (201) is connected to initiate a signal in the -y chain after interruption of the clock (202).

14. A combination according toclaim 13, wherein the clock 202) is connected to be blocked by the last node element reached by the signals (S3) advanced along the B chain.

15. A method of detecting loops in a network, comprising the steps of:

i. setting up in combination a control center (201) and a network-modelling circuit corresponding to said network;

the network-modelling circuit having a plurality of node elements (N,,, N.) interconnected by link elements (M), the link elements providing with the node elements three categories of lines interconnecting and passing through the node elements, a. a first category forming a B chain for conveying signals from node element to node element via respective link elements in a predetermined direction through the network,

b. a second category forming a 7 chain adapted to convey signals in a direction opposite to the said predetermined direction, and

c. a third category forming an or chain adapted to convey signals in the same direction as the B chain and extending through the node elements by way of OR gates (8) and forming in the network a validation necessary for operation of the corresponding B chain; the control center comprising a clock (202) for supervising a stepwise advance of signals along the B chain and for initiating energization of the 7 chain at the end of such advance;

and the B chain comprising in each node element an AND gate (1) to whose inputs (B2) are connected the B lines (50) from the several link elements (M) connected to such node element, and said several link elements (M) having associated therewith a circuit adapted to .detect and select from the several link elements, the first one reached by a B signal, or the last one reached by a B signal or both the first and last ones reached by a B signal, and adapted in response to such detection to validate an AND gate (5) on the 7 line extending through the link element so selected;

ii. exciting circuit setting signals in one of the chains before any starting of the clock by triggering said one chain from at least one node element of the network and for a time sufficiently long for the trigger signal to progress as far as the end of the chain and to set circuit elements in the network; and

iii thereafter interrupting the circuit setting signals and displaying the loops revealed in the networkmodelling circuit, and the circuit downstream of the loops.

16. Method according toclaim 15, wherein the a chain is excited, by exciting at least one target point of the network.

17. Method according toclaim 15, comprising the step of artificially rendering all the 7 lines conductive before the clock (202) is started;

and the 7 chain is excited, by exciting at least one starting point of the network.

Claims (17)

1. In combination: a network-modelling circuit having a plurality of node elements (Np, Ns) interconnected by link elements (M), the link elements providing with the node elements three categories of lines interconnecting and passing through the node elements, a. a first category forming a Beta chain for conveying signals from node element to node element via respective link elements in a predetermined direction through the network, b. a second category forming a gamma chain adapted to convey signals in a direction opposite to the said predetermined direction, and c. a third category forming an Alpha chain adapted to convey signals in the same direction as the Beta chain and extending through the node elements; OR gates (8) included in the Alpha chain and forming in the network a validation necessary for operation of the corresponding Beta chain; and a control center (201) comprising a clock (202) for supervising a stepwise advance of signals along the Beta chain and for initiating energization of the gamma chain at the end of such advance; the Beta chain comprising in each node element an AND gate (1) to whose inputs (E2) are connected the Beta lines (50) from the several link elements (M) connected to such node element, and said several link elements having associated therewith a circuit (3, 31, 4, 7, 11) adapted to detect and select from such several elements, the first one reached by a Beta signal, or the last one reached by a Beta signal or both the first and last ones reached by a Beta signal, and adapted, in response to such detection, to validate an AND gate (5) on the gamma chain extending through the link element so selected.

2. A combination according to claim 1, wherein the control center (201) includes circuit, means for transmitting a signal (E6; Alpha ) to the Alpha chain for a time sufficient for such signal to travel along all the lines of the Alpha chain which are accessible to the signal.

3. A combination according to claim 1, wherein each link element comprises a circuit for rendering the gamma chain conductive through the respective link Element (M) in the absence of energization of the Beta chain, and wherein the control center (201) includes circuit means for transmitting a signal to the gamma chain for a time sufficient for such signal to travel along all the lines of the gamma chain which are accessible to the signal

4. A combination according to claim 3, wherein each of the link elements (M) is provided with an output or display element (SV) connected both to the Alpha chain and to the gamma chain by way of an AND gate (13; 19).

5. A combination according to claim 4, wherein the Alpha chain and the gamma chain are connected to the AND gate (19) via respective OR-gates (17, 18) adapted to be energized in response to external instructions (A Alpha ; A gamma ).

6. A combination according to claim 3, wherein each of the node elements (Np, N2) is provided with an output or display element (SV) connected both to the Alpha chain and to the gamma chain by way of an AND gate.

7. A combination according to claim 6, wherein the Alpha chain and the gamma chain are connected to the AND gate (19) via respective OR-gates (17, 18) adapted to be energized in response to external instructions (A Alpha , A gamma ).

8. A combination according to claim 1, wherein the Beta lines effectively define a reverse direction through the network from respective successor node elements (Ns) to respective predecessor node elements (Np) and wherein each Beta line comprises in each link element an AND gate (3) which is arranged to be validated by the output of the AND gate (1) of the predecessor node element (Np) periodically by the clock (202; Ho), the output of the said link AND gate (3) being connected to a counter (31) counting for a value corresponding to the weight attributed to the particular link element concerned, and a decoding gate (4) arranged to detect a pretermined count of the counter (31) and having an output (S2) which is connected to the Beta line of the predecessor node element (Np) and which is arranged to validate and AND gate (5) in the gamma line.

9. A combination according to claim 8, wherein a second decoding state (7) is connected to the output side of the counter (31), and is arranged to detect the occurrence of an extra pulse in the backwards counter after its count to the predetermined number to produce an output signal, the output signal being connected to replace the output signal of the first decoding gate (4) at the Beta input of the predecessor node element (Np) and being connected to act via an inverter (23) to invalidate the said link AND gate (3).

10. A combination according to claim 9, wherein said link elements (N) are arranged to be inhibited by blocking of the counter in the extra pulse state by an inverter (24) controlled by the Alpha chain.

11. A combination according to claim 1, wherein the several link elements (M) connected to a node element (N) form a hierarchy, there being provided a hierarchy line (61, EH, IH) through said several elements and along which the several elements are classified in a predetermined order, the hierarchy line (61) being arranged to act via a respective inverter (22) to close the AND gate (5) of the gamma line of respective link elements when energized, and the hierarchy line comprising respective OR gates (6) connected to the output side of the respective AND gate (5) of the preceding link element.

12. A combination according to claim 9, wherein each link element (M) is provided with an input for blocking the second decoding gate (7); and wherein each node element comprises an AND gate and an OR gate (1b) which is connected to be interrupted (1c) in response to external instructions (E44), said AND gate (1a) and said OR gate (1b) being connected in parallel with the input (E2) of the Beta chain in the node element.

13. A combination according to claim 1, wherein the conTrol center (201) is connected to initiate a signal in the gamma chain after interruption of the clock (202).

14. A combination according to claim 13, wherein the clock (202) is connected to be blocked by the last node element reached by the signals (S3) advanced along the Beta chain.

15. A method of detecting loops in a network, comprising the steps of: i. setting up in combination a control center (201) and a network-modelling circuit corresponding to said network; the network-modelling circuit having a plurality of node elements (Np, Ns) interconnected by link elements (M), the link elements providing with the node elements three categories of lines interconnecting and passing through the node elements, a. a first category forming a Beta chain for conveying signals from node element to node element via respective link elements in a predetermined direction through the network, b. a second category forming a gamma chain adapted to convey signals in a direction opposite to the said predetermined direction, and c. a third category forming an Alpha chain adapted to convey signals in the same direction as the Beta chain and extending through the node elements by way of OR gates (8) and forming in the network a validation necessary for operation of the corresponding Beta chain; the control center comprising a clock (202) for supervising a stepwise advance of signals along the Beta chain and for initiating energization of the gamma chain at the end of such advance; and the Beta chain comprising in each node element an AND gate (1) to whose inputs (E2) are connected the Beta lines (50) from the several link elements (M) connected to such node element, and said several link elements (M) having associated therewith a circuit adapted to detect and select from the several link elements, the first one reached by a Beta signal, or the last one reached by a Beta signal or both the first and last ones reached by a Beta signal, and adapted in response to such detection to validate an AND gate (5) on the gamma line extending through the link element so selected; ii. exciting circuit setting signals in one of the chains before any starting of the clock by triggering said one chain from at least one node element of the network and for a time sufficiently long for the trigger signal to progress as far as the end of the chain and to set circuit elements in the network; and iii thereafter interrupting the circuit setting signals and displaying the loops revealed in the network-modelling circuit, and the circuit downstream of the loops.

16. Method according to claim 15, wherein the Alpha chain is excited, by exciting at least one target point of the network.

17. Method according to claim 15, comprising the step of artificially rendering all the gamma lines conductive before the clock (202) is started; and the gamma chain is excited, by exciting at least one starting point of the network.

Images