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

Matrices

Just as arrays are simulated using Python lists, matrices (two-dimensional arrays) are simulated using lists of lists.

For instance, the 2x2 matrix

+---+---+
| 5 | 7 |
+---+---+
| 3 | 4 |
+---+---+

is represented as follows:

M = [[5, 7], [3,4]]

Comments

• # X is a matrix visualises X, a list of lists, as a matrix
• # y indexes rows of X visualises y as a row index of X
• # y indexes cols of X visualises y as a column index of X

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

The following canonical example of matrix multiplication illustrates matrix visualisation.

def matrix_mul(A,B,n):
    # A is a matrix, B is a matrix, C is a matrix    
    C = [ [ 0 for i in range(n) ] for j in range(n) ]  # the zero matrix
    snapshot()

    # iterate through rows of A
    for i in range(len(A)):  # i indexes rows of A, i indexes rows of C
        # iterate through columns of B
        for j in range(len(B[0])):  # j indexes cols of B, j indexes cols of C
            # iterate through cols of A
            for k in range(len(B)): # k indexes cols of A, k indexes rows of B
                C[i][j] += A[i][k] * B[k][j]
                snapshot()    
    return C


clear_frames()
# 2x2 matrices
A = [[5, 7], [3, 4]]
B = [[8, 2], [9, 6]]
res = matrix_mul(A,B,2)
show_animation(size=[10,7])

Once Loop Reflect

Graphs

Algovis provides support for visualising graphs stored in two canonical representations: adjacency matrices and adjacency lists.

Adjacency Matrices

Adjacency matrices are simply square matrices and are represented the same way.

Comments

• X is a graph (adjacency matrix) visualises the adjacency matrix X (a list of lists of ints) as a graph.
• y indexes nodes of X annotates which node of X the int y refers to.

Multiple comments of each kind can be included in an algorithm. It is often helpful to use these comments in conjunction with those for matrices.

The following example, which simply iterates through a graph as an adjacency matrix and prints out each edge, shows these features in use.

G = [[0, 1, 0, 1],
     [1, 0, 0, 1],
     [0, 0, 0, 1],
     [1, 1, 1, 0]]

def each_edge(G):
    # G is a matrix, G is a graph (adjacency matrix)
    for u in range(len(G)): # u indexes rows of G, u indexes nodes of G
        for v in range(len(G)): # v indexes cols of G, v indexes nodes of G
            snapshot()
            if G[u][v] != 0:
                print("There is an edge from node {} to node {}".format(u,v))

clear_frames()
each_edge(G)
show_animation(size=[10,10])

There is an edge from node 0 to node 1
There is an edge from node 0 to node 3
There is an edge from node 1 to node 0
There is an edge from node 1 to node 3
There is an edge from node 2 to node 3
There is an edge from node 3 to node 0
There is an edge from node 3 to node 1
There is an edge from node 3 to node 2

Once Loop Reflect

Adjacency Lists

An adjacency list is simply an array of lists and is represented, therefore, as a list of lists.

Comments

• X is a graph (adjacency list) visualises the adjacency list X (a list of lists of ints) as a graph.
• y indexes nodes of X annotates which node of X the int y refers to.

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

The following example also simply prints out each edge of a graph as an adjacency list, and illustrates these features.

G = [[1, 3],      # edges from node 0 to nodes 1 and 3
     [0, 3],      # edges from node 1 to nodes 0 and 3
     [3],         # edge from node 2 to node 3
     [0, 1, 2]]   # edges from node 3 to nodes 0, 1 and 2


def each_edge(G):
    # G is a graph (adjacency list)
    for u in range(len(G)): # u indexes nodes of G
        for v in G[u]: # v indexes nodes of G
            msg="There is an edge from node {} to node {}".format(u,v)
            snapshot()
            print(msg)
    
    
clear_frames()
each_edge(G)
show_animation(size=[12,7])

There is an edge from node 0 to node 1
There is an edge from node 0 to node 3
There is an edge from node 1 to node 0
There is an edge from node 1 to node 3
There is an edge from node 2 to node 3
There is an edge from node 3 to node 0
There is an edge from node 3 to node 1
There is an edge from node 3 to node 2

Once Loop Reflect

Binary Trees

Algovis has some very basic and experimental support for visualising binary trees.

Similar to linked lists, Algovis assumes the following representation for binary trees, which exposes the canonical val, left and right fields of each tree node.

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Comments

• X is a tree: visualises X (a Node) as a binary tree.
• y is currently being traversed: augments the visualisation to indicate that y (a val field of a Node) is the current one of the algorithm.

The following example of recursively calculating the height of a tree illustrates.

def Height(T):
    # T is a tree
    if T is None:
        snapshot()
        return -1
    else:
        v = T.val # v is currently being traversed
        snapshot()
        return max(Height(T.left), Height(T.right)) + 1

T = Node(5,Node(3,Node(1,None,None),None),Node(6,None,None))
clear_frames()
Height(T)
show_animation(size=[8,5])

Once Loop Reflect

Recursion

The binary tree example above illustrates that visualising recursive algorithms without being able to see the callstack is challenging.

Therefore, Algovis also supports visualising the callstack. To do so, simply pass the printstack=True argument to snapshot().

For instance, we can visualise Shriram Krishnamurthi's least favourite algorithm to explain recursion: the Towers of Hanoi. We add arbitrary distinct comments (# 1 and # 2) to the two lines that make the recursive call so that we can distinguish the two calls in the callstack visualisation.

# we represent each tower as a list of disks, where each disk is an int.
# we also include with each tower a string name to aid the visualisation
def Hanoi(n, init, aux, fin): 
    snapshot(printstack=True)
    if n > 0:
        Hanoi(n - 1, init, fin, aux)  # 1
        snapshot(printstack=True)
        fin[1].append(init[1].pop())
        Hanoi(n - 1, aux, init, fin)  # 2
        snapshot(printstack=True)

# label the towers to make it easier to see which is which
init = ("left",[4, 3, 2, 1])
aux = ("middle",[])
fin = ("right",[])
clear_frames()
Hanoi(4, init, aux, fin)
print("Hanoi done. Rendering animation may take some time...")
show_animation(size=[17,5])

Hanoi done. Rendering animation may take some time...

Once Loop Reflect

Depth-First Graph Traversal

Recursive, depth-first traversal of a graph, represented as an adjacency matrix, shows many of the Algovis features working together. The following implementation is derived from that in Levitin's Introduction to the Design and Analysis of Algorithms.

def DFS(G):
    # G is a graph (adjacency matrix), G is a matrix
    global count
    mark = [0] * len(G)
    count = 0
    for v in range(len(G)): # v indexes nodes of G, v indexes rows of G
        snapshot(printstack=True)
        if mark[v] == 0:
            DFSExplore(v, G, mark)

def DFSExplore(v, G, mark):
    global count
    # G is a graph (adjacency matrix), G is a matrix
    # v indexes nodes of G, v indexes rows of G
    count = count + 1
    mark[v] = count
    for w in range(len(G)): # w indexes nodes of G, w indexes cols of G
        snapshot(printstack=True)
        if G[v][w] != 0:
            if mark[w] == 0:
                DFSExplore(w, G, mark)

clear_frames()
G = [[0, 1, 0, 1],
     [1, 0, 0, 1],
     [0, 0, 0, 1],
     [1, 1, 1, 0]]
DFS(G)
show_animation(size=[14,14])

Once Loop Reflect