Documentation of code

After this meeting students should:

• Understand the general structure required for documentation
• Understand how to write further markdown

Writing documentation

Discuss how we will write documentation for the tsp library we wrote in the first section.

There are 4 components for documentation:

1. Tutorial
2. How to guide
3. Reference
4. Discussion

Ask students what they think the purpose of each of these are. Ask them to discuss amongst themselves.

Say that we will address this after writing the documentation.

Writing the tutorial

Open a markdown file (in the same location as the tsp.py file) and call it README.md.

Write the following::

# TSP

A library for solving instances of the travelling sales agent problem

## Tutorial

In this tutorial we will see how to use `tsp` to solve instances of the
[Travelling Salesman Problem](https://en.wikipedia.org/wiki/Travelling_salesman_problem)

Assuming we have the following distance matrix:

```python
import numpy as np

distance_matrix = np.array(((0, 5, 2, 9), (5, 0, 3, 1), (2, 3, 0, 7), (9, 1, 7, 0)))
```

We can obtain a tour using the following:

```python
import tsp

tour = tsp.run_2_opt_algorithm(number_of_stops=4, distance_matrix=distance_matrix, iterations=1000, seed=0)
```

We can see the tour here:

```python
tour
```

This gives:

```
[0, 3, 1, 2, 0]
```

The `tsp` library includes further functionality which you can read in the
How To guides.

## How to guides

### How to obtain a basic tour

To obtain a basic tour, we use the `tsp.get_tour` function:

```python
import tsp

tsp.get_tour(number_of_stops=5)
```

This gives

```
[0, 1, 2, 3, 4, 0]
```

If we pass a random seed this will also shuffle the interior stops (in a
reproducible manner):

```python
tsp.get_tour(number_of_stops=5, seed=0)
```

This gives:

```
[0, 3, 4, 2, 1, 0]
```

### How to swap two spots

To swap two cities for a given tour, we use the `tsp.swap_cities` function:

```python
tour = [0, 1, 2, 3, 4, 5, 0]
tsp_swap_cities(tour=tour, indices=(2, 4))
```

This gives:

```
[0, 1, 4, 3, 2, 5, 0]
```

### How to get the cost of a tour

To calculate the cost of a given tour, we use the `tsp.get_cost` function:

```python
distance_matrix = np.array(((0, 5, 2, 9), (5, 0, 3, 1), (2, 3, 0, 7), (9, 1, 7, 0)))
tour = [0, 1, 2, 3, 0]
tsp.get_cost(tour=tour, distance_matrix=distance_matrix)
```

which gives:

```
24
```

### How to plot a tour

To plot a tour we use the `tsp.plot_tour` function:

```python
xs = (0, 1, 1, 2.5)
ys = (0, 5, 1, 3)
tour = [0, 1, 3, 2, 0]
tsp.plot_tour(x=xs, y=ys, tour=tour)
```

This gives the following image:

![](./how-to.svg)

### How to use the 2-opt algorithm

To run the full algorithm, we use the
`tsp.run_2_opt_algorithm` function:

```python
distance_matrix = np.array(((0, 5, 2, 9), (5, 0, 3, 1), (2, 3, 0, 7), (9, 1, 7, 0)))
tour = tsp.run_2_opt_algorithm(number_of_stops=4, distance_matrix=distance_matrix, iterations=1000, seed=0)
tour
```

This gives:

```
[0, 3, 1, 2, 0]
```

## Explanations

This software implements the 2-opt algorithm for the travelling sales agent
problem.

### The TSP

As an example, if we consider three cities with the following matrix
defining their distances between them:

$$
    \begin{pmatrix}
        0 & 4 & 1\\
        4 & 0 & 2\\
        9 & 2 & 0
    \end{pmatrix}
$$

Note that the distance matrix is not symmetric, it is a lot further to go
from the 3rd to the 1st city (9) than to go from the 1st to the 3rd (1)

If a tour starts **and** finishes at the first city there are in fact 2
possibilities:

$$T \in \{(0, 1, 2, 0), (0, 2, 1, 0)\}$$

The cost $c(t)$ for $t\in T$ of these tour tours is taken to be the total
distance travelled:

1. For $t=(0, 1, 2, 0)$ we have $c(t)=4 + 2 + 9=15$
2. For $t=(0, 2, 1, 0)$ we have $c(t)=1 + 2 + 2=5$

As the size of our problem grows the complexity of finding the optimal tour
grows in complexity. In fact this problem is NP-hard, which puts it in a
class of problems for which a general solution cannot be obtained
efficiently for any given sized problem.

## The 2-opt algorithm

One solution approach of this is the 2-opt algorithm which is what is
implemented in this software.

The 2-opt algorithm is an example of a neighbourhood search algorithm which
means that it iteratively improves a given solution by looking in
at other candidates near it.

The 2-opt algorithm does this by randomly choosing two stops in a tour, and
swapping the order between them. Essentially picking stop $n$ and stop $n +
k$ and reversing the order. Thus the new candidate would visit the same
stops as the original tour, until it got to stop $n$, when it would instead
go to stop $n + k$ and reverse its way back to stop $n$.

Once this candidate tour is obtained the cost is evaluated and if it is good
it is accepted as the new solution.

This has the effect of essentially untangling a given tour.

## Reference

### List of functionality

This software implements 5 functions:

1. `plot_tour`
2. `get_tour`
3. `swap_cities`
4. `get_cost`
5. `run_2_opt_algorithm`

### Bibliography

The wikipedia page on the TSP offers good background reading:
https://en.wikipedia.org/wiki/Travelling_salesman_problem

The following text is a recommended text on neighbourhood search algorithms:

> Aarts, Emile, Emile HL Aarts, and Jan Karel Lenstra, eds. Local search in
> combinatorial optimization. Princeton University Press, 2003.

After class communication

Send the following email after class::

Hi all,

A recording of today's class is available at <>.

In this class I went over documenting code.

In class we documented the travelling salesagent problem code
you can find a different example (studying snakes and ladders) here:
https://vknight.org/pfm/building-tools/06-documentation/tutorial/main.html

Please get in touch if I can assist with anything,
Vince