Method and system for finding or plotting an optimum path

Claim 2

Method of determining the shortest interconnection between a first point, or set of points, to a second point, or set of points, said points being located in a mesh network having interconnecting links, connecting said points together, comprising: applying addressing signals to first and second points to identify and select said first and second points within the points of the mesh network; applying tracing signals emanating from said second addressed point to all interconnecting links connected thereto; conducting said tracing signals from said links to all points connected to said links, other than said second point, and, during said conducting step; timing the progression of said tracing signals through all said links in accordance with predetermined characteristics of said links; passing said tracing signals through said points connected to said links and inhibiting said points, having said tracing signals passed therethrough, from accepting tracing signals from other links connected to respective points, at subsequent periods of time; repetitively applying said tracing signals from said points to subsequent links connected thereto; inhibiting the first addressed point, first reached by a tracing signal from a connecting link, from accepting subsequent tracing signals from other links connected thereto; establishing through those points and links, through which a tracing signal passed, a continuous closed connection, to establish a continuous circuit between said first and second points; and identifying those points and interconnecting links through which the tracing signal has passed and which are a part of said continuous, closed connection between said first and second points.

Claim 3

Method according to claim 1 wherein the step of timing the progression of the tracing signal comprises the step of controlling the timing of progression of said tracing signals in discrete timed steps, and controlling the number of steps required for passing of a signal through a link.

Claim 4

Method according to claim 1 further comprising the steps of: generating control signals in those interconnecting links which are part of said continuous closed connection between said first and second points; and controlling the continuity of a second circuit path through those points and those interconnecting links, by said control signals.

Claim 5

System to trace the shortest path from a first point, or set of points to a second point, or set of points, said points being located within a network of points, said network having interconnecting links emanating from said points and interconnecting said points in a predetermined pattern, comprising: a source of clock pulses (19); a plurality of similar nodal circuit elements (FIG. 3) forming nodal points in the system, said nodal circuit elements having input and output terminals and means (26), controlled by said clock pulses and by signals applied to at least one of said terminals, to establish a circuit path between said input and output terminals; a plurality of similar link circuit elements (FIG. 4) forming interconnecting links in the system, said link circuit elements being connected to said nodal circuit elements in accordance with the pattern of the network, said link elements having input and output terminals and means, controlled by said clock pulses and by signals applied to at least one of said terminals, establishing a circuit path between said input and output terminals; at least one time delay element (FIG. 5) selectively associated with, and connected to a link circuit element, said time delay element being connected to, and controlled by said source of clock pulses and having means delaying signals passing through the circuit path of said link element by a preselected number of clock pulses, the number of pulses of delay being determined by a characteristic of said delay element, whereby the output signals from the link elements having said time delay element associated therewith will appear at a time delayed with respect to the clock pulses controlling said circuit path; said circuit elements additionally comprising means (FIG. 3: 25-S2; FIG. 4: E7- 30- 29) inhibiting establishment of a circuit pAth through a preceding link element connected to a nodal element when a circuit path has already been established from another link element to said nodal element; means applying an addressing signal to one of said nodal circuit elements at a location in said network of points corresponding to said second point, said addressing signal controlling said nodal circuit element to enable application of said clock pulses to an output terminal, and hence to any link circuit element connected thereto; means applying a an addressing signal to another one of said nodal circuit elements elements at another location in said network of points, corresponding to said first point, said second addressing signal inhibiting progression of a clock pulse applied to said second nodal element from any link circuit element to a further connected link circuit element; and whereby the circuit path requiring the least number of clock pulses between said one nodal circuit element, and said other nodal circuit element, over said link circuits, will be established between said one and said other nodal circuit elements.

Claim 6

System to trace the shortest path from a first point, or set of points to a second point, or set of points, said points being located within a network of points, said network having interconnecting links emanating from said points and interconnecting said points in a predetermined pattern, comprising: a source of clock pulses (19); a plurality of similar nodal circuit elements (FIG. 3) forming nodal points in the system, said nodal circuit elements having input and output terminals and means (26), controlled by said clock pulses and by signals applied to at least one of said terminals, to establish a circuit path between said input and output terminals; a plurality of similar link circuit elements (FIG. 4) forming interconnecting links in the system, said link circuit elements being connected to said nodal circuit elements in accordance with the pattern of the network, said link elements having input and output terminals and means, controlled by said clock pulses and by signals applied to at least one of said terminals, establishing a circuit path between said input and output terminals; at least one time delay element (FIG. 5) selectively associated with, and connected to a link circuit element, said time delay element being connected to, and controlled by said source of clock pulses and having means delaying signals passing through the circuit path of said link element by a preselected number of clock pulses, the number of pulses of delay being determined by a characteristic of said delay element, whereby the output signals from the link elements having said time delay element associated therewith will appear at a time delayed with respect to the clock pulses controlling said circuit path; said circuit elements additionally comprising means (FIG. 3: 25-S2; FIG. 4: E7- 30- 29) inhibiting establishment of a circuit pAth through a preceding link element connected to a nodal element when a circuit path has already been established from another link element to said nodal element; means applying an addressing signal to one of said nodal circuit elements at a location in said network of points corresponding to said second point, said addressing signal controlling said nodal circuit element to enable application of said clock pulses to an output terminal, and hence to any link circuit element connected thereto; means applying a an addressing signal to another one of said nodal circuit elements elements at another location in said network of points, corresponding to said first point, said second addressing signal inhibiting progression of a clock pulse applied to said second nodal element from any link circuit element to a further connected link circuit element; and whereby the circuit path requiring the least number of clock pulses between said one nodal circuit element, and said other nodal circuit element, over said link circuits, will be established between said one and said other nodal circuit elements.

Claim 7

System according to claim 4 wherein said time delay (FIG. 5) element includes a pulse counter (38) connected to have said clock pulses applied thereto, the delay time being a whole number of clock pulses.

Claim 8

System according to claim 4 wherein said circuit elements have a pair of parallel circuit paths, each path passing signals in opposite direction.

Claim 9

System according to claim 4 wherein said nodal circuit elements comprise a bistable memory (25) and an AND gate (26), said AND gate (26) being controlled by a conjunction of timing signals from said clock pulse source (16) and said addressing signal, or by an output from a link circuit element being connected to said nodal circuit element; and interconnecting means controlling change of state of said memory (25) upon appearance of an output from said AND gate.

Claim 10

System according to claim 7, including a second circuit in parallel with said bistable memory (25) and said AND gate (26), said second circuit passing signals in a direction opposite to the signal paths through said bistable memory.

Claim 11

System according to claim 7, wherein said link elements are oriented, each including a circuit comprising: a bistable memory (28), and an AND gate (29) having an output connected to control said bistable memory; an OR gate (16); the output (S5) of said memory (28) and a first input (E6) of said AND gate being respectively connected, through said OR gate (16) to an input (E2) of the AND gate (26) of the nodal element forming a connection to the link element; and said link element further including an inverter (30) connected to the output (S2) of the bistable memory (26) of the next nodal element, said inverter having a further output connected to the AND gate (29) of the link element.

Claim 12

System according to claim 9, wherein said time delay element comprises: a binary counter (38); and an AND gate (39) controlling said counter, one of the inputs (40) of said AND gate (39) is connected to the output (S3) of the bistable memory (25) of the nodal element in advance of the link element with which the time delay element is associated; a decoding circuit (42); the output of the counter (38) being applied to said decoding circuit, said decoding circuit being preset to provide an output pulse only after a predetermined number of input pulses from said counter have been counted to define said characteristic of the delay element; and the output, after decoding, being applied to an additional input (31, 32) to the AND gate 29 of the link element to which the delay element is connected.

Claim 13

System according to claim 9, wherein said link element is oriented and comprises an inhibiting circuit (34) including an amplifier (33), the output of said amplifier being connected to an additional input of the AND gate (29) of the link element.

Claim 14

System according to cLaim 4, wherein said source of clock pulses supplied a pair of pulse output signals (T1, T2), one of which (T7) is connected (20- E3) to control the nodal elements (FIG. 3) and the other (T2) is connected (18- E5) to control the link elements (FIG. 4).

Claim 15

System according to claim 9, wherein: said circuit path establishing a selected itinerary between departure and arrival nodes includes an amplifier (27) ad associated with each of the nodal elements; an OR gate (17); an AND gate (35) associated with each of said link elements, the output of said AND gate (35) being connected (S4) through said OR gate (17) to the input of the amplifier (27) associated with the nodal element next connected to the link element; said AND gate (35) having additional inputs connected to the output of the bistable memory (28) of the link element.

Claim 16

System according to claim 12, including: an additional AND gate (35) included in said circuit path; an inhibiting amplifier (37); said additional AND gate (35) being controlled by said inhibiting amplifier (37); and means (36) controlling the operation of said inhibiting amplifier to inhibit progression of signals in said path.

Claim 17

System according to claim 4, wherein: the circuit path establishing the selected itinerary, or itineraries, between departure and arrival nodes includes a circuit (FIG. 6) associated with each of said nodal elements and successively comprising a first AND gate (50) with two inputs; a first bistable trigger circuit (53); a second AND gate (56) with two inputs; a second bistable trigger circuit (57); and one of the inputs of said first and the second AND gates being connected to receive, at one of the their inputs (52, 55), each successively or simultaneously, an activation signal (U1, U2) respectively and another input of said first and second AND gates being connected in said circuit path to control propagation of a signal along said path.

Claim 18

System according to claim 4 wherein said nodal circuit elements (FIG. 3) and said link circuit elements (FIG. 4) each includes a controllable bistable circuit (25, 28) and a conjunctive logic circuit (26, 29) controlling the state of said bistable circuit in the respective circuit element, one of the inputs of the conjunctive logic circuit being connected to said clock pulse source and the other input being connected to the output from a connected circuit element and to said means applying an addressing signal.

Claim 19

System according to claim 16 wherein each said link elements has a time delay element (FIG. 5) associated therewith, said time delay element including a settable pulse counter (38- 43) connected to said clock pulse source (19) and delaying transmission of pulses by said link elements under control of the count setting of the pulse counter.

Claim 20

System according to claim 16 wherein each said circuit element has a pair of independent, parallel circuit paths, passing signals in opposite direction; and one of said independent circuit paths in the link circuit (FIG. 4) includes a control element (35) closing said independent circuit path under control of the state of said bistable circuit (28).