# Path Generation#

Path generation consists of two parts: “how to cover?” (generators) and “what to cover?” (stop conditions).

AltWalker relies on GraphWalker to generate paths through your graph. Both use generators and stop conditions to decide how to walk through the models (directed graphs) and when the path (test sequence) is completed.

## Generators#

A generator is an algorithm that decides how to traverse a model. Different generators will generate different test sequences, and they will navigate in different ways.

Generators:

### Random#

Navigate through the models in a completely random manner, also called random walk. This algorithm selects randomly an out-edge from a vertex, and repeats the process for the next vertex.

Syntax

```random(<stop_conditions>)
```

Examples

Walk randomly until the path sequence has reached a length of 100 elements.

```random(length(100))
```

Walk randomly and never stop.

```random(never)
```

### Weighted Random#

Same as the random path generator, but will use weights when generating a path. A weight is assigned to an edge, and it represents the probability of an edge getting chosen.

Syntax

```weighted_random(<stop_conditions>)
```

Examples

Walk randomly with weights until the path sequence has reached a length of 100 elements.

```weighted_random(length(100))
```

Walk randomly with weights and never stop.

```weighted_random(never)
```

See the format for adding weights.

### Quick Random#

Tries to run the shortest path through a model. This is how the algorithm works:

1. Choose randomly an edge not yet visited.

2. Select the shortest path to that edge using Dijkstra’s algorithm.

3. Walk that path, and mark all the executed edges as visited.

4. When reaching the selected edge in step 1, start all over.

The algorithm works well for very large models, and generates reasonably short sequences.

The downside is when used in conjunction with guards, the algorithm can choose a path which is blocked by a guard.

Syntax

```quick_random(<stop_conditions>)
```

Examples

Randomly chooses an edge not visited until the path sequence has reached a length of 100 elements.

```quick_random(length(100))
```

Randomly chooses an edge not visited until the vertex coverage has reached 100%.

```quick_random(vertex_coverage(100))
```

### A Star#

Generates the shortest path to a specific vertex or edge, using the A* search algorithm.

Syntax

```a_star(<stop_conditions>)
```

Note

The A start generator must use a stop condition that names a vertex or an edge (`reached_vertex` or `reached_edge`).

Examples

Walks the shortest path to the vertex `v_name` and then stops.

```a_star(reached_vertex(v_name))
```

Walks the shortest path to the edge `e_name` and then stops.

```a_star(reached_edge(e_name))
```

## Stop Conditions#

A stop condition is responsible for deciding when a path is completed. The generator will generate a new step in the path until the stop condition is fulfilled.

Stop Conditions:

### Vertex Coverage and Edge Coverage#

Vertex coverage and edge coverage stop conditions take as arguments a percentage. The path is completed when the percentage of traversed elements is reached.

If an element is traversed more than once, it still counts as 1 when calculating the percentage coverage.

Syntax

```vertex_coverage(<percentage>)
```
```edge_coverage(<percentage>)
```

Examples

Randomly chooses an edge not visited until the vertex coverage has reached 50%.

```quick_random(vertex_coverage(50))
```

Walks randomly until the edge coverage has reached 75%.

```random(edge_coverage(75))
```

### Requirement Coverage#

This stop condition takes as an argument a percentage.

The path is completed when the percentage of traversed requirements is reached. If a requirement is traversed more than once, it still counts as 1 when calculating the percentage covered.

Syntax

```requirement_coverage(<percentage>)
```

Examples

Walks randomly until the requirements coverage has reached 25%.

```random(requirement_coverage(25))
```

See the format for adding requirements.

### Dependency Edge Coverage#

This stop conditions takes an integer as argument representing the dependency threshold.

The path is completed when all of the traversed edges with dependency higher or equal to the threshold are reached.

Syntax

```dependency_edge_coverage(<dependency_threshold>)
```

Examples

Walks randomly until all the edges with dependency higher or equal to 85 are reached.

```random(dependency_edge_coverage(85))
```

See the format for adding dependencies.

### Reached Vertex and Reached Edge#

Reached vertex and reached edge stop conditions take as argument a name of an element.

The path is completed when the element is reached.

Examples

Walks randomly until the vertex `v_name` is reached.

```random(reached_vertex(v_name))
```

Walks the shortest path to the edge `e_name` and then stops.

```a_star(reached_edge(e_name))
```

### Time Duration#

Time duration stop condition takes as argument a number of seconds, representing the time that the test generator is allowed to execute.

Please note that the time is compared with the execution for the whole test. This means that if you for example have:

• 2 models with common shared states

• both having `time_duration` stop condition set to 60 seconds

Then both models will stop executing after 60 seconds, even if one of the models have not been visited.

Warning

The `time_duration` stop condition is not allowed with `offline` mode.

Examples

Walks randomly for 500 seconds:

```random(time_duration(500))
```

### Length#

Length stop condition takes an integer as argument, representing the total numbers of edge-vertex pairs generated by a generator.

For example, if the number is 110, the test sequence would be 220 elements (110 pairs of edges and vertices).

Examples

Walks randomly until the path sequence has reached a length of 24 elements:

```random(length(24))
```

### Never#

This special stop condition will never stop the generator.

Warning

The `never` stop condition is not allowed with `offline` mode.

Examples

Walks randomly forever:

```random(never)
```

## Combining Stop Conditions#

Multiple stop conditions can be set using logical or, and, ||, &&.

Examples

Walks randomly until the edge coverage has reached 100%, or we have executed for 500 seconds.

```random(edge_coverage(100) or time_duration(500))
```

Walks randomly until the edge coverage has reached 100%, and it reached the vertex: `v_name`.

```random(reached_vertex(v_name) && edge_coverage(100))
```

## Chaining Generators#

Generators can be chained one after another.

Examples

Walks randomly until the edge coverage has reached 100% and it reached the vertex: `v_name`. Then starts walking randomly for 1 hour.

```random(reached_vertex(v_name) and edge_coverage(100)) random(time_duration(3600))
```