US5561790A — Shortest path determination processes for use in …

Claim 1

Independent Claim 192 words

A method of operating a modeling system, with the aid of a digital computer, to transform a first set of signals, including (a) signals representing a given linear network defined in terms of a set of node identifications signals, (b) a set of weighted/directed edge signals each of which identify the weight, direction and the pair of nodes in said network interconnected via a given edge, and (c) signals representing arbitrarily specified start and target nodes in said network, into a second set of signals indicating the shortest path in said network between said start and target nodes, comprising the steps of: (a) providing said computer with a database that includes at least said first set of signals, wherein said database is accessible by said computer to retrieve data during the transformation process; and (b) transforming with the aid of said computer said first set of signals into said second set of signals by incrementally creating an array of node identification signals through repeated direct reference to said first set of signals, all values of said first set of signals remaining constant during said incremental creation of said second set of signals.

Claim 2

Independent Claim 192 words

A method of operating a modeling system, with the aid of a digital computer, to transform a first set of signals, including (a) signals representing a given linear network defined in terms of a set of node identifications signals, (b) a set of weighted/directed edge signals each of which identify the weight, direction and the pair of nodes in said network interconnected via a given edge, and (c) signals representing arbitrarily specified start and target nodes in said network, into a second set of signals indicating the shortest path in said network between said start and target nodes, comprising the steps of: (a) providing said computer with a database that includes at least said first set of signals, wherein said database is accessible by said computer to retrieve data during the transformation process; and (b) transforming with the aid of said computer said first set of signals into said second set of signals by incrementally creating an array of node identification signals through repeated direct reference to said first set of signals, all values of said first set of signals remaining constant during said incremental creation of said second set of signals.

Claim 3

Dependent Claim 52 words

A method as set forth in claim 1 wherein said step of transforming further comprises the step of determining the information to be retrieved from said database, to construct a given incremental portion of said array, as a function of the contents of the array itself as the array is being created.

Claim 4

Dependent Claim 148 words

A method as set forth in claim 2 wherein each entry in said array of node identification signals comprises: (a) a first signal having a unique value for identifying a given node in said linear network; (b) a second signal for indicating if said given node is a permanent node; (c) a third signal representing the calculated shortest weight to said given node, calculated by said computer as a function of the variable contents of array as the array is being constructed; and (d) a fourth signal, for indicating the identity of a previously visited node in the path between the start node and the given node, which may be utilized to determine the shortest path from said target node back to said start node at the completion of the array creation process whenever said given node is in the shortest path between said start and target nodes.

Claim 5

Dependent Claim 30 words

A method as set forth in claim 3 wherein said step of transforming further comprises the step of maintaining the entries in said array as part of a binary tree.

Claim 6

Dependent Claim 35 words

A method as set forth in claim 4 wherein said step of transforming further comprises the step of sorting said binary tree based on the unique value of said first signal for a given node.

Claim 7

Dependent Claim 37 words

A method as set forth in claim 3 wherein the entries of said array which are not associated with permanent nodes, as indicated by said second signal for each array entry, are maintained in a linked list.

Claim 8

Dependent Claim 188 words

A method as set forth in claim 3 wherein said step of transforming, including the step of incrementally creating an array of node identification signals directly from said first set of signals, further comprises the steps of: (a) initializing said array with a first array entry for said start node, wherein the step of initializing further includes the step of labeling said start node as a permanent node utilizing the second signal in said first array entry; (b) adding a new entry to said array for each node that can be reached directly via an edge from the last node labeled permanent, so long as a corresponding array entry for the node that can be reached does not already exist; and (c) updating the third and fourth signals in a given array entry existing prior to performing said step of adding, corresponding to a given node that can be reached directly via an edge from the last node labeled permanent, whenever it is determined by said computer that the calculated shortest weight to the given node is less than a previously calculated shortest weight to the given node.

Claim 9

Dependent Claim 96 words

A method as set forth in claim 7 wherein said step of adding a new array entry further comprises the steps of: (a) determining the value of the first, third and fourth signals of each new array entry, with the aid of said computer, based on said set of weighted/directed edge signals provided to said computer via said database and based on the contents of the array entry associated with the last node labeled permanent; and (b) setting the second signal of each new array entry to indicate that the corresponding node is not labeled permanent.

Claim 10

Dependent Claim 77 words

A method as set forth in claim 8 further comprising the steps of: (a) determining if the nodes associated with all of the array entries are labeled as being permanent; (b) defining said second set of signals to be the empty set whenever the nodes associated with all the array entries are labeled as being permanent; and (c) terminating the array creation process whenever the nodes associated with all the array entries are labeled as being permanent.

Claim 11

Dependent Claim 123 words

A method as set forth in claim 9 further comprising the steps of: (a) determining which array entry has the smallest calculated weight, from the set of remaining array entries corresponding to nodes which have not been labeled permanently; (b) setting the second signal, of the array entry determined in step (a) to have the smallest calculated weight, to indicate that the node associated with the array entry is permanent; (c) determining if the node associated with the array entry for which the second signal was set, in step (b), is the target node; and (d) terminating the array creation process whenever the node associated with the array entry for which the second signal was set, in step (b), is the target node.

Claim 12

Dependent Claim 53 words

A method as set forth in claim 10 further comprising the step of repeating the aforestated process steps, beginning with said step of adding a new entry, so long as the array creating process is not terminated and at least one array entry exists for a node which have not been labeled permanent.

Claim 13

Dependent Claim 91 words

A method as set forth in claim 10 further comprising the steps of: (a) utilizing said computer to determine the shortest path from said target node back to said start node, at the completion of the array creation process, based on the set of fourth signals in said array; and (b) defining said second set of signals as the set of node identification signals which identify the nodes in the path determined in step (a), thereby completing the transformation of said first set of signals into said second set of signals.

Claim 14

Dependent Claim 53 words

A method as set forth in claim 10 wherein said step of determining which array entry has the smallest calculated weight is performed with the aid of said computer by comparing the values of the third signal for each of the array entries corresponding to the nodes which have not been labeled permanent.

Claim 15

Dependent Claim 78 words

A method as set forth in claim 7 wherein said step of initializing said array with a first array entry for said start node further comprises the step of setting the values of the first, third and fourth signals in said first array entry such that the first signal identifies the start node, said third signal indicates a calculated weight of zero, and said fourth signal indicates that the first array entry is the start node array entry.

Claim 16

Dependent Claim 17 words

A method as set forth in claim 1 wherein said modeling system is a geographical information system.

Claim 17

Dependent Claim 17 words

A method as set forth in claim 1 wherein said modeling system is a geographical positioning system.

Claim 18

Dependent Claim 18 words

A method as set forth in claim 1 wherein said modeling system is a computer aided design system.

Claim 19

Dependent Claim 18 words

A method as set forth in claim 1 wherein said modeling system is a computer aided manufacturing system.

Claim 20

Independent Claim 188 words

A method of operating a computer assisted communications network to transform a first set of signals, including (a) signals representing a given linear communications network defined in terms of a set of node identification signals, (b) a set of weighted/directed edge signals each of which identify the weight, direction and the pair of nodes in said network interconnected via a given edge, and (c) signals representing arbitrarily specified start and target nodes in said network, into a second set of signals indicating the shortest path in said network between said start and target nodes, comprising the steps of: (a) providing said computer with a database that includes at least said first set of signals, wherein said database is accessible by said computer to retrieve data during the transformation process; and (b) transforming with the aid of said computer said first set of signals into said second set of signals by incrementally creating an array of node identification signals through repeated direct reference to said first set of signals, all values of said first set of signals remaining constant during said incremental creation of said second set of signals.

Claim 21

Independent Claim 188 words

A method of operating a computer assisted communications network to transform a first set of signals, including (a) signals representing a given linear communications network defined in terms of a set of node identification signals, (b) a set of weighted/directed edge signals each of which identify the weight, direction and the pair of nodes in said network interconnected via a given edge, and (c) signals representing arbitrarily specified start and target nodes in said network, into a second set of signals indicating the shortest path in said network between said start and target nodes, comprising the steps of: (a) providing said computer with a database that includes at least said first set of signals, wherein said database is accessible by said computer to retrieve data during the transformation process; and (b) transforming with the aid of said computer said first set of signals into said second set of signals by incrementally creating an array of node identification signals through repeated direct reference to said first set of signals, all values of said first set of signals remaining constant during said incremental creation of said second set of signals.

Claim 22

Dependent Claim 51 words

A method as set forth in claim 19 wherein said of transforming further comprises the step of determining the information to be retrieved from said database, to construct a given incremental portion of said array, as a function of the contents of the array itself as the array is being created.

Claim 23

Dependent Claim 183 words

A computer assisted process for transforming a first set of signals, including (a) signals representing a given linear communications network defined in terms of a set of node identification signals, (b) a set of weighted/directed edge signals each of which identify the weight, direction and the pair of nodes in said network interconnected via a given edge, and (c) signals representing arbitrarily specified start and target nodes in said network, into a second set of signals indicating the shortest path in said network between said start and target nodes, comprising the steps of: (a) providing said computer with a database that includes at least said first set of signals, wherein said database is accessible by said computer to retrieve data during the transformation process; and (b) transforming with the aid of said computer said first set of signals into said second set of signals by incrementally creating an array of node identification signals through repeated direct reference to said first set of signals, all values of said first set of signals remaining constant during said incremental creation of said second set of signals.

Claim 24

Dependent Claim 183 words

A computer assisted process for transforming a first set of signals, including (a) signals representing a given linear communications network defined in terms of a set of node identification signals, (b) a set of weighted/directed edge signals each of which identify the weight, direction and the pair of nodes in said network interconnected via a given edge, and (c) signals representing arbitrarily specified start and target nodes in said network, into a second set of signals indicating the shortest path in said network between said start and target nodes, comprising the steps of: (a) providing said computer with a database that includes at least said first set of signals, wherein said database is accessible by said computer to retrieve data during the transformation process; and (b) transforming with the aid of said computer said first set of signals into said second set of signals by incrementally creating an array of node identification signals through repeated direct reference to said first set of signals, all values of said first set of signals remaining constant during said incremental creation of said second set of signals.

Claim 25

Dependent Claim 53 words

A method as set forth in claim 21 wherein said step of incrementally creating further comprises the step of determining the information to be retrieved from said database, to construct a given incremental portion of said array, as a function of the contents of the array itself as the array is being created.

Claim 26

Dependent Claim 48 words

A method as set forth in claim 22 further comprising the step of utilizing said computer assisted process in a computer aided modeling system, including a predefined modeling coordinate system, to determine the shortest path between two nodes in a linear network defined in said modeling coordinate system.

Claim 27

Dependent Claim 35 words

A method as set forth in claim 22 further comprising the step of utilizing said computer assisted process in a computer aided communications network to determine the shortest path between two nodes in said network.

Claim 28

Dependent Claim 148 words

A method as set forth in claim 22 wherein each entry in said array of node identification signals comprises: (a) a first signal having a unique value for identifying a given node in said linear network; (b) a second signal for indicating if said given node is a permanent node; (c) a third signal representing the calculated shortest weight to said given node, calculated by said computer as a function of the variable contents of array as the array is being constructed; and (d) a fourth signal, for indicating the identity of a previously visited node in the path between the start node and the given node, which may be utilized to determine the shortest path from said target node back to said start node at the completion of the array creation process whenever said given node is in the shortest path between said start and target nodes.

Claim 29

Dependent Claim 31 words

A method as set forth in claim 25 wherein said step of incrementally creating further comprises the step of maintaining the entries in said array as part of a binary tree.

Claim 30

Dependent Claim 36 words

A method as set forth in claim 26 wherein said step of incrementally creating further comprises the step of sorting said binary tree based on the unique value of said first signal for a given node.

Claim 31

Dependent Claim 37 words

A method as set forth in claim 25 wherein the entries of said array which are not associated with permanent nodes, as indicated by said second signal for each array entry, are maintained in a linked list.

Claim 32

Dependent Claim 183 words

A method as set forth in claim 25 wherein said step of incrementally creating an array of node identification signals directly from said first set of signals, further comprises the steps of: (a) initializing said array with a first array entry for said start node, wherein the step of initializing further includes the step of labeling said start node as a permanent node utilizing the second signal in said first array entry; (b) adding a now entry to said array fox each node that can be reached directly via an edge from the last node labeled permanent, so long as a corresponding array entry for the node that can be reached does not already exist; and (c) updating the third and fourth signals in a given array entry existing prior to performing said step of adding, corresponding to a given node that can be reached directly via an edge from the last node labeled permanent, whenever it is determined by said computer that the calculated shortest weight to the given node is less than a previously calculated shortest weight to the given node.

Claim 33

Dependent Claim 96 words

A method as set forth in claim 29 wherein said step of adding a new array entry further comprises the steps of: (a) determining tile value of the first, third and fourth signals of each new array entry, with the aid of said computer, based on said set of weighted/directed edge signals provided to said computer via said database and based on the contents of the array entry associated with the last node labeled permanent; and (b) setting the second signal of each new array entry to indicate that the corresponding node is not labeled permanent.

Claim 34

Dependent Claim 77 words

A method as set forth in claim 30 further comprising the steps of: (a) determining if the nodes associated with all of the array entries are labeled as being permanent; (b) defining said second set of signals to be the empty set whenever the nodes associated with all the array entries are labeled as being permanent; and (c) terminating the array creation process whenever the nodes associated with all the array entries are labeled as being permanent.

Claim 35

Dependent Claim 123 words

A method as set forth in claim 31 further comprising the steps of: (a) determining which array entry has the smallest calculated weight, from the set of remaining array entries corresponding to nodes which have not been labeled permanently; (b) setting the second signal, of the array entry determined in step (a) to have the smallest calculated weight, to indicate that the node associated with the array entry is permanent; (c) determining if the node associated with the array entry for which the second signal was set, in step (b), is the target node; and (d) terminating the array creation process whenever the node associated with the array entry for which the second signal was set, in step (b), is the target node.

Claim 36

Dependent Claim 53 words

A method as set forth in claim 32 further comprising the step of repeating the aforestated process steps, beginning with said step of adding a new entry, so long as the array creating process is not terminated and at least one array entry exists for a node which have not been labeled permanent.

Claim 37

Dependent Claim 91 words

A method as set forth in claim 32 further comprising the steps of: (a) utilizing said computer to determine the shortest path from said target node back to said start node, at the completion of the array creation process, based on the set of fourth signals in said array; and (b) defining said second set of signals as the set of node identification signals which identify the nodes in the path determined in step (a), thereby completing the transformation of said first set of signals into said second set of signals.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1999-10-01	2000-04-01	2000-10-01	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2003-10-01	2004-04-01	2004-10-01	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2007-10-01	2008-04-01	2008-10-01	$7700.00	Window Closed / Lapsed

Shortest path determination processes for use in modeling systems and communications networks

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag