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

• US 5,561,790 A
• Filed: 06/07/1995
• Issued: 10/01/1996
• Est. Priority Date: 03/24/1992
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Fusaro, William E.
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): MOHAMED, AYNI Y
• Application Number:
  US08/472,162
• Time in Patent Office: 482 Days
• Field of Search: 395/500, 395/200, 395/600, 364/578, 364/488-491
• US Class Current: 703/26
• CPC Class Codes: G06F 30/18 Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04Q 3/665 Circuit arrangements therefor

Abstract

Methods for operating a modeling system and/or a communications network, using a computer assisted process, are described, which transform a first set of signals, including (a) signals representing a given linear 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 the network interconnected via a given edge, and (c) signals representing arbitrarily specified start and target nodes in the network, into a second set of signals indicating the shortest path in the network between the start and target nodes. The processes contemplated by the invention perform the aforementioned transformation by incrementally creating an array of node identification signals directly from the first set of signals. No starting matrix (or sparse matrix), as required by prior art processes, needs to be created or stored. Furthermore, the processes contemplated by the invention build the array as a function of array contents (as the array is being incrementally created). As a result of these features, it is not necessary to visit every node in the network to determine the shortest path between two nodes, and the shortest path determination can be made in a manner which conserves computing resources.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

7. 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.

8. 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.

9. 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.

10. 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.

11. 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.

12. 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.

13. 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.

14. 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.

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

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

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

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

19. 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.

20. 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.

21. 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.

22. 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.

23. 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.

24. 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.

25. 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.

26. 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.

27. 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.

28. 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.

29. 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.

30. 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.

31. 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.

32. 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.

33. 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.

34. 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.