# Algovis DocumentationÂ¶

Algovis is a rudimentary tool designed to enable the interactive visualisation of simple algorithms implemented in Python, via Jupyter Notebooks.

It was created to aid teaching the introductory algorithms subject *COMP90038 - Algorithms and Complexity* at the University of Melbourne. It was created by Toby Murray (toby.murray@unimelb.edu.au) with contributions from Zongdong (Ethan) Liu.

## Table of ContentsÂ¶

## Downloading Â¶

Algovis can be obtained from github: https://github.com/tobycmurray/algovis

For instance, you can download it by running in your shell:

```
curl -O https://raw.githubusercontent.com/tobycmurray/algovis/main/algovis.py
```

## Dependencies Â¶

Algovis makes use of the following dependencies:

Assuming you are using Jupyter Lab, they can be installed via pip as follows:

```
pip install jupyterlab matplotlib networkx
```

## Getting Started Â¶

Open a new Jupyter notebook where you will write and visualise your algorithm.

Import the key functions from the `algovis`

module:

```
from algovis import snapshot, clear_frames, show_animation
```

Now define your algorithm that you wish to visualise. Let's use a simple binary search implementation as an example:

```
# search for the 'key' within array 'A' between indices 'lo' and 'hi' inclusive
# returns the index of 'key' within 'A' if it is found and -1 otherwise
# precondition: [lo,..,hi] are all valid indices of 'A'
def binsearch(A,lo,hi,key):
while lo <= hi:
mid = int(hi - ((hi - lo)/2))
if A[mid] == key:
return mid
elif A[mid] < key:
lo = mid+1
else:
hi = mid-1
# didn't find it
return -1
```

Algovis works by running the algorithm to create a visualisation. The programmer inserts calls to the `snapshot()`

function *within the algorithm being visualised* to create animation frames ("snapshots") for the visualisation. This means that the programmer has complete control over the granularity of the visualisation. (They also have control over what information is visualised and how, see features below.)

Let's suppose we wish to visualise the state of the algorithm at the top of each loop iteration (just after it has computed `mid`

) as well as just before it returns. So we add the following `snapshot()`

call to the code above.

```
# search for the 'key' within array 'A' between indices 'lo' and 'hi' inclusive
# returns the index of 'key' within 'A' if it is found and -1 otherwise
# precondition: [lo,..,hi] are all valid indices of 'A'
def binsearch(A,lo,hi,key):
while lo <= hi:
mid = int(hi - ((hi - lo)/2))
snapshot()
if A[mid] == key:
snapshot()
return mid
elif A[mid] < key:
lo = mid+1
else:
hi = mid-1
# didn't find it
snapshot()
return -1
```

Now to create a visualisation we simply need to do three things:

- Call the
`clear_frames()`

function, which clears any previously saved animation frames (e.g., if we had already done a visualisation) - Run the algorithm on some inputs, to create the visualisation of its execution over those inputs. Doing so creates a series of animation frames.
- Call the
`show_animation([width,height])`

function to display the saved animation that was just created. Here`width`

and`height`

are the width and the height respectively of the animation pane used to render the animation. You may need to experiment to find appropriate values for your animation, depending on which Algovis features you are using.

For instance, for our binary search example we might define:

```
A = [1,4,7,10,18,22]
clear_frames()
# search for the key 4
binsearch(A,0,len(A)-1,4)
show_animation([7,5])
```

On its own this is useful, but it would be easier to understand what's going on if the visualisation made explicit that `mid`

, `lo`

, and `hi`

were indices into the array `A`

. We can add this information by adding appropriate comments to the algorithm that turn on additional visualisation features of Algovis. More are described below.

## Complete Binary Search Example Â¶

```
# search for the 'key' within array 'A' between indices 'lo' and 'hi' inclusive
# returns the index of 'key' within 'A' if it is found and -1 otherwise
# precondition: [lo,..,hi] are all valid indices of 'A'
def binsearch(A,lo,hi,key):
# A is an array, lo indexes A, hi indexes A
while lo <= hi:
mid = int(hi - ((hi - lo)/2)) # mid indexes A
snapshot()
if A[mid] == key:
snapshot()
return mid
elif A[mid] < key:
lo = mid+1
else:
hi = mid-1
# didn't find it
snapshot()
return -1
A = [1,4,7,10,18,22]
clear_frames()
# search for the key 4
binsearch(A,0,len(A)-1,4)
show_animation([7,6])
```

The visualisation now makes the purpose of the array indices (to define the array slice over which each iteration of the algorithm operates) clear.

## Arrays Â¶

### CommmentsÂ¶

`# X is an array`

: visualise the Python list`X`

, indexed from zero, as an array`# y indexes X`

: visualise the Python int`i`

as an index into array`X`

Multiple comments of each kind can be included in an algorithm.

Array visualisation is demonstrated with the binary search example above.

## Linked Lists Â¶

The linked list visualisation assumes the following simulation for linked lists in Python, which exposes the traditional `val`

field and `next`

pointer of each node.

```
class node:
def __init__(self, val, next):
self.val = val
self.next = next
def __str__(self):
return "<a node whose val is %s>" % str(self.val)
```

### CommentsÂ¶

`# hd is a linked list`

visualises`hd`

(a`node`

) as a linked list head pointer.`# p points into hd`

visualises`p`

(a`node`

) as a node pointer into the linked list whose head is`hd`

Multiple comments of each kind can be included in an algorithm.

The following simple example illustrates:

```
# returns None to simulate returning a null pointer
def find(head, value):
# head is a linked list
# p points into head
p = head
snapshot()
while p != None:
if p.val == value:
snapshot()
return p
p = p.next
snapshot()
return None
# define a simple linked list. None is the null pointer to indicate the end of the list
hd = node(2,node(3,node(5,(node(7,None)))))
clear_frames()
find(hd,5)
show_animation(size=[10,5])
```