SICP Exercise 1.14 Plotting

113plot.py

import pygraphviz as pgv
import networkx as nx

nodeCount = 1
G = nx.DiGraph()
Ranks = {}

def countChange(amount):
    global G
    global Ranks

    l = '(count-change ' + str(amount) +')'
    G.add_node(0, label = l)
    Ranks[0] = [0]

    return cc(amount,5, 0, 1)

coins = [0,1,5,10,25,50]

def cc(amount, kinds, parent, depth):
    global nodeCount
    global G
    global Ranks

    curNode = nodeCount
    nodeCount += 1

    l = '(cc ' + str(amount) + ' ' + str(kinds) + ')'
    G.add_node(curNode, label = l)

    if depth in Ranks:
        Ranks[depth].append(curNode)
    else:
        Ranks[depth] = [curNode]

    G.add_edge(parent, curNode)

    if amount == 0:
        return 1
    if amount < 0 or kinds == 0:
        return 0
    return cc(amount, kinds-1, curNode, depth+1) + cc(amount-coins[kinds], kinds, curNode, depth+1)

print countChange(11)
print Ranks

A = nx.to_agraph(G)

for r in Ranks:
    A.add_subgraph(r, rank='same')

print A.string()
A.draw('graph.png', prog='dot')