Archive for April, 2010

Coursetree Prerequisites

Apr 05 2010 Published by under CourseTree,Programming

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,

tree
would translate to

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

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[0]
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:

>>> [1].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[0]
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:

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

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.

No responses yet