ca.uqac.lif.ecp

Class GreedyTraceGenerator<T extends Event>

java.lang.Object

ca.uqac.lif.ecp.TraceGenerator<T>

ca.uqac.lif.ecp.GreedyTraceGenerator<T>

Type Parameters:

T - The type of event in the generated traces

Direct Known Subclasses:

GreedyAtomicStatechartGenerator, GreedyAutomatonGenerator, GreedyLtlGenerator

public abstract class GreedyTraceGenerator<T extends Event>
extends TraceGenerator<T>

Generates a test suite using a greedy algorithm. The algorithm works as follows; given integers M and N:

1. Generate N traces, each having a length randomly picked between 1 and M
2. Pick the trace that maximizes the improvement on coverage according to the specified metric
3. Repeat until compete coverage is reached and output the resulting test suite

In case complete coverage is very hard to achieve using this algorithm, a maximum number of iterations is also programmed (and usually set to a high value), in order to prevent quasi-infinite loops. When this maximum number of iterations is reached, the test suite is output even if complete coverage is not obtained.

Author:

Sylvain Hallé

Field Summary

Fields

Modifier and Type	Field and Description
protected float	m_lastCoverage The coverage obtained the last time generateTraces() was called
protected int	m_maxIterations The maximum number of iterations of the algorithm before giving up
protected CoverageMetric<T,java.lang.Float>	m_metric The coverage metric used to evaluate the generated traces
protected int	m_numCandidates The number of candidate traces to generate at each pass
protected java.util.Random	m_random The random number generator used to generate the traces

Constructor Summary

Constructors

Constructor and Description
GreedyTraceGenerator(java.util.Random random, CoverageMetric<T,java.lang.Float> metric)

Method Summary

Modifier and Type	Method and Description
abstract Trace<T>	generateTrace(int length) Randomly generates a trace of given length
TestSuite<T>	generateTraces() Generates a set of traces
float	getLastCoverage() Gets the coverage obtained the last time generateTraces() was called
int	pickLength() Chooses a length for a trace to be generated
void	setMaxIterations(int iterations) Sets the maximum number of iterations of the algorithm before giving up

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

m_random

protected final java.util.Random m_random

The random number generator used to generate the traces

m_metric

protected final CoverageMetric<T extends Event,java.lang.Float> m_metric

The coverage metric used to evaluate the generated traces

m_numCandidates

protected int m_numCandidates

The number of candidate traces to generate at each pass

m_maxIterations

protected int m_maxIterations

The maximum number of iterations of the algorithm before giving up

m_lastCoverage

protected float m_lastCoverage

The coverage obtained the last time generateTraces() was called

Constructor Detail

GreedyTraceGenerator

public GreedyTraceGenerator(java.util.Random random,
                            CoverageMetric<T,java.lang.Float> metric)

Method Detail

setMaxIterations

public void setMaxIterations(int iterations)

Sets the maximum number of iterations of the algorithm before giving up

Parameters:

iterations - The number of iterations

getLastCoverage

public float getLastCoverage()

Gets the coverage obtained the last time generateTraces() was called

Returns:

The coverage, -1 if the method has not been called yet

generateTraces

public TestSuite<T> generateTraces()

Description copied from class: TraceGenerator

Generates a set of traces

Specified by:

generateTraces in class TraceGenerator<T extends Event>

Returns:

The set of traces

pickLength

public int pickLength()

Chooses a length for a trace to be generated

Returns:

The length

generateTrace

public abstract Trace<T> generateTrace(int length)

Randomly generates a trace of given length

Parameters:

length - The length

Returns:

The trace, or null if no trace could be generated