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. Herewidth
andheight
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 listX
, indexed from zero, as an array# y indexes X
: visualise the Python inti
as an index into arrayX
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
visualiseshd
(anode
) as a linked list head pointer.# p points into hd
visualisesp
(anode
) as a node pointer into the linked list whose head ishd
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])