Traversing a cyclic graph using a modified breadth-first search in complex modeling
A method determines an order of calculation for one or more of a set of variables in the complex system, so that the calculation order is substantially optimal for avoiding having to skip calculations due to lack of precursors. The method reviews the complex model and orders calculations in a list, so that variables depending on precursors are ordered later, so that their calculation need not be skipped. The method determines a threshold (which can be a single pass), and when the threshold is exceeded, reorders the calculation, so that optimality of calculation can be improved. The method can reorder the calculation so that the new order of calculation is substantially a reverse of the original.
1. A method including, at a processor:
collecting a system model into a memory, the system model including inputs, variables, values that the variables can have, and rules, each rule specifying one or more of a computation to be performed and a conditional statement to be evaluated in response to the variables;
providing a directed graph including both leaf nodes and root nodes, each leaf
node specifying one or more of an input or a parameter of the model, and each root node specifying rules and variables whose values are operated upon by the root nodes, with edges of the directed graph representing a driver relationship such that a driver node is a node whose output is used by another node;
disposing the root nodes in a first list; and
transferring the root nodes from the first list onto an order-of-performance list which is ordered in an order in which the root nodes are to be performed comprising:
(a) when a first root node on the first list does not have itself as a driver, allocating a corresponding queue for the root node and moving that root node to the corresponding queue;
(b) when the first root node on the first list has itself as a driver, moving that first root node to one or more of a last position on the first list or a self-linking queue;
(c) when the corresponding queue is not empty, and a first node in that queue has nodes with all of its drivers already on the order-of-performance list, moving that first node to a last position on that order-of-performance list; and
(d) when a queue is not empty, and the first node in that queue has nodes with one or more of its driver nodes not yet on the order-of-performance list, moving that first node to a last position on its queue, and moving one or more driver nodes for that first node onto that queue, so long as those driver nodes are not themselves root nodes;
outputting the order-of-performance list which is ordered in an order in which the root nodes are to be performed.
2. The method as in claim 1 , including the steps of:
presenting a representation of the graph to a user, the representation including one or more of a display of nodes associated with the rules and a display of links showing direction of changes from input to output;
receiving instructions from the user, those instructions from the user including one or more of zooming in for a more detailed view of the model and zooming out for a more global view of the model.
3. The method as in claim 2 , including, when the only nodes not yet on the order-of-performance list are either on the self-linking queue or have drivers thereon, requesting assistance from the user and responding thereto.
4. The method as in claim 1 , including repeating the steps of transferring root nodes from the first list onto the order-of-performance list until all nodes are on the order-of-performance list.
5. The method as in claim 1 , including the steps of:
when the steps of transferring root nodes from the first list onto the order-of-performance list have been performed at least a specified number of times, reversing the first list; and
performing the steps of transferring root nodes from the first list onto the order-of-performance list after the steps of reversing.
6. The method as in claim 5 , including the steps of performing those steps of reversing the first list and re-performing the steps of transferring root nodes a plurality of times.
7. The method as in claim 6 , wherein that plurality of times is no more than a specified threshold.
8. The method as in claim 5 , wherein the specified number of times is once.
9. The method as in claim 1 , including the steps of:
when the steps of transferring root nodes from the first list onto the order-of-performance list have been performed at least a specified number of times, performing a reordering transform on the first list whereby one or more dependencies on said first list are reduced with high probability; and
performing the steps of transferring root nodes from the first list after performing the reordering transform.
10. The method as in claim 2 , wherein presenting the representation further includes one or more of aggregating nodes collected into single nodes and aggregating links collected into single links.
11. The method as in claim 1 , wherein the first list is sorted in an order in which the root nodes are to be performed.
12. The method as in claim 1 , wherein the model's rules include one or more of calculating one or more output values or variables in response to one or more input values or variables, comparing one or more input values or variables with a threshold value or variable, and conditionally performing an operation.
13. The method as in claim 1 , wherein, when the only nodes not yet on the order-of-performance list are either on the self-linking queue or have drivers thereon, moving a first root node from the self-linking queue to the order-of-performance list and continuing the steps of transferring root nodes from the first list.
14. The method as in claim 1 , wherein when the steps of transferring root nodes from the first list have no nodes to move to the order-of-performance list, the only nodes not yet on the order-of-performance list are either on the self-linking queue or have drivers thereon.