Techniques for graph data structure management

• US 20040249781A1
• Filed: 06/03/2003
• Published: 12/09/2004
• Est. Priority Date: 06/03/2003
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Anderson, Eric
• Granted Patent: US 8,250,107 B2
• Time in Patent Office: Days
• US Class Current: 707/1
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

Techniques for graph data structure management. In one aspect, a data structure includes a plurality of nodes connected by edges. A node of the data structure includes a current set of variables for defining a state of the node and at least one last-in, first-out stack for storing pointers to prior sets of variables for the node. The state of the node may be saved by adding a pointer to at least one of the stacks at the node. The state of the node may be restored by removing the pointer from the stack and restoring the node variables to those indicated by the pointer. A first counter associated with a stack at the node may store a number of pending saves at the node, while a second counter may store a number of saves to be propagated to descendents of the node. A state of the data structure may be saved by traversing other nodes of the data structure and adding pointers or incrementing counters at the nodes.

Claims

1. A data structure having a plurality of nodes, wherein each node includes a current set of variables for defining a state of the node and at least one last-in, first-out stack for storing pointers to prior sets of variables for the node and wherein the state of the data structure is defined by the states of the nodes.

2. The data structure according to claim 1, wherein each node further comprises a first counter associated with each stack, wherein the first counter stores a number of pending saves at the node.

3. The data structure according to claim 2, wherein the pending saves are instantiated by a number of pointers added to the corresponding stack.

4. The data structure according to claim 2, wherein a state of at least a portion of the data structure is saved by a traversal of nodes in the data structure and wherein the first counter for a stack is incremented when the node is traversed.

5. The data structure according to claim 4, wherein a state of at least a portion of the data structure is restored by a traversal of nodes in the data structure and wherein the first counter for a stack is decremented if non-zero and, otherwise, a pointer is removed from the stack and the node variables are restored to those indicated by the pointer.

6. The data structure according to claim 4, wherein a state of at least a portion of the data structure is discarded by a traversal of nodes in the data structure and wherein the first counter for the stack is decremented if it is non-zero and, otherwise, a pointer is removed from the stack and discarded.

7. The data structure according to claim 2, wherein nodes of the data structure further comprise a flag for indicating whether the node has been traversed.

8. The data structure according to claim 2, wherein at least some of the nodes have descendent nodes and include a second counter associated with each stack, wherein the second counter stores a number of saves to be propagated to descendents of the node.

9. The data structure according to claim 8, wherein the saves to be propagated are propagated by the first counter for a stack at the node being incremented and by the second counter for the stack at descendents of the node being incremented.

10. The data structure according to claim 8, wherein a state of at least a portion of the data structure is restored by decrementing the second counter for the stack for a node.

11. The data structure according to claim 8, wherein a state of at least a portion of the data structure is discarded by decrementing the second counter for the stack for a node.

12. The data structure according to claim 1, wherein at least some of the nodes have descendent nodes and include a counter associated with each stack, wherein the counter stores a number of saves to be propagated to descendents of the node.

13. A method for saving a state of a node in a data structure having a plurality of nodes, wherein the node includes a current set of variables for defining a state of the node, at least one last-in, first-out stack for storing pointers to prior sets of variables for the node, the method comprising adding a pointer to at least one of the stacks.

14. The method according to claim 13, further comprising restoring the state of the node by removing the pointer from the stack and restoring the node variables to those indicated by the pointer.

15. The method according to claim 13, further comprising discarding the state of the node by removing the pointer from the stack and discarding the pointer.

16. The method according to claim 13, further comprising saving a state of at least a portion of the data structure by traversing at least some other nodes of the data structure and, at each of the other nodes, adding a pointer to at least one stack at the node.

17. The method according to claim 13, further comprising incrementing a first counter associated with a stack at the node wherein the first counter stores a number of pending saves at the node.

18. The method according to claim 17, further comprising restoring the state of the node by decrementing the first counter for the stack if it is non-zero and, otherwise, removing a pointer from the stack and restoring the node variables to those indicated by the pointer.

19. The method according to claim 17, further comprising instantiating the pending saves by adding a number of pointers to the stack wherein the number of pointers corresponds to the number of pending saves.

20. The method according to claim 17, further comprising saving a state of at least a portion of the data structure by traversing some other nodes of the data structure and, at each of the other nodes, incrementing a first counter for a stack at the node.

21. The method according to claim 20, further comprising restoring the state of the at least a portion of the data structure by traversing some other nodes in the data structure and, at each of the other nodes, decrementing the first counter for a stack is if it is non-zero and, otherwise, removing a pointer from the stack and restoring the node variables to those indicated by the pointer.

22. The method according to claim 20, further comprising discarding the state of at least a portion of the data structure by traversing some other nodes in the data structure and, at each of the other nodes, decrementing the first counter for a stack is if it is non-zero and, otherwise, removing a pointer from the stack and discarding the pointer.

23. The method according to claim 20, wherein nodes of the data structure include an indicator of whether the node has been traversed.

24. The method according to claim 14, further comprising incrementing a second counter associated with a stack at the node wherein the second counter stores a number of saves to be propagated to descendents of the node.

25. The method according to claim 24, further comprising propagating saves to descendents of the node by incrementing a second counter for the stack at a next generation of descendents of the node and decrementing the second counter for the stack at the node.

26. The method according to claim 25, wherein said propagating saves to descendents of the node further comprises incrementing the first counter for the stack at the node.

27. The method according to claim 25, wherein said propagating saves to descendents of the node is performed prior to changing variables of a node in the data structure.

28. The method according to claim 13, wherein nodes of the data structure include an indicator of whether descendents of the node include two or more parents of any child node.

29. The method according to claim 13, wherein nodes of the data structure include an indicator of whether descendents of the node are only reachable via the node.

30. The method according to claim 13, further comprising incrementing a counter associated with a stack at the node wherein the counter stores a number of saves to be propagated to descendents of the node.

31. A method for saving a data structure state, the data structure having a plurality of nodes, wherein each node includes a current set of variables for defining a state of the node, at least one last-in, first-out stack for storing pointers to prior sets of variables for the node and a counter associated with each stack, the method comprising traversing the data structure and, at each node, incrementing the counter.

32. The method according to claim 31, further comprising traversing the data structure and, at each node, decrementing the counter if the counter is non-zero and, otherwise, removing a pointer from the stack and restoring the set of variables to those indicated by the pointer.

33. A method for restoring a data structure state, the data structure having a plurality of nodes, wherein each node includes a current set of variables for defining a state of the node, at least one last-in, first-out stack for storing pointers to prior sets of variables for the node and a counter associated with each stack, the method comprising traversing the data structure and, at each node, decrementing the counter if the counter is non-zero and, otherwise, removing a pointer from the stack and restoring the set of variables to those indicated by the pointer.

34. A method for discarding a data structure state, the data structure having a plurality of nodes connected by edges, wherein each node includes a current set of variables for defining a state of the node, at least one last-in, first-out stack for storing pointers to prior sets of variables for the node and a counter associated with each stack, the method comprising traversing the data structure and, at each node, decrementing the counter if the counter is non-zero and, otherwise, removing a pointer from the stack and discarding the pointer.

35. A program storage medium readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for saving a data structure state, the data structure having a plurality of nodes, wherein each node includes a current set of variables for defining a state of the node, at least one last-in, first-out stack for storing pointers to prior sets of variables for the node and a counter associated with each stack, said method steps including traversing the data structure and, at each node, incrementing the counter.

36. The program storage medium according to claim 35, said method steps further comprising traversing the data structure and, at each node, decrementing the counter if the counter is non-zero and, otherwise, removing a pointer from the stack and restoring the set of variables to those indicated by the pointer.