Method and apparatus for minimum cost cycle removal from a directed graph

A system for optimizing a directed graph by minimizing a cost of removing at least one cycle of the directed graph, the system comprising:

• a computing device including a processor coupled to a system memory, the system memory storing instructions for execution on the processor, the instructions configured to cause the processor to:
• obtain the directed graph including at least two vertices and at least one edge at a first computing device, wherein the at least two vertices of the directed graph represent at least two operations of a software application and the at least one edge of the directed graph represents a dependency between the at least two operations;
• assign each vertex in the directed graph a unique value;
• identify the at least one cycle in the directed graph;
• and
• determine the at least one edge to remove from the directed graph by:
• obtain an edge weight for each edge in the directed graph;
• assign the each edge a binary variable;
• generate a linear cost function that is equal to a sum of each edge weight multiplied by the corresponding binary variable;
• generate a constraint for the each edge that is a function of the unique value of an ending vertex minus the unique value of a starting vertex plus a product of the binary variable associated with the edge and a large number wherein the large number is set by the system to be larger than any possible outcome of a subtraction of the starting vertex value from the ending vertex value;
• and
• remove the at least one edge from the directed-graph and the corresponding dependency between the at least two operations of the software application according to the linear cost function and the constraint.

A computer-implemented method of for optimizing a directed graph by minimizing a cost of removing at least one cycle of the directed graph, the method comprising:

• obtaining the directed graph including at least two vertices and at least one edge at a first computing device by a processor, wherein the at least two vertices of the directed graph represent at least two operations of a software application and the at least one edge of the directed graph represents a dependency between the at least two operations;
• assigning each vertex a unique value;
• determining a presence of at least one cycle in the directed graph by:
• subtracting the unique value of a first vertex from a second vertex, wherein an edge starts at the first vertex and ends at the second vertex;
• and
• comparing a result of the subtraction to zero, wherein a value less than zero indicates the presence of the at least one cycle;
• and
• determining the at least one edge to remove from the directed graph by:
• obtaining an edge weight for each edge in the directed graph;
• assigning the each edge a binary variable;
• generating a linear cost function that is equal to a sum of the each edge weight multiplied by the corresponding binary variable;
• generating a constraint for the each edge that is a function of the unique value of an ending vertex minus the unique value of a starting vertex plus a product of the binary variable associated with the each edge and a large number wherein the large number comprises at least double a total number of edges in the directed graph;
• and
• removing the at least one edge of the directed graph and the corresponding dependency between the at least two operations of the software application according to a linear program that utilizes the linear cost function and the constraint and determines a value of each binary variable to be assessed in removing the at least one edge.