Method and apparatus for determining compatible versions of dependent entities in a computer system
First Claim
Patent Images
1. A computer executed method of determining compatible versions of dependent entities of a root entity having a specified version in a computer system, the method comprising:
- building a directed graph comprising the dependent entities;
dividing the directed graph into multiple levels;
determining which level of the multiple levels each dependent entity belongs to;
dividing each level into one or more isolated subsets; and
determining compatible versions for all entities in upper levels of the directed graph before determining compatible versions for any entity in lower levels of the directed graph;
wherein building the directed graph comprises;
representing the entities by nodes and dependency relationships between the entities by edges; and
putting a directed edge from a first node to a second node which is dependent on the first node and referring to the first node as a parent node and the second node as a child node;
wherein the directed graph is divided into levels in such a way that no node of a given level is dependent on a node of a lower level; and
wherein dividing the directed graph into multiple levels comprises;
putting a root node representing the root entity in a first level of the directed graph and all of said root node'"'"'s child nodes into a new level and then for each level of the directed graph;
a. including in the current level all nodes which are interdependent directly or indirectly with the nodes already included in the current level;
b. pushing into a next level of the directed graph all those nodes from the current level that are dependent on nodes which have not yet been assigned to a level; and
c. putting all the child nodes of parent nodes in the current level into the next level of the directed graph if said child nodes have not already assigned to a level; and
repeating a) to c) until all nodes have been assigned to a level of the directed graph.
4 Assignments
0 Petitions
Accused Products
Abstract
A computer executed method of determining compatible versions of dependent entities of a root entity having a specified version in a computer system. The method comprises building a directed graph containing dependent entities and dividing the directed graph into multiple levels. Compatible versions are determined for entities in upper levels of the directed graph before determining compatible versions for entities in lower levels of the directed graph.
-
Citations
15 Claims
-
1. A computer executed method of determining compatible versions of dependent entities of a root entity having a specified version in a computer system, the method comprising:
-
building a directed graph comprising the dependent entities; dividing the directed graph into multiple levels; determining which level of the multiple levels each dependent entity belongs to; dividing each level into one or more isolated subsets; and determining compatible versions for all entities in upper levels of the directed graph before determining compatible versions for any entity in lower levels of the directed graph; wherein building the directed graph comprises; representing the entities by nodes and dependency relationships between the entities by edges; and putting a directed edge from a first node to a second node which is dependent on the first node and referring to the first node as a parent node and the second node as a child node; wherein the directed graph is divided into levels in such a way that no node of a given level is dependent on a node of a lower level; and wherein dividing the directed graph into multiple levels comprises; putting a root node representing the root entity in a first level of the directed graph and all of said root node'"'"'s child nodes into a new level and then for each level of the directed graph; a. including in the current level all nodes which are interdependent directly or indirectly with the nodes already included in the current level; b. pushing into a next level of the directed graph all those nodes from the current level that are dependent on nodes which have not yet been assigned to a level; and c. putting all the child nodes of parent nodes in the current level into the next level of the directed graph if said child nodes have not already assigned to a level; and repeating a) to c) until all nodes have been assigned to a level of the directed graph. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. An apparatus comprising a processor, a memory in communication with the processor, and computer executable instructions stored in the memory and executable by the processor to:
-
build a directed graph containing dependent entities; divide the directed graph into multiple levels and determine which level of the multiple levels each dependent entity belongs to; assign the dependent entities in each level into one or more isolated subsets; assign compatible versions for all entities in upper levels of the directed graph before assigning compatible versions for any entity in lower levels of the directed graph; wherein the instructions to build the directed graph comprise instructions to; represent the entities by nodes and dependency relationships between the entities by edges; and put a directed edge from a first node to a second node which is dependent on the first node and referring to the first node as a parent node and the second node as a child node; wherein the directed graph is divided into levels in such a way that no node of a given level is dependent on a node of a lower level; and wherein the instructions to divide the directed graph into multiple levels comprise instructions to put a root node representing the root entity into a first level of the directed graph and all of said root node'"'"'s child nodes into a new level and then for each level of the directed graph; a. include in the current level all nodes which are interdependent directly or indirectly with the nodes already included in the current level; b. push into a next level of the directed graph all those nodes from the current level that are dependent on nodes which have not yet been assigned to a level; and c. put all the child nodes of parent nodes in the current level into the next level of the directed graph if said child nodes have not already assigned to a level; and repeat a) to c) until all nodes have been assigned to a level of the directed graph.
-
-
13. A method executed by a processor of upgrading a computer system comprising a root entity and a set of other entities that are dependent on the root entity, the method comprising:
-
specifying a change to the root entity or receiving information relating to a specified change for the root entity; building a directed graph of the entities, dividing the directed graph into multiple levels and determining which level of the multiple levels each entity belongs to; grouping entities within a same level of the graph into one or more isolated subsets, each isolated subset comprising entities which are directly dependent on a common parent entity; and determining consequential changes to the entities in each isolated subset, consequential changes for the entities in isolated subsets in upper levels of the directed graph being determined before consequential changes for entities in isolated subsets in lower levels of the directed graph; wherein at least one level of the directed graph includes at least a first isolated subset and a second isolated subset, said second isolated subset including a plurality of entities; wherein building the directed graph comprises; representing the entities by nodes and dependency relationships between the entities by edges; and putting a directed edge from a first node to a second node which is dependent on the first node and referring to the first node as a parent node and the second node as a child node; wherein the directed graph is divided into levels in such a way that no node of a given level is dependent on a node of a lower level; and wherein each entity corresponds to a node in the directed graph and wherein dividing the directed graph into multiple levels comprises; putting a root node representing the root entity in a first level of the directed graph and all of said root node'"'"'s child nodes into a new level and then for each level of the directed graph; a. including in the current level all nodes which are interdependent directly or indirectly with the nodes already included in the current level; b. pushing into a next level of the directed graph all those nodes from the current level that are dependent on nodes which have not yet been assigned to a level; and c. putting all the child nodes of parent nodes in the current level into the next level of the directed graph if said child nodes have not already assigned to a level; and repeating a) to c) until all nodes have been assigned to a level of the directed graph. - View Dependent Claims (14, 15)
-
Specification