Directed non-cyclic graph walking system for data processing and analysis in software application

• US 7,263,694 B2
• Filed: 10/26/2001
• Issued: 08/28/2007
• Est. Priority Date: 10/26/2001
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Clewis, Fred T., Sitze, Richard A.
• Primary Examiner(s): Zhen; Wei
• Assistant Examiner(s): RAMPURIA, SATISH
• Application Number:
  US10/038,136
• Publication Number:
  US 20030084061A1
• Time in Patent Office: 2,132 Days
• Field of Search: 717/138, 717145-161, 717/102, 707/5, 707/102, 707/203, 709/225, 704/244, 704/254
• US Class Current: 717/156
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

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.

Claims

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.