Method and system that determine whether or not two graph-like representations of two systems describe equivalent systems

Patent metadata

Field	Value
Publication number	US-2016110434-A1
Application number	US-201414517710-A
Country	US
Kind code	A1
Filing date	Oct 17, 2014
Priority date	Oct 17, 2014
Publication date	Apr 21, 2016
Grant date	—

Abstract

The current document is directed to methods and systems that determine whether or not two graph-like representations of two physically or temporally distinct computer systems or computer-system configurations are equivalent. The currently described methods and systems extract a first and second ordered set of subgraphs from each of a first and second graph-like representation of a first and a second computer system. The ordered sets of subgraphs are logically aligned, forming a set of subgraph pairs. The currently described methods and systems transform the first and second subgraph of each subgraph pair into a corresponding first and second set of trees, label the trees, and then compare labels at each level of the trees to determine whether or not an isomorphic tree can be found in the second set of trees for each tree in the first set of trees.

First claim

1 . An administration-and-management component of a computer system comprising:
one or more processors; one or more memories; one or more graph databases; and computer instructions stored in the one or more memories that, when executed by one or more of the one or more processors, control the computer-system administration-and-management component, on behalf of a calling computational entity, to
store a first graph and a second graph that each represents a computer system in one or more of the one or more graph databases, and
determine whether or not the first and second graphs are equivalent by
extracting two or more sets of subgraphs from each of the first and second graphs, each set of subgraphs extracted from the first graph corresponding to a complementary set of subgraphs extracted from the second graph,
transforming the subgraphs in the sets of subgraphs into trees within corresponding sets of trees,
labeling nodes of the trees in the corresponding sets of trees,
comparing labels at each level of trees selected from the sets of trees to generate a return value stored in one of the one or more memories, and
returning the generated return value to the calling computational entity.

2 . The administration-and-management component of claim 1 wherein each of the first and second graphs comprises:
a set of nodes that represent computer system components and subsystems; and
a set of edges that represent relationships between pairs of nodes.

3 . The administration-and-management component of claim 2 wherein the nodes and edges are associated with attribute/attribute-value pairs.

4 . The administration-and-management component of claim 1 wherein extracting a first set of subgraphs from the first graph and a complementary second set of subgraphs from the second graph further comprises:
receiving a connections set that specifies types of edges to extract, along with types of nodes connected by the edges;
determining a root-node type for the subgraphs of the first and second sets;
for each of the first and second graphs,
for each unextracted node of the determined root-node type within the graph, extracting the as yet unextracted node and a subgraph containing edges of the specified types of edges connected directly or indirectly to the extracted node.

5 . The administration-and-management component of claim 4 wherein the connections set includes specifications of one or more relationships, selected from among one-to-many and many-to-many relationships, between types of nodes of the first and second graphs.

6 . The administration-and-management component of claim 1 wherein transforming a subgraph in a set of subgraphs into one or more trees within a corresponding set of trees comprises:
removing edge of a type included in a set of selected redundant edge types from the subgraph; and
for each node in the subgraph with multiple incoming edges, duplicating the node and its progeny to remove a cycle within the subgraph.

7 . The administration-and-management component of claim 1 wherein labeling nodes of a tree comprises:
for each level of modes in the tree, starting with the a level of nodes directly above the leaf nodes,
for each node in the level of the tree,
assigning a label to the node that describes the quantity and type of progeny nodes of the node.

8 . The administration-and-management component of claim 7 wherein the label assigned to a node includes, for each level of progeny nodes below the node and for each type of node at the level, an indication of a number of nodes at the level associated with an indication of a node type.

9 . The administration-and-management component of claim 7 wherein the label assigned to a node includes one or more attribute values selected from attribute values associated with the node and with edges outgoing from, and incoming to, the node.

10 . The administration-and-management component of claim 1 wherein comparing labels at each level of trees selected from the sets of trees further includes:
for each set of trees transformed from a set of subgraphs extracted from the first graph,
when, for a tree in the set of trees, a matching tree cannot be identified in the set of trees transformed from a complementary set of subgraphs extracted from the second graph by comparing labels at each level of the tree and the matching tree above a leaf-node level, generating a return value indicating that the first and second graphs are not equivalent; and

when, for each tree in each set of trees transformed from a set of subgraphs extracted from the first graph, a matching tree is identified in a corresponding set of trees transformed from a complementary set of subgraphs extracted from the second graph, generating a return value indicating that the first and second graphs are equivalent.

11 . The administration-and-management component of claim 10 wherein a tree in a first set of trees matches a tree in a corresponding second set of trees when, at each level of the trees above the leaf-node level, a unique, equivalent node is identified at the level in the second tree for each node at the level in the first tree.

12 . The administration-and-management component of claim 11 wherein a first node is equivalent to a second node when a label associated with the first node is equivalent to the label associated with the second node.

13 . The administration-and-management component of claim 1 wherein, in addition to generating a return value stored in one of the one or more memories, comparing labels at each level of trees selected from the sets of trees also generates a set of differences between the the first and second graphs.

14 . A method, carried out by a computer system having one or more processors, one or more memories, one or more graph databases, and computer instructions stored in the one or more memories that, when executed by one or more of the one or more processors, control the computer system to determine whether a first graph is equivalent to a second graph by:
storing the first graph and the second graph in one or more of the one or more graph databases, and determining whether or not the first and second graphs are equivalent by
extracting two or more sets of subgraphs from each of the first and second graphs, each set of subgraphs extracted from the first graph corresponding to a complementary set of subgraphs extracted from the second graph,
transforming the subgraphs in the sets of subgraphs into trees within corresponding sets of trees,
labeling nodes of the trees in the corresponding sets of trees, and
comparing node labels of trees selected from the sets of trees to generate a return value stored in one of the one or more memories that indicates whether or not the first and second graphs are equivalent.

15 . The method of claim 14 wherein each of the first and second graphs comprises:
a set of nodes associated with attribute/attribute-value pairs; and
s set of edges associated with attribute/attribute-value pairs.

16 . The method of claim 14 wherein extracting a first set of subgraphs from the first graph and a complementary second set of subgraphs from the second graph further comprises:
receiving a connections set that specifies types of edges to extract, along with types of nodes connected by the edges;
determining a root-node type for the subgraphs of the first and second sets;
for each of the first and second graphs,
for each unextracted node of the determined root-node type within the graph, extracting the as yet unextracted node and a subgraph containing edges of the spec

Assignees

• Vmware Inc

Inventors

• Kakaraddi Shishir Mahesh
• Soundararajan Ravi

Classifications

• G06F11/202

  where processing functionality is redundant (redundant communication control functionality G06F11/2005, redundant storage control functionality G06F11/2089) · CPC title

• G06F11/3452

  Performance evaluation by statistical analysis · CPC title

• G06F2201/815

  Virtual · CPC title

• G06F16/9024 Primary

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F11/3604

  Analysis of software for verifying properties of programs (testing of software G06F11/3668) · CPC title