Coursetree Prerequisites
While working on the tree part of the coursetree project, I ran into the question of how to display the course dependencies. I have written a recursive function that returns a recursive list of course prerequisites:
I wanted to turn it into a diagram of course prerequisites and decided 2 flat lists could retain the data:
- a list for the levels
- a list for connections between courses
For example,
would translate to
and
Separating the Levels
We start off with a recursive list representing the tree structure:
To tackle the problem, I first solved a similar one: flattening a list.
This can easily be done in Scheme, as syntax and type declarations do not get in the way.
(cond ((null? sequence) '()) ; simplest case: ()
((list? (car sequence)) ; a list in front: ((1) ...)
(append (flatten (car sequence))
(flatten (cdr sequence))))
(else (cons (car sequence) ; an atom in front: (1 ...)
(flatten (cdr sequence))))))
> (flatten '(1 (2 3)))
(list 1 2 3)
Here’s the same code translated into Python:
cdr = lambda lst: lst[1:]
def flatten(seq):
if not seq:
return list()
elif isinstance(car(seq), list):
return flatten(car(seq)).extend(flatten(cdr(seq)))
else:
return [car(seq), flatten(cdr(seq))]
Unfortunately, flatten in Python produces a hypernested structure for flat lists, as (1 2 3) in Scheme is equibalent to (cons 1 (cons 2 (cons 3 empty))) or (1 . (2 . 3)).
[1, [2, [3, []]]]
The more serious problem is that it exposes a quirk in Python:
>>>
Yes, that means the list disappears after being extended with an empty list . . . one of those unpleasant surprises.
So let’s redefine a flat list in Python:
result = []
for node in tree:
if isinstance(node, list):
result.extend(flatten(node))
else:
result.append(node)
return result
>>> flatten([1,2,3])
[1,2,3]
>>> flatten([1,[2,3]])
[1,2,3]
There is a similarity between this approach and the recursive one: different actions are taken for a list node and other nodes. I used a combined functional and imperative approach to solve the problem:
cdr = lambda lst: lst[1:]
'''
depth: returns the maximum nesting level of a list
Given:
ls, a list
Result:
an integer
'''
def depth(ls):
if not ls:
return 0
elif isinstance(car(ls),list):
return max(depth(car(ls))+1,depth(cdr(ls)))
else:
return max(1,depth(cdr(ls)))
'''
strip: returns the list elements of a list
Given:
ls, a list
Result:
ls, the modified list
'''
def strip(ls, top):
if top:
for item in top:
if item in ls:
ls.remove(item)
elif cdr(ls):
ls = car(ls) + strip(cdr(ls), top) # case like [[1], ...]
else:
ls = car(ls) # case like [[1]]
return ls
'''
level: returns the top level elements of a list
Given:
ls, a list
Result:
a new list
'''
def level(ls):
if not ls:
return []
elif not isinstance(car(ls),list):
return [car(ls)] + level(cdr(ls))
else:
return level(cdr(ls))
'''
levelize: returns a list of lists, each list is contains the items of a level
Given:
ls, a list
Result:
a new list
'''
def levelize(ls):
result = []
a = list(ls)
for i in range(2*depth(ls)):
if not i%2:
result.append(level(a))
a = strip(a, level(a))
return result
>>> levelize([1,[2,6,[3,5,[4,[]],[]],[7,[]]]])
[[1], [2, 6], [3, 5, 7], [4]]
Connecting the Nodes
We start off with a recursive list representing the tree structure, slightly different from the list for separating the levels:
Again, a mix of recursion and iteration easily solves the problem:
pair: returns a list of lists, each list has an odd and even pair
Given:
ls, a list
Result:
a list
'''
def pair(ls):
result = []
while ls:
result.append(ls[0:2])
ls = ls[2:]
return result
'''
connect: returns a list of tuples, each tuple represents an edge of the graph
Given:
ls, a list
Result:
a list of tuples
'''
def connect(ls):
result = []
if cdr(ls):
if cdr(cdr(ls)):
for item in pair(ls):
result.extend(connect(item))
else:
second = car(cdr(ls))
for item in level(second):
result.append((car(ls),item))
result.extend(connect(second))
return result
>>> connect([1,[2,[3,[4],5],6,[7]]])
[(1, 2), (1, 6), (2, 3), (2, 5), (3, 4), (6, 7)]
Hopefully, you’ve had fun reading this article and meanwhile came up with a better way to represent the tree as a flat structure.