# Documentation¶

## First meeting¶

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:

Tutorial

How to guide

Reference

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 email¶

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
```