FORM 2
THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENT RULES, 2003
COMPLETE SPECIFICATION
(See Section 10 and Rule 13)
Title of invention
METHOD AND SYSTEM FOR REGRESSION PACK OPTIMIZATION
Applicant
Tata Consultancy Services Limited
A company Incorporated in India under the Companies Act, 1956
Having address:
Nirmal Building, 9th floor,
Nariman point, Mumbai 400021,
Maharashtra, India
Preamble to the Description
The following specification particularly describes the invention and the manner in which it is to be performed.
2
TECHNICAL FIELD
[001] The disclosure herein generally relates to test case processing, and, more particularly, to a method and system for regression pack optimization.
5
BACKGROUND
[002] Automation testing tools, which can simulate wider scenarios, contribute to making any transformation more successful to deliver within time, cost, and quality. Critical programs are mandated to adopt tools which can manage 10 exhaustive scenarios, which need to be executed with maximum degree of parallelism to meet the changing data and timeline, while maintaining the data integrity and exclusiveness to make the testing effective. Every release adds new scripts to ensure coverage, but sometimes it adds overburden to the regression pack by introducing redundant execution paths with increased complex dependencies. 15 Manual audit fails to find optimized solution during the critical path execution.
SUMMARY
[003] Embodiments of the present disclosure present technological 20 improvements as solutions to one or more of the above-mentioned technical problems recognized by the inventors in conventional systems. For example, in one embodiment, a processor implemented method is provided. The method includes identifying, via one or more hardware processors, an optimized set of scenarios. Identifying the optimized set of scenarios includes the following steps. Initially, 25 information on a plurality of actionable events is obtained as input. Further, a control flow graph is generated by processing the information on the plurality of actionable events, wherein a plurality of unique modules form a vertex of the control flow graph and a control flow forms an edge of the control flow graph. Further, a plurality of paths between all of a plurality of pairs of entry and exit nodes 30 of the control flow graph are generated. Further, each of the plurality of paths is
3
categorized as one of low, average, and high, based on a determined cardinality. Further, the optimized set of scenarios is identified, based on categorization of the plurality of paths to generate one or more optimized automation scripts.
[004] In another aspect, the method includes reconstructing one or more of the plurality of paths in the control flow graph to obtain an optimized control 5 flow graph to accommodate at least one new functionality.
[005] In another aspect, the method includes reoptimizing the optimized set of scenarios to accommodate the additional functionality. Reoptimizing the optimized set of scenarios includes the following steps. Initially, at least one of a chosen path or a favorable path is prioritized based on associated length and cost. 10 Further, one or more key parameters of the additional functionality are identified by analyzing one or more scripts associated with the additional functionality, based on the prioritization of at least one of the chosen path or the favorable path. Further, the optimized set of scenarios from the generated plurality of paths are reoptimized to accommodate the identified one or more key parameters of the additional 15 functionality, wherein after reoptimizing the optimized set of scenarios, all paths are equivalent to a job.
[006] In yet another aspect, the method includes identifying dependency on plurality of optimized set of paths for one or more jobs. Identifying the dependency includes the following steps. Initially, a disjoint tree is constructed 20 based on the identified one or more key parameters, wherein, each node of the disjoint tree represents a job, wherein a directed edge exists between subsequent jobs and an edge exists between a job and associated critical data. Further, a collection of jobs is represented as a disjoint-set of weighted colored N-ary Trees (T) wherein a weight W is represented as vertex weight and a constraint C is 25 represented as vertex color. Further, a list of paths from the collection of disjoint set of weighted colored N-ary trees (T) is generated, wherein each path in the list of paths is from a root node to a leaf node for the disjoint set of weighted colored N-ary trees (T).
[007] In yet another aspect, the method includes scheduling the one or 30 more optimized jobs in the one or more hardware processors. Scheduling the one
4
or more optimized jobs includes constructing a timed N-ary tree(Ti), wherein in the constructing a timed N-ary tree(Ti), a plurality of running jobs and plurality of queued jobs are represented as the vertex and the minimum duration of the running jobs are represented as the edges, wherein the vertex and edges are pointing to one or more combination of possible sequence of plurality of running jobs and plurality 5 of queued jobs in a plurality of child vertices, and generating a minimum cost depth of the timed N-ary tree(Ti) for faster turnaround of one or more of the jobs with optimized sequence of plurality of jobs.
[008] In yet another aspect, a system is provided. The system includes one or more hardware processors, a communication interface, and a memory storing a 10 plurality of instructions. The plurality of instructions causes the one or more hardware processors to identify an optimized set of scenarios by executing the following steps. Initially, information on a plurality of actionable events is obtained as input. Further, a control flow graph is generated by processing the information on the plurality of actionable events, wherein a plurality of unique modules form a 15 vertex of the control flow graph and a control flow forms an edge of the control flow graph. Further, a plurality of paths between all of a plurality of pairs of entry and exit nodes of the control flow graph are generated. Further, each of the plurality of paths is categorized as one of low, average, and high, based on a determined cardinality. Further, the optimized set of scenarios is identified, based on 20 categorization of the plurality of paths to generate one or more optimized automation scripts.
[009] In yet another aspect, the system reconstructs one or more of the plurality of paths in the control flow graph to obtain an optimized control flow graph to accommodate at least one new functionality. 25
[010] In yet another aspect, the system reoptimizes the optimized set of scenarios to accommodate the additional functionality. Reoptimizing the optimized set of scenarios includes the following steps. Initially, at least one of a chosen path or a favorable path is prioritized based on associated length and cost. Further, one or more key parameters of the additional functionality are identified by analyzing 30 one or more scripts associated with the additional functionality, based on the
5
prioritization of at least one of the chosen path or the favorable path. Further, the optimized set of scenarios from the generated plurality of paths are reoptimized to accommodate the identified one or more key parameters of the additional functionality, wherein after reoptimizing the optimized set of scenarios, all paths are equivalent to a job. 5
[011] In yet another aspect, the system identifies dependency on plurality of optimized set of paths for one or more jobs. Identifying the dependency includes the following steps. Initially, a disjoint tree is constructed based on the identified one or more key parameters, wherein, each node of the disjoint tree represents a job, wherein a directed edge exists between subsequent jobs and an edge exists 10 between a job and associated critical data. Further, a collection of jobs is represented as a disjoint-set of weighted colored N-ary Trees (T) wherein a weight W is represented as vertex weight and a constraint C is represented as vertex color. Further, a list of paths from the collection of disjoint set of weighted colored N-ary trees (T) is generated, wherein each path in the list of paths is from a root node to a 15 leaf node for the disjoint set of weighted colored N-ary trees (T).
[012] In yet another aspect, the system schedules the one or more optimized jobs in the one or more hardware processors. Scheduling the one or more optimized jobs includes constructing a timed N-ary tree(Ti), wherein in the constructing a timed N-ary tree(Ti), a plurality of running jobs and plurality of 20 queued jobs are represented as the vertex and minimum duration of running jobs are represented as the edges, wherein the vertex and edges are pointing to one or more combination of possible sequence of plurality of running jobs and plurality of queued jobs in a plurality of child vertices, and generating a minimum cost depth of the timed N-ary tree(Ti) for faster turnaround of one or more of the jobs with 25 optimized sequence of plurality of jobs.
[013] In yet another aspect, a non-transitory computer readable medium is provided. The non-transitory computer readable medium includes a plurality of instructions, which when executed, cause one or more hardware processors to perform identification of an optimized set of scenarios. Identifying the optimized 30 set of scenarios includes the following steps. Initially, information on a plurality of
6
actionable events is obtained as input. Further, a control flow graph is generated by processing the information on the plurality of actionable events, wherein a plurality of unique modules form a vertex of the control flow graph and a control flow forms an edge of the control flow graph. Further, a plurality of paths between all of a plurality of pairs of entry and exit nodes of the control flow graph are 5 generated. Further, each of the plurality of paths is categorized as one of low, average, and high, based on a determined cardinality. Further, the optimized set of scenarios is identified, based on categorization of the plurality of paths to generate one or more optimized automation scripts.
[014] In yet another aspect, the non-transitory computer readable medium 10 configures the one or more hardware processors to reconstruct one or more of the plurality of paths in the control flow graph to obtain an optimized control flow graph to accommodate at least one new functionality.
[015] In another aspect, the non-transitory computer readable medium configures the one or more hardware processors to reoptimize the optimized set of 15 scenarios to accommodate the additional functionality. Reoptimizing the optimized set of scenarios includes the following steps. Initially, at least one of a chosen path or a favorable path is prioritized based on associated length and cost. Further, one or more key parameters of the additional functionality are identified by analyzing one or more scripts associated with the additional functionality, based on the 20 prioritization of at least one of the chosen paths or the favorable path. Further, the optimized set of scenarios from the generated plurality of paths are reoptimized to accommodate the identified one or more key parameters of the additional functionality, wherein after reoptimizing the optimized set of scenarios, all paths are equivalent to a job. 25
[016] In yet another aspect, the non-transitory computer readable medium configures the one or more hardware processors to identify dependency on plurality of optimized set of paths for one or more jobs. Identifying the dependency includes the following steps. Initially, a disjoint tree is constructed based on the identified one or more key parameters, wherein, each node of the disjoint tree represents a 30 job, wherein a directed edge exists between subsequent jobs and an edge exists
7
between a job and associated critical data. Further, a collection of jobs is represented as a disjoint-set of weighted colored N-ary Trees (T) wherein a weight W is represented as vertex weight and a constraint C is represented as vertex color. Further, a list of paths from the collection of disjoint set of weighted colored N-ary trees (T) is generated, wherein each path in the list of paths is from a root node to a 5 leaf node for the disjoint set of weighted colored N-ary trees (T).
[017] In yet another aspect, the non-transitory computer readable medium configures the one or more hardware processors to schedule the one or more optimized jobs in the one or more hardware processors. Scheduling the one or more optimized jobs includes constructing a timed N-ary tree(Ti), wherein in the 10 constructing a timed N-ary tree(Ti), a plurality of running jobs and plurality of queued jobs are represented as the vertex and the minimum duration of the running jobs are represented as the edges, wherein the vertex and edges are pointing to one or more combination of possible sequence of plurality of running jobs and plurality of queued jobs in a plurality of child vertices, and generating a minimum cost depth 15 of the timed N-ary tree(Ti) for faster turnaround of one or more of the jobs with optimized sequence of plurality of jobs.
[018] It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory only and are not restrictive of the invention, as claimed. 20
BRIEF DESCRIPTION OF THE DRAWINGS
[019] The accompanying drawings, which are incorporated in and constitute a part of this disclosure, illustrate exemplary embodiments and, together 25 with the description, serve to explain the disclosed principles:
[020] FIG. 1 illustrates an exemplary system for regression pack optimization, according to some embodiments of the present disclosure.
[021] FIG. 2 is a flow diagram depicting steps involved in the process of regression pack optimization being performed by the system of FIG. 1, according 30 to some embodiments of the present disclosure.
8
[022] FIG. 3 is a flow diagram depicting steps involved in the process of reoptimizing an optimized set of scenarios to accommodate an additional functionality, by the system of FIG. 1, according to some embodiments of the present disclosure.
[023] FIG. 4 is a flow diagram depicting steps involved in the process of 5 identifying dependency on a plurality of optimized set of paths for one or more jobs, by the system of FIG. 1, according to some embodiments of the present disclosure.
[024] FIG. 5 is a flow diagram depicting steps involved in the process of scheduling one or more optimized jobs in the one or more hardware processors, by the system of FIG. 1, according to some embodiments of the present disclosure. 10
[025] FIGS. 6A through 6E depict example diagrams of various stages of the regression pack optimization by the system of FIG. 1, according to some embodiments of the present disclosure.
DETAILED DESCRIPTION OF EMBODIMENTS 15
[026] Exemplary embodiments are described with reference to the accompanying drawings. In the figures, the left-most digit(s) of a reference number identifies the figure in which the reference number first appears. Wherever convenient, the same reference numbers are used throughout the drawings to refer 20 to the same or like parts. While examples and features of disclosed principles are described herein, modifications, adaptations, and other implementations are possible without departing from the scope of the disclosed embodiments.
[027] Automation testing tools, which can simulate wider scenarios, contribute to making any transformation more successful to deliver within time, 25 cost, and quality. Critical programs are mandated to adopt tools which can manage exhaustive scenarios, which need to be executed with maximum degree of parallelism to meet the changing data and timeline, while maintaining the data integrity and exclusiveness to make the testing effective. Every release adds new scripts to ensure coverage, but sometimes it adds overburden to the regression pack 30
9
by introducing redundant execution paths with increased complex dependencies. Manual audit fails to find optimized solution during the critical path execution.
[028] In order to address these challenges, embodiments disclosed herein provide a method and a system for regression pack optimization. The system initially identifies an optimized set of scenarios, for a given set of data, which 5 involves generating a control flow graph by processing information on a plurality of actionable events received as input. Further, one or more of a plurality of paths in the control flow graph are reconstructed to obtain an optimized control flow graph to accommodate at least one new functionality. Further, dependency on a plurality of optimized set of paths for one or more jobs is identified. Further, based 10 on the identified dependency, one or more optimized jobs are scheduled.
[029] Referring now to the drawings, and more particularly to FIG. 1 through FIG. 6E, where similar reference characters denote corresponding features consistently throughout the figures, there are shown preferred embodiments and these embodiments are described in the context of the following exemplary system 15 and/or method.
[030] FIG. 1 illustrates an exemplary system for regression pack optimization, according to some embodiments of the present disclosure. The system 100 includes or is otherwise in communication with hardware processors 102, at least one memory such as a memory 104, an I/O interface 112. The hardware 20 processors 102, memory 104, and the Input /Output (I/O) interface 112 may be coupled by a system bus such as a system bus 108 or a similar mechanism. In an embodiment, the hardware processors 102 can be one or more hardware processors.
[031] The I/O interface 112 may include a variety of software and hardware interfaces, for example, a web interface, a graphical user interface, and 25 the like. The I/O interface 112 may include a variety of software and hardware interfaces, for example, interfaces for peripheral device(s), such as a keyboard, a mouse, an external memory, a printer and the like. Further, the I/O interface 112 may enable the system 100 to communicate with other devices, such as web servers, and external databases. 30
10
[032] The I/O interface 112 can facilitate multiple communications within a wide variety of networks and protocol types, including wired networks, for example, local area network (LAN), cable, etc., and wireless networks, such as Wireless LAN (WLAN), cellular, or satellite. For the purpose, the I/O interface 112 may include one or more ports for connecting several computing systems with one 5 another or to another server computer. The I/O interface 112 may include one or more ports for connecting several devices to one another or to another server.
[033] The one or more hardware processors 102 may be implemented as one or more microprocessors, microcomputers, microcontrollers, digital signal processors, central processing units, node machines, logic circuitries, and/or any 10 devices that manipulate signals based on operational instructions. Among other capabilities, the one or more hardware processors 102 is configured to fetch and execute computer-readable instructions stored in the memory 104.
[034] The memory 104 may include any computer-readable medium known in the art including, for example, volatile memory, such as static random-15 access memory (SRAM) and dynamic random-access memory (DRAM), and/or non-volatile memory, such as read only memory (ROM), erasable programmable ROM, flash memories, hard disks, optical disks, and magnetic tapes. In an embodiment, the memory 104 includes a plurality of modules 106.
[035] The plurality of modules 106 include programs or coded instructions 20 that supplement applications or functions performed by the system 100 for executing different steps involved in the process of regression pack optimization. The plurality of modules 106, amongst other things, can include routines, programs, objects, components, and data structures, which performs particular tasks or implement particular abstract data types. The plurality of modules 106 may also be 25 used as, signal processor(s), node machine(s), logic circuitries, and/or any other device or component that manipulates signals based on operational instructions. Further, the plurality of modules 106 can be used by hardware, by computer-readable instructions executed by the one or more hardware processors 102, or by a combination thereof. The plurality of modules 106 can include various sub-30 modules (not shown). The plurality of modules 106 may include computer-readable
11
instructions that supplement applications or functions performed by the system 100 for the regression pack optimization.
[036] The data repository (or repository) 110 may include a plurality of abstracted piece of code for refinement and data that is processed, received, or generated as a result of the execution of the plurality of modules in the module(s) 5 106.
[037] Although the data repository 110 is shown internal to the system 100, it will be noted that, in alternate embodiments, the data repository 110 can also be implemented external to the system 100, where the data repository 110 may be stored within a database (repository 110) communicatively coupled to the system 10 100. The data contained within such external database may be periodically updated. For example, new data may be added into the database (not shown in FIG. 1) and/or existing data may be modified and/or non-useful data may be deleted from the database. In one example, the data may be stored in an external system, such as a Lightweight Directory Access Protocol (LDAP) directory and a Relational 15 Database Management System (RDBMS). Functions of the components of the system 100 are now explained with reference to the steps in flow diagrams in FIG. 2, FIG. 3, FIG. 4, and FIG. 5.
[038] FIG. 2 is a flow diagram depicting steps involved in the process of regression pack optimization being performed by the system of FIG. 1, according 20 to some embodiments of the present disclosure.
[039] In an embodiment, the system 100 comprises one or more data storage devices or the memory 104 operatively coupled to the processor(s) 102 and is configured to store instructions for execution of steps of a method 200 by the processor(s) or one or more hardware processors 102. The steps of the method 200 25 of the present disclosure will now be explained with reference to the components or blocks of the system 100 as depicted in FIG. 1 and the steps of flow diagram as depicted in FIG. 2. Although process steps, method steps, techniques or the like may be described in a sequential order, such processes, methods, and techniques may be configured to work in alternate orders. In other words, any sequence or order of steps 30 that may be described does not necessarily indicate a requirement that the steps to
12
be performed in that order. The steps of processes described herein may be performed in any order practical. Further, some steps may be performed simultaneously.
[040] The system 100 is configured to identify an optimized set of scenarios for a given input. Identifying the optimized set of scenarios includes the 5 following steps. At step 202 of the method 200 in FIG. 2, information on a plurality of actionable events is obtained as input. In an embodiment, the input is fed to the system via one or more users, using a user interface provided by the one or more communication interfaces 112. In another embodiment, the system 100 may collect/fetch the input from one or more associated sources that may have been 10 configured to be in communication with the system 100 via the one or more communication interfaces 112. For example, the system 100 may use an event listener plug-in as depicted in the example in FIG. 6A, to collect information about the actionable events of a target application. If the target application is a web application, then the system 100 may use a browser plugin to gather the information 15 on the actionable events.
[041] Further, at step 204 of the method 200, the system 100 generates a control flow graph by processing the information on the plurality of actionable events. The system 100 generates the control flow graph such that a plurality of unique modules identified from the information on the plurality of actionable events 20 form each vertex of the control flow graph and a control flow forms each edge of the control flow graph.
[042] Flow control graph 𝐺= {𝑉,𝐸},
where, 𝑉= {𝜐1,𝜐2,…𝜐𝑛}, 𝐸= {𝑒1,𝑒2,…𝑒𝑛}, and 𝑒𝑥= {(𝜐1,𝜐𝑗)| 1 ≤25 𝑖,𝑗 ≤𝑛}
For every flow of manual test execution, value of 𝑔 is obtained, where 𝑔 ∈𝐺, and 𝐺= 𝑔1∪ 𝑔2…, i.e. 𝐺= ⋃𝑔𝑖1≤𝑖≤𝐼
30
13
Further, the system 100 finds a scenario list 𝑆={𝑠1,𝑠2,…𝑠𝑘 } where each 𝑠={(𝜐1,𝜐2,…𝜐𝑛)| 𝑙 ≤𝑛}.
This approach has been designed with a goal to
Minimize 𝑘, where ⋃𝑠𝑖\𝑉=∅1≤𝑖≤𝑘, which ensures that minimum set of 5 scenarios cover maximum actionable coordinates.
[043] Further, at step 206 of the method 200, a plurality of paths between all of a plurality of pairs of entry and exit nodes of the control flow graph are generated. Approach used for retrieving all the paths between the entry and exist 10 nodes is given in Algorithm 1.
Algorithm 1 All pair path extraction
1: Input: Directed graph G = (V, E)
2: Output: Set of visited path Set[] All Paths 15
3: for each node vx ∈ V do
4: if incident edge e ∈ vx then
5: if No child of vx then
6: vexit = vexit ∪ vx
7: end if 20
8: else
9: ventry = ventry ∪vx
10: end if
11: end for
12: for each entry-node i of ventry ∈ V do 25
13: for each exit-node j of vexit ∈ V do
14: Define array as_visited of length n
15: Set as_visited[v] = False for v = 1, . . . , n
16: Call DFS-traversal(i)
17:All Paths.add (as_visited[j]) 30
14
18: end for
19: end for
20: return All Paths
[044] For each pair of entry-exit nodes, there exists (|𝑉|−2)!|𝐸| number 5 of paths.
[045] From among the paths, a subset of paths i.e. 𝑆′⊂𝑆 is to be selected as optimized set of scenarios, so that 𝑉𝑠\𝑉= ∅|𝑉𝑠∈ ⋃𝑆′. To achieve this, at step 208 of the each of the plurality of paths is categorized as one of low, average, and high, based on a determined cardinality. In an embodiment, categorization of each 10 of the plurality of paths as one of the low, average, and high, is in comparison with reference values defined against each of the low, average, and high classes. Based on match of a measured cardinality value with any of the reference values, associated class is selected as one of low, average, and high classes. A scenario with very cardinality below a threshold indicates less functional script, and increases 15 volume of the regression suite. Similarly a scenario with cardinality exceeding a threshold indicates less script covering more functional points, which may be difficult to maintain.
[046] Further, at step 210 of the method 200, the system 100 identifies the optimized set of scenarios based on categorization of the plurality of paths to 20 generate one or more optimized automation scripts. For identifying the optimized set of scenarios, the system 100 may use a range of the cardinality of the sets in 𝑆 was used along with a suitable technique (for example, Nearest Neighbor Classification with distance-based weighting scheme with value of kdecision objects being minimum, average, and maximum cardinality), in order to adjust cost, 25 for example, as in a set cover algorithm given below.
Algorithm 2: Set cover algorithm
1: Input: All Nodes V = {v1,v2,..,vn} , All Scenario Set[]
S = {s1,s2,..,sm} ∈ V , Cost C = {c1,c2,..} 30
2: Output: A Set Cover S’
15
3: S′ ← ∅
4: X ← ∅
5: while X ̸= V do
6: j = argmin
{ ∀cjlow = 3, ∀cjavg = 2, ∀cjhigh = 3} 5
7: S′ ← S′ ∪ {Sj}
8: X ← S′ ∪ Sj
9: end while
[047] The system 100 is configured to reoptimize the optimized set of 10 scenarios to accommodate an additional functionality when required. Steps involved in the process of reoptimizing the optimized set are depicted in method 300 in FIG. 3, and are explained hereafter. At step 302 of the method 300, the system 100 prioritizes at least one of a chosen path or a favorable path based on associated length and cost. Further, at step 304 of the method 300, the system 100 15 identifies one or more key parameters of the additional functionality by analyzing one or more scripts associated with the additional functionality, based on the prioritization of at least one of the chosen path or the favorable path. Further, at step 306 of the method 300, the system 100 reoptimizes the optimized set of scenarios from the generated plurality of paths to accommodate the identified one or more 20 key parameters of the additional functionality, wherein after reoptimizing the optimized set of scenarios, all paths are equivalent to a job.
[048] By means of the re-optimization, when the new functionality is added to 𝐺, 𝐺′ is obtained, wherein.
𝐺′= 𝐺+ 𝛿𝐺| 𝐺′= {𝑉+ 𝛿𝑉,𝐸+ 𝛿𝐸}. In this process the system 100 25 rebuilds scenario paths with minimum modification of 𝑆′ to obtain 𝑆′′= 𝑆′+ 𝛿𝑆 𝐴𝑙𝑙 𝑉𝑆′′∈ 𝑆′′| 𝑉𝑆′′\𝑉= ∅
[049] The system 100 reanalyzes 𝐺′ using Algorithm 3, which internally calls algorithm 1 to generate revised set of paths between all pair sets. The system 100 further prioritizes the already chosen paths to reduce rework, and also 30 decrements the cost [𝑐𝑗] for the already chosen path sets.
16
Algorithm 3: Reconstruct the path set
1: Input: All Nodes V ′ = {v1,v2,..,vn}
2: Output: A Set Cover Snew′
3: S′′ = Call Algorithm 1(V’) 5
4: for cost ci ∈ S′′ ∩ S′ do
5: ci + +
6: end for
7: Call Algorithm 3(V ′,S′′,C)
10
[050] The system 100 further identifies dependency on plurality of optimized set of paths for one or more jobs. Various steps involved in the process of identifying the dependency are depicted in method 400 in FIG. 4, and are explained hereafter. At step 402 of the method 400, the system 100 constructs a disjoint tree based on the identified one or more key parameters, wherein, each node 15 of the disjoint tree represents a job, wherein a directed edge exists between subsequent jobs and an edge exists between a job and associated critical data. Further, at step 404 of the method 400, the system 100 represents a collection of jobs as a disjoint-set of weighted colored N-ary Trees (T) wherein a weight W is represented as vertex weight and a constraint C is represented as vertex color. 20 Further, at step 406 of the method 400, the system 100 generates a list of paths from the collection of disjoint set of weighted colored N-ary trees (T), wherein each path in the list of paths is from a root node to a leaf node for the disjoint set of weighted colored N-ary trees (T).
[051] Once the dependencies are identified, the system 100 may use this 25 information for scheduling the one or more optimized jobs in the one or more hardware processors. Steps involved in the process of scheduling the one or more optimized jobs are depicted in method 500 in FIG. 5, and are explained hereafter. At step 502 of the method 500, the system 100 constructs a timed N-ary tree(Ti), wherein in the constructing a timed N-ary tree(Ti), a plurality of running jobs and 30 plurality of queued jobs are represented as the vertex and a minimum job duration
17
(i.e. minimum duration of running jobs) are represented as the edges, wherein the vertex and edges are pointing to one or more combination of possible sequence of plurality of running jobs and plurality of queued jobs in a plurality of child vertices. The step 502 outputs a list of paths P such that ∀𝑝 ∈ 𝑃, 𝑝 is a path from the root node to a leaf node for each Tree in the disjoint forest of trees. Algorithm 4 is an 5 example algorithm that may be used by the system 100 for finding paths. Further, at step 504 of the method 500, the system 100 generates a minimum cost depth of the timed N-ary tree(Ti) for faster turnaround of one or more of the jobs with optimized sequence of plurality of jobs. Algorithm 5 is an example algorithm that may be used by the system 100 for scheduling the jobs. 10
Algorithm 4: Weighted Colored N-ary Tree Path Finder
1: Input: Disjoint-set of weighted colored N-ary trees (T)
2: Output: List LP of paths P such that ∀p ∈ P, p is a path from rootT to a leaf 15 node
3: initialize: List LP
4: for each tree t ∈ T do
5: begin procedure: find all leaf nodes L ∈ T
6: Input: Weighted colored N-ary tree (T) 20
7: Output: Subset L ∈ N such that ∀l ∈ L, l is a leaf node
8: initialize: stack S, set L, node M, node R := rootT
9:S.push(R)
10:while S ̸= empty do
11:M ← S.pop() 25
12: if M is a leaf node then
13: L.insert(M)
14: else
15: S.push(childrenM)
16:end if 30
17:end while
18:end procedure: find all leaf nodes L ∈ T
18
19: for each leaf node l ∈ L do
20: begin procedure: find path from leaf node l to R
21:initialize: list P
22: while S ̸= R do
23: P.insert(l) 5
24: l ← parentl
25: end while
26: LP.insert(P)
27:end procedure: find path from leaf node l to R
28: end for 10
29: end for
Algorithm 5: Regression Test Suite Scheduler
15
1: Input: List of jobs J, working jobs JW , Queued jobs JQ, a timed nary tree P
2: Output: Ordered list LS of nodes N such that –
i) N <= NS
ii) TAT(N ∈Li) >= TAT(N ′ ∈Lj) for i < j
iii) ∃ 𝑐𝑜𝑛𝑠𝑡𝑟𝑎𝑖𝑛𝑡𝑠 𝐶𝑖,𝑗∶∀ 𝐶𝑖 𝜖 𝑁 𝑎𝑛𝑑 𝐶𝑗 𝜖 𝑁, 𝐶𝑖≠ 𝐶𝑖
3: begin procedure: Create Child Node (P, JW , JQ)
4: if J = ∅ and JW = ∅ and JQ = ∅ then
5: return
6: else
7: 𝐽 ←min(𝐽𝑤)
8: 𝐽𝑊 ← 𝐽𝑤−𝐽
9: 𝐽𝑄 ← 𝐽𝑄 ∪𝑐ℎ𝑖𝑙𝑑 𝑜𝑓 𝑗 ∪𝑎𝑙𝑙 𝑟𝑜𝑜𝑡𝑠 𝑗
10: |𝑗|=∅ then
11: 𝐶 ← 𝐽𝑤 𝐶𝑅
12: else
13: 𝐶 ← 𝐽𝑤 𝐶 |𝑗|
19
14: end if
15: for each X ∈𝐶 𝒅𝒐
16: 𝑁𝑥 ← 𝐽𝑊+𝑋
17: If 𝑁𝑥 is non conflicting (unique colors) then
18: P.add (𝑁𝑥)
19: Create child node 𝑁𝑥,𝐽𝑤,𝐽𝑄
20: end if
21: for all DFS(P) do
𝐿𝑠 ←min(𝑃) 𝑟𝑒𝑡𝑢𝑟𝑛 𝐿𝑠
22: end for
Experimental Results:
[052] An example control flow graph of an observed UI application is depicted in FIG. 6B and the optimized path in FIG. 6C. After gathering all paths 5 defined as unique scenario transformed into a job, that need to be scheduled to CI tool. The job has their constraints by nature are defined as a graph, as in FIG. 6D.
[053] During the experiments, continuous build and deploy process was augmented by performing an ’optimize and add’ strategy. All the optimized scenarios generated by the system 100 were fed into a pipeline configuration system 10 in a framework-agnostic text format. By resolving the weighted coloured trees with nodes (jobs), the system 100 arrived at a job schedule for different slot sizes using a RTS scheduler algorithm. FIG. 6E depicts how the job pipelines can be reorganized and scheduled to maximize conflict resolution and minimize total turnaround time using optimum slot sizes. It was observed that job pipelines can be 15 reorganized and scheduled to maximize conflict resolution and minimize total turnaround time using optimum slot sizes. Comparison between scenario sets with and without dependency/constraints indicated considerable change in turn-around time with linear variance. As the degree of dependency increased, i.e. as more scripts depend on same resources, exponential increase in turnaround time was 20 observed when using the state-of-the-art approaches. A comparison was made
20
between manual and optimizer performance against increasing system complexity, and it was observed that with incremental scenario inclusions, script filtering and subsequent scheduling done by the optimizer performs consistently better than that based on instinct. Taking two random data points at counts 100 and 350, it was found that a tester designed 62 and 145 scripts respectively, which was a derivative 5 of the tester’s experience and instinct. In contrast, the system 100 employed the optimization technique to cut back on the number of scripts to 26 and 77 respectively. Consequently, the overall time to schedule and execute a regression pack formed out of these scripts progressively decreased with an increase in code complexity and volume. During the experiments, a few complex scenarios like 10 complexity level 200 were observed, where the basic block counts were more with respect to the overall volume of the code base. The experiments indicated real and augmented data providing minimum 40% and a maximum 61% improvements.
[054] The written description describes the subject matter herein to enable
any person skilled in the art to make and use the embodiments. The scope of the 15 subject matter embodiments is defined by the claims and may include other modifications that occur to those skilled in the art. Such other modifications are intended to be within the scope of the claims if they have similar elements that do not differ from the literal language of the claims or if they include equivalent elements with insubstantial differences from the literal language of the claims. 20
[055] The embodiments of present disclosure herein address unresolved
problem of regression pack optimization. The embodiment thus provides a method and system for identifying an optimized set of scenarios by processing actionable events obtained as input. Moreover, the embodiment herein further provides mechanisms for reoptimizing the optimized set of scenarios to accommodate 25 additional functionality, identifying dependency on plurality of optimized set of paths for one or more jobs, and scheduling the one or more optimized jobs in the one or more hardware processors.
[056] It is to be understood that the scope of the protection is extended to
such a program and in addition to a computer-readable means having a message 30 therein; such computer-readable storage means contain program-code means for
21
implementation of one or more steps of the method, when the program runs on a server or mobile device or any suitable programmable device. The hardware device can be any kind of device which can be programmed including e.g., any kind of computer like a server or a personal computer, or the like, or any combination thereof. The device may also include means which could be e.g., hardware means 5 like e.g., an application-specific integrated circuit (ASIC), a field-programmable gate array (FPGA), or a combination of hardware and software means, e.g., an ASIC and an FPGA, or at least one microprocessor and at least one memory with software processing components located therein. Thus, the means can include both hardware means and software means. The method embodiments described herein 10 could be implemented in hardware and software. The device may also include software means. Alternatively, the embodiments may be implemented on different hardware devices, e.g., using a plurality of CPUs.
[057] The embodiments herein can comprise hardware and software
elements. The embodiments that are implemented in software include but are not 15 limited to, firmware, resident software, microcode, etc. The functions performed by various components described herein may be implemented in other components or combinations of other components. For the purposes of this description, a computer-usable or computer readable medium can be any apparatus that can comprise, store, communicate, propagate, or transport the program for use by or in 20 connection with the instruction execution system, apparatus, or device.
[058] The illustrated steps are set out to explain the exemplary
embodiments shown, and it should be anticipated that ongoing technological development will change the manner in which particular functions are performed. These examples are presented herein for purposes of illustration, and not limitation. 25 Further, the boundaries of the functional building blocks have been arbitrarily defined herein for the convenience of the description. Alternative boundaries can be defined so long as the specified functions and relationships thereof are appropriately performed. Alternatives (including equivalents, extensions, variations, deviations, etc., of those described herein) will be apparent to persons 30 skilled in the relevant art(s) based on the teachings contained herein. Such
22
alternatives fall within the scope of the disclosed embodiments. Also, the words “comprising,” “having,” “containing,” and “including,” and other similar forms are intended to be equivalent in meaning and be open ended in that an item or items following any one of these words is not meant to be an exhaustive listing of such item or items, or meant to be limited to only the listed item or items. It must also be 5 noted that as used herein and in the appended claims, the singular forms “a,” “an,” and “the” include plural references unless the context clearly dictates otherwise.
[059] Furthermore, one or more computer-readable storage media may be
utilized in implementing embodiments consistent with the present disclosure. A computer-readable storage medium refers to any type of physical memory on which 10 information or data readable by a processor may be stored. Thus, a computer-readable storage medium may store instructions for execution by one or more processors, including instructions for causing the processor(s) to perform steps or stages consistent with the embodiments described herein. The term “computer-readable medium” should be understood to include tangible items and exclude 15 carrier waves and transient signals, i.e., be non-transitory. Examples include random access memory (RAM), read-only memory (ROM), volatile memory, non-volatile memory, hard drives, CD ROMs, DVDs, flash drives, disks, and any other known physical storage media.
[060] It is intended that the disclosure and examples be considered as 20
exemplary only, with a true scope of disclosed embodiments being indicated by the following claims.1. A processor implemented method, comprising:
obtaining (202) information on a plurality of actionable events as input;
generating (204) a control flow graph by processing the information on the plurality of actionable events, wherein a plurality of unique modules form a vertex of the control flow graph and a control flow forms an edge of the control flow graph;
generating (206) a plurality of paths between all of a plurality of pairs of entry and exit nodes of the control flow graph; categorizing (208) each of the plurality of paths as one of low, average, and high, based on a determined cardinality; and identifying (210) an optimized set of scenarios, based on categorization of the plurality of paths to generate one or more optimized automation scripts.
2. The method as claimed in claim 1, comprising reconstructing one or more of the plurality of paths in the control flow graph to obtain an optimized control flow graph to accommodate at least one new functionality.
3. The method as claimed in claim 2, comprising reoptimizing the optimized set of scenarios to accommodate the at least one additional functionality, by:
prioritizing (302) at least one of a chosen path or a favorable path
based on associated length and cost;
identifying (304) one or more key parameters of the additional
functionality by analyzing one or more scripts associated with the
additional functionality based on the prioritization of at least one of
the chosen path or the favorable path; and
reoptimizing (306) the optimized set of scenarios from the generated
plurality of paths, to accommodate the identified one or more key

parameters of the additional functionality, wherein after reoptimizing the optimized set of scenarios, all paths are equivalent to a job.
4. The method as claimed in claim 3, comprising identifying dependency on
plurality of optimized set of paths for one or more jobs, wherein identifying
the dependency comprising:
constructing (402) a disjoint tree based on the identified one or more key parameters, wherein, each node of the disjoint tree represents a job, wherein a directed edge exists between subsequent jobs and an edge exists between the job and associated critical data; representing (404) a collection of jobs as a disjoint-set of weighted colored N-ary Trees (T) wherein a weight W is represented as vertex weight and a constraint C is represented as vertex color; and generating (406) a list of paths from the collection of disjoint set of weighted colored N-ary trees (T), wherein each path in the list of paths is from a root node to a leaf node for the disjoint set of weighted colored N-ary trees (T).
5. The method as claimed in claim 3, comprising scheduling the one or more
optimized jobs in the one or more hardware processors, by:
constructing (502) a timed N-ary tree(Ti), wherein a plurality of running jobs and plurality of queued jobs are represented as the vertex and a minimum job duration are represented as the edges of the timed N-ary tree(Ti), wherein the vertex and edges are pointing to one or more combination of possible sequence of plurality of running jobs and plurality of queued jobs in a plurality of child vertices; and
generating (504) a minimum cost depth of the timed N-ary tree(Ti) for faster turnaround of one or more of the jobs with optimized sequence of plurality of jobs.

6. A system (100), comprising:
one or more hardware processors (102);
a communication interface (112); and
a memory (104) storing a plurality of instructions, wherein the plurality of
instructions cause the one or more hardware processors to:
obtain information on a plurality of actionable events as input;
generate a control flow graph by processing the information on the
plurality of actionable events, wherein a plurality of unique modules
form a vertex of the control flow graph and a control flow forms an
edge of the control flow graph;
generate a plurality of paths between all of a plurality of pairs of
entry and exit nodes of the control flow graph;
categorize each of the plurality of paths as one of low, average, and
high, based on a determined cardinality; and
identify the optimized set of scenarios, based on categorization of
the plurality of paths to generate one or more optimized automation
scripts.
7. The system as claimed in claim 6, wherein the one or more hardware processors are configured to reconstruct one or more of the plurality of paths in the control flow graph to obtain an optimized control flow graph to accommodate at least one new functionality.
8. The system as claimed in claim 7, wherein the one or more hardware processors are configured to reoptimize the optimized set of scenarios to accommodate the at least one additional functionality, by:
prioritizing at least one of a chosen path or a favorable path based on associated length and cost;
identifying one or more key parameters of the additional functionality by analyzing one or more scripts associated with the additional functionality based on the prioritization of at least one of

the chosen path or the favorable path; and
reoptimizing the optimized set of scenarios from the generated plurality of paths, to accommodate the identified one or more key parameters of the additional functionality, wherein after reoptimizing the optimized set of scenarios, all paths are equivalent to a job.
9. The system as claimed in claim 8, wherein the one or more hardware
processors are configured to identify dependency on plurality of optimized
set of paths for one or more jobs, by:
constructing a disjoint tree based on the identified one or more key
parameters, wherein, each node of the disjoint tree represents a job,
wherein a directed edge exists between subsequent jobs and an edge
exists between the job and associated critical data;
representing a collection of jobs as a disjoint-set of weighted colored
N-ary Trees (T) wherein a weight W is represented as vertex weight
and a constraint C is represented as vertex color; and
generating a list of paths from the collection of disjoint set of
weighted colored N-ary trees (T), wherein each path in the list of
paths is from a root node to a leaf node for the disjoint set of
weighted colored N-ary trees (T).
10. The system as claimed in claim 8, wherein the one or more hardware
processors are configured to schedule the one or more optimized jobs in the
one or more hardware processors, by:
constructing a timed N-ary tree(Ti), wherein a plurality of running jobs and plurality of queued jobs are represented as the vertex and the minimum job duration are represented as the edges in the constructed timed N-ary tree(Ti), wherein the vertex and edges are pointing to one or more combination of possible sequence of plurality of running jobs and plurality of queued jobs in a plurality

of child vertices; and
generating a minimum cost depth of the timed N-ary tree(Ti) for faster turnaround of one or more of the jobs with optimized sequence of plurality of jobs.