GRAPH TRANSFORMATION

• US 20110231418A1
• Filed: 03/18/2010
• Published: 09/22/2011
• Est. Priority Date: 03/18/2010
• Status: Active Grant

• Current Assignee: Micro Focus LLC (Open Text Corporation)
• Original Assignee: Micro Focus LLC (Open Text Corporation)
• Inventors: Arshavsky, Vadim, Ben-Dor, Uri, BIRON, Ran
• Granted Patent: US 10,909,733 B2
• Time in Patent Office: Days
• US Class Current: 707/756
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs

Abstract

Systems, methods, and other embodiments associated with graph transformation are described. One example method includes transforming a base graph into a folded graph as a function of a folding query.

Claims

1. A computer-readable medium storing computer-executable instructions that when executed by a computer cause the computer to perform a method, the method comprising:

transforming a base graph into a folded graph as a function of a folding query, where the folding query describes an edge to add to the folded graph when a pre-specified sub-graph is detected in the base graph; and

providing the folded graph.

2. The computer-readable medium of claim 1, the method comprising:

executing a base query on a stored graph to identify the base graph.

3. The computer-readable medium of claim 2, where identifying the base graph comprises creating a copy of a portion of the stored graph.

4. The computer-readable medium of claim 2, where the stored graph resides in a configuration management database, where nodes in the stored graph represent elements of an information technology (IT) infrastructure, and where edges in the graph represent relationships between the elements of the IT infrastructure.

5. The computer-readable medium of claim 2, the method comprising generating the folding query based on a folding definition that describes a desired hierarchy of an output graph.

6. The computer-readable medium of claim 5, where generating the folding query comprises:

creating nodes in the folding query for placeholder nodes found while traversing a definition tree in the folding definition; and

adding edges linking nodes in the folding query based on relationships in the definition tree as a function of anchoring rules associated with placeholder nodes in the definition tree.

7. The computer-readable medium of claim 5, the method comprising receiving the base query and the folding definition from a client, where the folded graph is provided to the client, and where the client uses the folded graph to generate the output graph based, at least in part, on the folding definition.

8. The computer-readable medium of claim 5, where the output graph is a tree.

9. The computer-readable medium of claim 5, where the folded graph comprises nodes found in the base graph and edges derived from relationships between placeholder nodes in the folding definition.

10. The computer-readable medium of claim 9, where transforming the base graph into the folded graph comprises placing a directed edge in the folded graph, where the directed edge is directed from a first node in the folded graph to a second node in the folded graph, and where the directed edge is placed in response to detecting an edge connecting a third node in the base graph and a fourth node in the base graph, where the third node and the fourth node are specified by placeholder nodes in the folding definition, where the first node is associated with the third node, and where the second node is associated with the fourth node.

11. The computer-readable medium of claim 9, where transforming the base graph into the folded graph comprises placing a directed edge in the folded graph, where the directed edge is directed from a first node in the folded graph to a second node in the folded graph, and where the directed edge is placed in response to detecting a compound edge connecting a third node in the base graph and a fourth node in the base graph, where the third node and the fourth node are specified by placeholder nodes in the folding definition, where the first node is associated with the third node, where the second node is associated with the fourth node, and where a compound edge is a series of edges connecting the third node and the fourth node through at least one intermediary node.

12. A system, comprising:

a configuration management data store (CMDB) to store descriptions of components of an information technology (IT) infrastructure and to store a directed graph describing relationships between the components of the IT infrastructure;

a topological query logic to select a sub-graph of the directed graph in response to a topological query; and

a folding logic to transform the sub-graph of the directed graph into a folded sub-graph based on information describing a desired display output.

13. The system of claim 12, comprising a provision logic to provide the folded sub-graph to a client that generates a view of a portion of the IT infrastructure as a function of the folded sub-graph.

14. The system of claim 12, comprising a receipt logic to receive the topological query and the information describing the desired display output from the client in response to a user input, and where the information describing the desired display output describes a hierarchy of information to be displayed in the view.

15. A system, comprising:

means for searching a graph for a pre-specified sub-graph; and

means for transforming the pre-specified sub-graph into a folded sub-graph.

16. The system of claim 15, where the pre-specified sub-graph is transformed according to a folding query.

17. The system of claim 16, comprising means for generating the folding query.

18. The system of claim 16, comprising means for generating the folding query as a function of a folding definition.

19. The system of claim 15, comprising means for providing the folded sub-graph to a client for creating a view of the pre-specified sub-graph.

20. The system of claim 15, where the means for transforming is configured to place a directed edge from a first node in the folded sub-graph to a second node in the folded sub-graph, where the directed edge is placed in response to detecting an edge connecting a third node in the pre-specified sub-graph and a fourth node in the pre-specified sub-graph.