This paper describes the SDMLib solution to the Class Responsibility Assignment Case for TTC2016. SDMLib provides reachability graph computation ala Groove. Thus, the simple idea was to provide rules for possible clustering operations and then use the reachability graph computation to generate all possible clusterings. Then, we apply the CRAIndex computation to each generated clustering and identify the best clustering. Of course, this runs into scalability problems, very soon. Thus, we extended our reachability graph computation to do an A* based search space exploration. Therefore, we passed the CRAIndex computation as a metric to our reachability graph computation and in each step, we consider the set of not yet expanded graphs and choose the one, that has the best metric value for expansion. The paper reports about the results we achieved with this approach.
Copyright c by the paper's authors. Copying permitted for private and academic purposes. in addition we are able to investigate all intermediate results in order to identify which paths through the search space are the most interesting ones. The drawback of this approach is that it wastes a lot of runtime and memory space for copying the whole class model graph each time a rule is applied and for the search of already known isomorphic copies of the generated graphs. As shown in the case description, the number of possible clusterings grows with the Bell number, i.e. for larger examples a complete enumeration of all possible clustering is not possible in a meaningful time. As only a small fraction of the search space can be explored, it might be helpful to be able to investigate all intermediate states to identify the most promising spots for further expansion. Thus, we hope that the exibility provided by the SDMLib reachability graphs to investigate di erent intermediate states pays o , in the end.
As it is usually not possible to generate the whole reachability graph for a given example, our reachability graph computation may be restricted to a maximum number of reachable states to be generated. Next, we have extended our reachability graph computation with an A* like search space exploration that takes a metric as parameter and at each step chooses the state with the best metric value for expansion. We have developed two variants of this A* algorithm which will be discussed below.
The next section introduces the rules we use to solve the Class Responsibility Assignment Case and then Section 3 shows the di erent search strategies we use in this example. Finally, Section 4 shows our performance measurements. 2
Our feature clustering approach uses two SDMLib model transformation rules. In the preparation phase we use the rule shown in Figure 1 to create one class for each feature in our class model.
This rule starts by matching the pattern object c1 to the ClassModel object passed as parameter. Then, f2 is matched to a Feature object attached to this ClassModel object. The fallMatchesg constraint causes the rule to be applied to all possible matches. Thus, for each Feature object in our current ClassModel, the <<create>> sterotype on pattern object c3 causes the creation of a new Class object. In addition the new Class object is attached to the ClassModel via a classes link and to the Feature object via an encapsulates link. Finally, the new Class object's name attribute gets assigned the concatenation of the pre x "Class4" and the name of the current Feature. Thus, after the execution of this rule, each feature has its own class containing just this feature. This class model is then used as starting point for the repetitive application of our clustering rule.
Our clustering rule merges classes along functional or data dependencies, cf. Figure 2. The matching of this rule starts with the ClassModel object which is bound to c1 at rule invocation. Then we follow a classes edge to nd a match for c2, i.e. a Class object in our ClassModel. Next, we follow an encapsulates edge to match a Method object m4 contained in c2. The object matched by m4 must have a dataDependency edge or a functionalDependency edge to a Feature object matched by the pattern object f5. This Feature object in turn must be contained in a Class matched by c6. By default, SDMLib allows homomorphic matches, thus c2 and c6 would be allowed to match the same Class object. Via the fmatchOtherThen c2g clause, we enforce isomorphic matching, i.e. c2 and c6 must match two di erent Class objects. Finally, the Class matched by c6 must belong to our ClassModel c1. When such a match is found, the subpattern containing the FeaturePO pattern object f7 is executed on all possible matches. Pattern object f7 matches for all features contained in the Class matched by c6. (Note, f7 exploits homomorphic matching and will c2 : ClassPO
classes isEncapsulatedBy << create>>
dataDependency or functionalDependency f5 : FeaturePO also match the Feature object already matched by f5.) For each Feature object, the encapsulates edge connecting it to the Class matched by c6 is deleted and a new isEncapsulatedBy edge connecting it to the Class matched by c2 is created. After transferring all features to the Class matched by c2, the Class matched by c6 is destroyed. Thus, the rule shown in Figure 2 merges two classes that are connected via a feature dependency into one class.
Our clustering rule merges classes only if there is a dependency between them. This already utilizes application speci c knowledge about our CRAIndex metric. Our search space expansion will start with classes containing only one feature each. Merging classes without a dependency between them is not going to improve the CRAIndex of the resulting class model. Merging classes has the potential to improve the CRAIndex only if the classes contain features that depend on each other. Thus, our clustering rule is already optimized for the optimization of the CRAIndex. Using a di erent metric would perhaps require a more general clustering strategy. As the metric is evaluated during the search space exploration, it would be easy to simply merge any two classes, as any graphs resulting from applying a non metric improving rule would immediately be dismissed anyways. 3
At the beginning, a ReachbilityGraph object is initialized with a start graph or startState and with a set
of rules that shall be applied to the di erent reachable states. Our standard A* search space exploration
algorithm is shown in Listing 1. For the A* search space exploration, we call e.g.
rg.explore(25000, g -> CRAIndexCalculator.calculateCRAIndex((ClassModel) g));
where the rst parameter is the maximal number of states to be generated and the second parameter is the
metric function that guides our search space expansion algorithm. First, our expansion algorithm initializes
its todo list with the startState and adds the startState to a hash table of reachable states where a
graph certificate is used as key, as proposed by [
Listing 1: Default A* based Search Space Expansion
Within each step, our default A search space exploration strategy generates all successors of the current state. For case E there are about 400 dependencies, thus, the initial state has about 400 successor states. While this number decreases by one with each rule application, the rst 100 rule applications have 350 successors on average resulting in 35000 states, which already exceeds our memory space. To improve this, we added a variant of our algorithm called Ignore Decline mode. The Ignore Decline mode improves our exploration algorithm by comparing the metric value of the newState with the current bestMetric. If the metric of the newState is lower then the bestMetric we ignore the newState, i.e. we do not add it to our reachability graph nor to our todo list. This may exclude some important candidates from later consideration but it reduces the number of states to be added to our reachability graph considerably thus reducing memory space consumption.
The second variant of our search space exploration algorithm is called Promote Improvements mode. The Promote Improvement mode computes the metric for each new state and in case of an improvement compared to the current state, we stop the expansion of the current state (putting it back into the todo list). Then we jump back to line 6 and start with a new iteration, i.e. we sort the todo list (bringing the new best state to the front) and continue the search space exploration with this new state. The Promote Improvement mode reaches local optima of the reachability graph very fast. Note, when the search is exhausted for some state and we go back to earlier states, rule application on those earlier states will rst produce the same matches as in earlier runs. These same old matches will be identi ed by line 11 as isoOldStates and thus ignored. However, this requires the computation of a certi cate and an isomorphism check. To avoid this e ort, our real implementation of the Promote Improvement mode stores the number of already created successors for each state and on reconsideration, this number of rule applications is directly ignored.