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
• Dependencies
• Getting Started
  • Complete Binary Search Example
• Features
  • Arrays
  • Linked Lists
  • Matrices
  • Graphs
    • Adjacency Matrices
    • Adjacency Lists
  • Binary Trees
  • Recursion
    • Depth-First Graph Traversal

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:

• Python 3
• Jupyter
• matplotlib
• networkx

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:

1. Call the clear_frames() function, which clears any previously saved animation frames (e.g., if we had already done a visualisation)
2. Run the algorithm on some inputs, to create the visualisation of its execution over those inputs. Doing so creates a series of animation frames.
3. 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])

Once Loop Reflect

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])

Once Loop Reflect

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

Features

Algovis has support for visualising various basic data structures (and therefore algorithms that operate over such structures):

• Arrays
• Linked Lists
• Matrices
• Graphs
• Binary Trees

It also has support for visualising recursion, by visualising the callstack.

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])

Once Loop Reflect