source: trunk/EventBenchConsole/src/de/ugoe/cs/eventbench/commands/CMDgenerateGreedy.java @ 425

Last change on this file since 425 was 395, checked in by sherbold, 13 years ago
  • optimized the run-time of the command generateGreedy. Worst-case nearly unchanged, but the average run-time has been reduced to 1/3 of the worst case.
  • The optional parameter validEnd has been added to the command generateGreedy. If the parameter is true, only sequences that end in de.ugoe.cs.eventbench.data.Event.ENDEVENT are generated. If the parameter is false, the final event is arbitrary.
  • Property svn:mime-type set to text/plain
File size: 5.6 KB
Line 
1package de.ugoe.cs.eventbench.commands;
2
3import java.security.InvalidParameterException;
4import java.util.Collection;
5import java.util.Iterator;
6import java.util.LinkedHashSet;
7import java.util.LinkedList;
8import java.util.List;
9import java.util.Map;
10import java.util.Set;
11
12import de.ugoe.cs.eventbench.CommandHelpers;
13import de.ugoe.cs.eventbench.coverage.SequenceTools;
14import de.ugoe.cs.eventbench.data.Event;
15import de.ugoe.cs.eventbench.data.GlobalDataContainer;
16import de.ugoe.cs.eventbench.models.IStochasticProcess;
17import de.ugoe.cs.util.ArrayTools;
18import de.ugoe.cs.util.console.Command;
19import de.ugoe.cs.util.console.Console;
20
21/**
22 * <p>
23 * Command to generate test suite with a greedy strategy to achieve a desired
24 * coverage.
25 * </p>
26 *
27 * @author Steffen Herbold
28 * @version 1.0
29 */
30public class CMDgenerateGreedy implements Command {
31
32        /**
33         * <p>
34         * Tolerance for double comparisons
35         * </p>
36         */
37        final static double eps = 0.000000000001;
38
39        /*
40         * (non-Javadoc)
41         *
42         * @see de.ugoe.cs.util.console.Command#run(java.util.List)
43         */
44        @Override
45        public void run(List<Object> parameters) {
46                String modelname;
47                String sequencesName;
48                int minLength;
49                int maxLength;
50                int coverageDepth;
51                float desiredCoverage;
52                boolean validEnd = true;
53                try {
54                        modelname = (String) parameters.get(0);
55                        sequencesName = (String) parameters.get(1);
56                        minLength = Integer.parseInt((String) parameters.get(2));
57                        maxLength = Integer.parseInt((String) parameters.get(3));
58                        coverageDepth = Integer.parseInt((String) parameters.get(4));
59                        desiredCoverage = Float.parseFloat((String) parameters.get(5));
60                        if (parameters.size() >= 7) {
61                                validEnd = Boolean.parseBoolean((String) parameters.get(6));
62                        }
63                } catch (Exception e) {
64                        throw new InvalidParameterException();
65                }
66
67                IStochasticProcess model = null;
68                Object dataObject = GlobalDataContainer.getInstance()
69                                .getData(modelname);
70                if (dataObject == null) {
71                        CommandHelpers.objectNotFoundMessage(modelname);
72                        return;
73                } else if (!(dataObject instanceof IStochasticProcess)) {
74                        CommandHelpers.objectNotType(modelname, "IStochasticProcess");
75                        return;
76                }
77                model = (IStochasticProcess) dataObject;
78
79                // set up everything
80                List<List<? extends Event<?>>> allSequences = new LinkedList<List<? extends Event<?>>>();
81                for (int length = minLength; length <= maxLength; length++) {
82                        if (validEnd) {
83                                allSequences.addAll(model.generateValidSequences(length + 2));
84                        } else {
85                                allSequences.addAll(model.generateSequences(length + 1, true));
86                        }
87                }
88                Console.traceln("" + allSequences.size() + " possible");
89
90                Collection<List<? extends Event<?>>> allSubSeqs = model
91                                .generateSequences(coverageDepth);
92                Map<List<? extends Event<?>>, Double> weightMap = SequenceTools
93                                .generateWeights(model, allSubSeqs);
94                Set<List<? extends Event<?>>> coveredSubSeqs = new LinkedHashSet<List<? extends Event<?>>>();
95
96                List<Set<List<? extends Event<?>>>> containedSubSeqs = new LinkedList<Set<List<? extends Event<?>>>>();
97                for (List<? extends Event<?>> sequence : allSequences) {
98                        List<List<? extends Event<?>>> wrapper = new LinkedList<List<? extends Event<?>>>();
99                        wrapper.add(sequence);
100                        Set<List<? extends Event<?>>> currentSubSeqs = SequenceTools
101                                        .containedSubSequences(wrapper, coverageDepth);
102                        containedSubSeqs.add(currentSubSeqs);
103                }
104
105                List<List<? extends Event<?>>> testSuite = new LinkedList<List<? extends Event<?>>>();
106                double currentCoverage = 0.0d;
107
108                // Build test suite
109                double prevGain = 1.0d;
110                boolean gainEqual = false;
111                while (currentCoverage < desiredCoverage) {
112                        Double[] sequenceGain = new Double[allSequences.size()];
113                        int i = 0;
114                        for (Set<List<? extends Event<?>>> containedSubSeq : containedSubSeqs) {
115                                double gain = 0.0d;
116                                Iterator<List<? extends Event<?>>> subSeqIter = containedSubSeq
117                                                .iterator();
118                                while (subSeqIter.hasNext()) {
119                                        List<? extends Event<?>> subSeq = subSeqIter.next();
120                                        if (!coveredSubSeqs.contains(subSeq)) {
121                                                gain += weightMap.get(subSeq);
122                                        } else {
123                                                subSeqIter.remove();
124                                        }
125                                }
126                                sequenceGain[i] = gain;
127                                // optimization using that the gain is monotonically decreasing
128                                if (Math.abs(gain - prevGain) <= eps) {
129                                        gainEqual = true;
130                                        break;
131                                }
132                                i++;
133                        }
134                        int maxIndex;
135                        if (gainEqual) {
136                                maxIndex = i;
137                        } else {
138                                maxIndex = ArrayTools.findMax(sequenceGain);
139                        }
140                        if (maxIndex < 0 || sequenceGain[maxIndex] <= 0.0 + eps) {
141                                Console.traceln("No gain anymore! Desired coverage cannot be satisfied!");
142                                break;
143                        }
144                        prevGain = sequenceGain[maxIndex];
145                        testSuite.add(allSequences.get(maxIndex));
146                        coveredSubSeqs.addAll(containedSubSeqs.get(maxIndex));
147                        currentCoverage += sequenceGain[maxIndex];
148                        if (gainEqual) {
149                                allSequences.remove(maxIndex);
150                                containedSubSeqs.remove(maxIndex);
151                                gainEqual = false;
152                        } else {
153                                for (int j = sequenceGain.length - 1; j >= 0; j--) {
154                                        if (j == maxIndex || sequenceGain[j] <= 0.0 + eps) {
155                                                allSequences.remove(j);
156                                                containedSubSeqs.remove(j);
157                                        }
158                                }
159                        }
160                }
161
162                if (GlobalDataContainer.getInstance().addData(sequencesName, testSuite)) {
163                        CommandHelpers.dataOverwritten(sequencesName);
164                }
165                Console.println("" + testSuite.size() + " sequences generated");
166                Console.println("" + currentCoverage + " coverage achieved");
167        }
168
169        /*
170         * (non-Javadoc)
171         *
172         * @see de.ugoe.cs.util.console.Command#help()
173         */
174        @Override
175        public void help() {
176                Console.println("generateGreedy <modelname> <sequencesName> <minLength> <maxLength> <coverageDepth> <desiredCoverage> {<validEnd>}");
177        }
178
179}
Note: See TracBrowser for help on using the repository browser.