## 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:

[u'SE 112', [u'MATH 135', []]]

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,

[,[2,6],[3,5,7],]

and

[(1,2),(2,3),(2,5),(3,4),(1,6),(6,7)]

#### Separating the Levels

We start off with a recursive list representing the tree structure:

[1,[2,6,[3,5,[4,[]],[]],[7,[]]]]

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.

(define (flatten sequence)
(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:

car = lambda lst: lst
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)).

>>> flatten([1,2,3])
[1, [2, [3, []]]]

The more serious problem is that it exposes a quirk in Python:

>>> .extend([])
>>>

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:

def flatten(tree):
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:

car = lambda lst: lst
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 [, ...]
else:
ls = car(ls)  # case like []
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,[]]]])
[, [2, 6], [3, 5, 7], ]

#### Connecting the Nodes

We start off with a recursive list representing the tree structure, slightly different from the list for separating the levels:

[1,[2,[3,,5],6,]]

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,,5],6,]])
[(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.