This paper describes one of the solutions for the ninth Transformation Tool Contest (TTC '16)1, which resolves the Class Responsibility Assignment Case using a transformation tool based on Microsoft Excel and Visual Basic. In this project, these relatively unusual technologies are used to e ectively enhance the processing of large models and matrices throughout di erent test cases proposed for the competition. Given a Responsibility Dependency Graph, the solution analyzes the relationships among the given features and produces a class diagram that aims to get the highest possible cohesion and lowest possible coupling. The solution is based on an adaptation of the Markov Clustering Algorithm used to manage bi-directional, un-weighted sets of nodes and grouping them into clusters. The aim of this work is to take one step further in the graph/model optimization eld through the treatment of matrices, a strategy that is not so widely used.
Cohesion is a property that refers to the degree to which the elements of a module belong together, while coupling is the degree of interdependence between di erent modules. In order to generate high-quality models, the need for measuring and comparing how strong the relationship is between di erent components of a module is extremely important. Even though in some cases the coupling will always be inevitably higher than the cohesion, there will always exist ways to optimize the resulting model as much as possible.
The algorithm used in this solution to generate the resulting class diagram is based on the foundations of the Markov Clustering Algorithm [SVD00] [KM09]. However, most of the steps have been slightly or completely altered since they have been deemed not as e ective for the proposed problem.
As described in the problem de nition, for a total of 18 input features there are 682.076.806.159 possible class diagrams built upon di erent feature combinations, so the time it takes for the solution to generate a potentially optimal output is essential.
The objective of the proposed solution2 is to perform a model transformation from the initial Responsibility Dependency Graph received as input into a Class Diagram which attempts to achieve the highest possible CRAIndex by having as high cohesion and as low coupling as possible.
The meta-model transformation relies in linking each feature (method or attribute) to a class that encapsulates it, as shown in Figure 1. At the beginning of this project, the idea of using Microsoft Excel as the main part of the transformation was merely a result of the developer's working experience with Visual Basic in di erent elds of the industry. However, since the moment we found out about the Markov Clustering Algorithm and its use within matrix/graph operations, Excel naturally started to sound more and more convenient. Additionally, since matrices are worked upon the actual spreadsheet, the debugging of the algorithm as well as further experimentation with it became signi cantly easier. The tool is highly transparent, very easy to use, requires little to no technology stack at all (for Windows users, that is) and its transformation process, described in the following section, is relatively simple. 3
The implementation starts o with a pre-processing step that transforms the input le into meaningful data that will shortly after be used in order to generate the classes. The results are nally formatted as an .xmi le for further use. Several inputs have been tested for the competition, however Input A (the smallest one) will be the one used as an example in this section.
Select features with high affinity Update matrix Transform RDG into matrix
Measure affinity Matrix transformations The rst step in the process is importing the Responsibility Diagram and parsing it in order to harvest the available features and existing relationships between them.
A matrix of size ( + ) is generated, where is the number of methods and is the number Table 1 Associate Matrix for Input A - First Step of attributes. The matrix will be lled with 0, 1 or 2 which represents the type of relationship be- Methods Attributes tween two particular features (no relationship, uni- 0 1 2 3 4 5 6 7 8 directional and bi-directional respectively). This 0 1 0 1 0 0 0 0 1 1 value will be referred to as . The result after this 1 1 1 0 2 0 0 1 1 0 step for Input A is shown in Table 1. In the exam- 2 0 0 1 1 1 0 0 0 0 ple, relationships for each method with itself will be 3 1 2 0 1 0 1 0 1 0 1 but this can vary depending on certain properties (this concept is explained further under section 4). Table 2 Associate Matrix for Input A - Second Step
The distinction between uni- and bi-directional relationships in the associate matrix is the rst Methods Attributes di erence from the classic Markov Clustering Al- 0 1 2 3 4 5 6 7 8 gorithm implementation, which contemplates bi- 0 1,4 0,2 1,1 0,2 0 0 0 1 1 directional links only. 1 1,2 1,5 0,1 2,4 0 0 1 1 0
In the next step, the algorithm analyzes the simi- 2 0,1 0,1 1,3 1,1 1 0 0 0 0 larities between each pair of methods by counting 3 1,2 2,4 0,1 1,5 0 1 0 1 0 how many features they share relationships with (both values should be > 0 to be counted). In the example, methods 1 and 3 have four features in common (0, 1, 3 and 7). Each value will be calculated for every pair of methods and placed next to each cell value separated by a comma, and will be referred to as . This newly calculated value is arguably one of the most important across the entire algorithm, as it directly related to the stregth of the relationship between two given methods. As a result, values in each cell will correspond to , as shown in Table 2. Attribute values will remain unchanged in this step.
Shortly after, a new value will be calculated on each of the recently modi ed cells. This calculation, as well as the use of the diagonal will vary depending on various properties associated with the initial Responsibility Dependency Graph. This is explained more in depth in section 4.
However, in this case the a nity index ( ) will be de ned as = . Results for this example can be found in table 3. 3.2
Class Generation In order to achieve the last step of the algorithm and calculations will be performed: nally get to the resulting class diagram, the following 1. Sum total for each method row, showing which method has the most/strongest relationships. 2. Maximum a nity index -calculated previously- for each method column, showing which pair has the strongest relationship. 3. Sum total for each attribute column, showing by how many methods each attribute is used.
From here on, we start by choosing the rst row with the highest row total. If the matrix exceeds a speci ed threshold in the number of methods, values in this row will be slightly increased in order to simulate the generation of a superclass or \leading" class, but in the example shown values will remain the same.
For each method column in the row selected before, we check if the a nity index is equal to the previously calculated maximum. If the values are Table 3 Associate Matrix for Input A - Third Step the same, we store that method in an array in order to group them together in the class generation step. In the example, the rst row selected will be Method 1 (with 14 as row sum), and the only candidate method will be itself. This attempts to ensure the highest possible cohesion within all method-to-method relationships.
After that we move on to the grouping of attributes to be put within the same class. In order to do so, we calculate the sum total of each attribute column but only for the methods previously selected. If the sum is equal to or greater than 50 percent of the column total, that attribute will be selected since the majority of methods that use it are candidates for the newly generated class. If the sum is less than 50 percent that means the attribute will produce higher cohesion placed in a di erent class. For Method 1, attribute 6 will be grouped with it since 1 0:5 1, but attribute 7 will not since 1 < 0:5 3.
Methods and attributes selected in the last section will be placed in a newly created class. In order to prevent other classes from re-using them in the future, column values for each attribute and row/column values for each method will be set to zero. This process will go on generating classes by grouping methods and attributes until values on all cells are zero.
After wrapping up the last set of features within a class, the solution will transform the class diagram into a .xmi le with the correct formatting and store it within the same le-path as the input. 4
When analyzing and processing a nity indexes, values shown in the diagonal are often (such as in the example shown in this paper) necessary in order to generate a class diagram that carries a high CRA-index. However, in some cases it has been proven to be misleading and therefore largely increasing the overall coupling of the output.
For this reason, it has been determined the need to establish a threshold within the number of methods required in order to deem the diagonal counter-productive. For our solution, every time the input exceeds 12 methods the values in the diagonal will become zero. This threshold is not completely precise and might be re ned after further experimentation.
Furthermore, for inputs in which the number of methods is < 12 the diagonal might require to be turned to zero as well for very speci c cases (such as having less attributes than methods and thus requiring multiple methods to be put together in order to increase the cohesion). This avoids methods to be isolated and being grouped up only with the attributes they make use of.
When it comes to calculating the A nity Index , several di erent heuristics using both and have been tested (such as + ; 2 + , etc.) but the best results have been obtained by using simply = .
Another concept introduced in this algorithm is the generation of a main or leading class which contains the majority of the methods/attributes, while keeping the overall strongest relationships between features in the associate matrix to classes other than the main one. This is a means to represent the way in which developers generally build class diagrams when illustrating real-life schemes, having one class that contains a large number of methods and attributes (i.e. class Person/Student/Employee, class Product/Furniture/Vehicle, etc.) as well as a few other classes that provide functionality, usability or additional relevant information. 5
The results obtained by the proposed solution can be found below:
D E F G
Proposed Excel Solution4 CRA-Index Execution Time 3.0 0,46 sec. 2.99999999 1,13 sec. 0.64803921 1,92 sec. -0.2913547 7,54 sec. 0.21916410 21,83 sec. 1.92302499 2 min. 46 sec. -0.0343154 37 min. 42 sec.
CRA-Index Execution Time
3.0 4 min. 03 sec.
1.125 5 min. 05 sec. -5.63571428 12 min. 02 sec. -23.6338095 26 min. 51 sec. -69.65545274 38 min. 08 sec.
Unknown Unknown Unknown Unknown 4Executions have been performed on a Lenovo Y50 notebook running Windows 8 x64, i5 4210H @ 2.90GHz, 8.00GB
which can be later used for visualization through \Initialize ecore diagram diagram le" feature in Eclipse. Figure 3 shows the class diagram for the output produced for Input A.
The proposed solution can be executed in a remote server through a Powershell prompt, allowing users to provide an input le and transform it into an output .xmi le or an ecore model. 7
the CRA problem. Recently, meta-heuristic optimization techniques such as Genetic Algorithm (GA), Hill Climbing (HC), Simulated Annealing (SA), Particle Swarm Optimization (PSO) have been analyzed by many research groups [E07]. Multiobjective genetic algorithm (MOGA) is another technique that has been used to solve the Class Responsibility Assignment Case [BBL10] [MJ14]. 8
Although the Markov Clustering Algorithm has been proven to be exceptionally useful for nding strongly connected components within bi-directional, un-weighted graphs, a classic implementation of this algorithm is not enough to completely cover the problem analyzed in this paper. Originally this algorithm merely compares similarities between features (which belong to an unique type), and expands the variables until they're stable enough to point out the clusters found in the graph. In-depth explanation of this algorithm can be found in its very own author's paper [SVD00].
Without the adjustments proposed in this paper, but speci cally those described under section 4, Excel would simply return poorly generated class diagrams and the resulting CRA-index would be considerably lower.
When it comes to resulting CRA values, they're closely comparable to those obtained by other solutions in the competition, being located under highly accurate transformation tools such as VIATRA or Henshin. However these solutions are based on space-exploration strategies and genetic algorithms respectively, and therefore their execution time is signi cantly higher as they require to wander through several solutions and compare them afterwards.
Even though the results obtained are somewhat respectable, there still exists a gap between the class diagrams generated and the overall optimal class diagram for each input, which remains yet undisclosed. This gap could be lled by re ning the proposed techniques, establishing new thresholds or simply adding new variables that could help achieve higher CRA-indexes. [SVD00] S. M. van Dongen. Graph Clustering by Flow Simulation. 2000. [KM09] K. Macropol. Clustering on Graphs: The Markov Clustering Algorithm. 2009.
A. P. Engelbrecht. Computational Intelligence: An Introduction, 2nd ed. John Willey & Sons. 2007 [MJ14]
H. Masoud, S. Jalili. A clustering-based model for class responsibility assignment problem in objectoriented analysis in Journal of Systems and Software, volume 93, pp. 110-131, 2014