Directed non-cyclic graph walking system for data processing and analysis in software application
View Patent ↗A system and method for efficiently walking a directed non-cyclic graph of hierarchical data using multiple analysis tools. The graph walking system comprises: a system for binding a plurality of graph observers to a graph, wherein each graph observer is further bound to a set of node patterns and a set of node observers; graph walking logic for systematically walking through nodes within the graph, wherein the graph walking logic can be instructed by a first pruning system not to walk a set of sub-nodes of an encountered node; and a second pruning system that can be instructed by a node observer bound with an associated graph observer to deactivate the associated graph observer until the set of sub-nodes for the encountered node has been walked. The first pruning system will cause the set of sub-nodes not to be walked only if all of the plurality of graph observers have been deactivated.
1. A computer implemented graph walking system, comprising:
a processor; and
a memory, including a program executable by the processor, the program including:
a binding system to bind a graph observer to find matching node patterns with a directed non-cyclic graph, to bind node patterns that identify distinguishing node attributes of data of a node to node observers that at least one of analyze and process a particular node to generate at least one node pairing, and to bind the graph observer to at least one node pattern-node observer pairing;
graph walking logic to systematically walk through nodes within the directed non-cyclic graph;
a pattern testing system to determine if an attribute of an encountered node matches one of the node patterns;
an event manager to generate an encountered event when one of the node observers is bound to a matching node pattern; and
a pruning system to deactivate the graph observer with respect to sub-nodes of the encountered node without deleting the sub-nodes if a bound node observer determines that there is no interest in the sub-nodes.
2. The graph walking system of claim 1 , wherein the encountered event is handled by the bound node observer.
3. The graph walking system of claim 1 , wherein the graph walking logic walks through the graph in a top down hierarchal manner.
4. The graph walking system of claim 1 , wherein the pruning system reactivates a deactivated graph observer after the sub-nodes of the encountered node have been walked.
5. The graph walking system of claim 1 , wherein the event manager generates a completed event for each node observer that received an encountered event and that did not cause the graph observer to become deactivated.
6. The graph walking system of claim 5 , wherein the completed event causes the graph walking logic to repeat the walk through the sub-nodes.
7. The graph walking system of claim 1 , wherein the pruning system further causes the graph walking logic to bypass walking of the sub-nodes if the graph observer has been deactivated and no other active graph observers exist.
8. A computer implemented system for analyzing a directed non-cyclic graph of hierarchical data, comprising:
a processor; and
a memory, including a program executable by the processor, the program including:
a system to bind a plurality of graph observers to find matching node patterns to a directed non-cyclic graph, wherein each graph observer is further bound to a set of node patterns that identify distinguishing node attributes of data of a node and a set of node observers that at least one of analyze and process a particular node;
graph walking logic to systematically walk through nodes within the graph;
a first pruning system that is instructed by a node observer bound with an associated graph observer to deactivate the associated graph observer until a set of sub-nodes for the encountered node has been walked; and
a second pruning system that instructs the graph walking logic not to walk the set of sub-nodes for the encountered node without deleting the set of sub-nodes.
9. The system of claim 8 , wherein the second pruning system causes the set of sub-nodes not to be walked only if all of the plurality of graph observers have been deactivated.
10. The system of claim 8 , further comprising a pattern testing system for determining if the encountered node matches one of the node patterns.
11. The system of claim 8 , further comprising an event manager for generating an encountered event when one of the node observers is bound to a matching node pattern.
12. A computer implemented method for analyzing a directed non-cyclic graph of hierarchical data, comprising the steps of:
binding a plurality of graph observers to find matching node patterns to a directed non-cyclic graph, wherein each graph observer is further bound to a set of node patterns that identify distinguishing node attributes of dataof a node and a set of node observers that at least one of analyze and process a particular node;
systematically walking through nodes within the graph;
generating an encounter event and handling the encounter event with a bound node observer when one of the node patterns matches an attribute of an encountered node;
deactivating the graph observer associated with the bound node observer if the bound node observer determines that a set of sub-nodes of the encountered node is to be pruned; and
bypassing the walking of the set of sub-nodes without deleting the set of sub-nodes if all of the plurality of graph observers have been deactivated.
13. The method of claim 12 , comprising the further step of generating a completed event for each node observer that received an encountered event and that did not cause the graph observer to become deactivated.
14. The method of claim 12 , comprising the further step of reactivating the graph observer associated with the bound node observer after the set of sub-nodes of the encountered node have been walked.
15. The method of claim 12 , comprising the further step of reactivating the graph observer associated with the bound node observer after set of sub-nodes of the encountered node have been bypassed.
16. The method of claim 12 , comprising the further step of walking the sub-nodes if at least one graph observer is active.
17. A computer program product stored on a recordable medium, which when executed, analyzes a directed non-cyclical graph of hierarchical data, the program product comprising:
program code configured to bind a plurality of tree observers to find matching node patterns to a graph, wherein each graph observer is further bound to a set of node patterns that identify distinguishing node attributes of data of a node and a set of node observers that at least one of analyze and process a particular node;
program code configured to provide graph walking logic for systematically walking through nodes within the graph;
program code configured to provide a first pruning system that is instructed by a node observer bound with an associated graph observer to deactivate the associated graph observer until a set of sub-nodes for an encountered node has been walked; and
program code configured to provide a second pruning system that instructs the graph walking logic not to walk the set of sub-nodes for the encountered node without deleting the set of sub-nodes.
18. The program product claim 17 , wherein the second pruning system causes the set of sub-nodes not to be walked only if all of the plurality of graph observers have been deactivated.
19. The program product claim 17 , further comprising program code configured to provide a pattern testing system for determining if the encountered node matches one of the node patterns.
20. The program product claim 17 , further comprising program code configured to provide an event manager for generating an encountered event when one of the node observers is bound to a matching node pattern.