Recursive Python Function Returns None Always

Question

So I am implementing an algorithm to prune leaf nodes from a graph before doing the heavier calculation of finding cycles within that graph. I am representing the graphs as adjacency lists, the example I will use is the graph corresponding to the carbons in methyl benzene:

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

I want to remove entries corresponding to edges that connect leaf nodes, so the edge [5,6] needs to be 'pruned' to produce this new adjacency list:

[[0, 1], [0, 2], [1, 3], [2, 4], [3, 5], [4, 5]]

The code below (Python 3.4) appears to perform this operation correctly for when I print the adjacency list within the function the output is correct. However, when I call the function and print the returned 'value' it is always None.

def prune_adj_list(adj_list):
    print(adj_list)
    all_indices = []
    for bond in adj_list:
        all_indices = all_indices + bond
    leaf_nodes = []
    for value in range(min(all_indices),max(all_indices)+1):
        if all_indices.count(value) == 1: #count how many bonds to node
            leaf_nodes.append(value)
    if len(leaf_nodes) == 0: # no leaf nodes so done
        print("done pruning")
        print(adj_list) #<- the value here is correct
        return adj_list
    else:
        new_adj_list = []
        for bond in adj_list:
            if not (leaf_nodes.count(bond[0]) > 0 or leaf_nodes.count(bond[1]) > 0):
                new_adj_list.append(bond)
        if len(new_adj_list) > 0:
            prune_adj_list(new_adj_list)
        else:
            print("pruned away entire graph")
            return []

Here is an example of a call that prints "None" instead of the correct value.

def find_cycles(compound):
    adj_list = make_adj_list(compound) # this produces the list:     [[0, 1], [0, 2], [1, 3], [2, 4], [3, 5], [4, 5], [5, 6]] 
    print(adj_list)
    print(prune_adj_list(adj_list))

Can someone explain to me why the return value is incorrect but when I print it right before the return it is correct? Also any suggestions on how to fix this? I've played with returning copies of adj_list and have tested that the code seems to perform the operation I want correctly.

Thanks in advance, if additional information is needed please let me know.

Perhaps did you mean to write `return prune_adj_list(new_adj_list) ` instead of `prune_adj_list(new_adj_list)`? — Frxstrem, May 26 '15 at 23:07
Yes, that was it. I'm not sure how I missed that but thanks. — JMM, May 26 '15 at 23:46

score 3 · Answer 1 · answered May 26 '15 at 23:10

3

Your recursive case is missing a return:

if len(new_adj_list) > 0:
    return prune_adj_list(new_adj_list)
    ^^^^^^
else:
    print "pruned away entire graph"
    return []

answered May 26 '15 at 23:10

Barry

286,269
29
621
977

Thanks, I should have caught that... it's been a long day lol. – JMM May 26 '15 at 23:45

score 1 · Answer 2 · edited May 26 '15 at 23:28

1

Can you add

return prune_adj_list(new_adj_list)

In your if condition instead of

prune_adj_list(new_adj_list)

edited May 26 '15 at 23:28

Ethan Furman

63,992
20
159
237

answered May 26 '15 at 23:14

Exception

785
8
8

Recursive Python Function Returns None Always

2 Answers2