Recursive Python Function Returns None Always [duplicate]

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)? — Freyja
– Freyja, Commented May 26, 2015 at 23:07
Yes, that was it. I'm not sure how I missed that but thanks. — JMM
– JMM, Commented May 26, 2015 at 23:46

Barry · Accepted Answer · 2015-05-26 23:10:07Z

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, 2015 at 23:10

Barry

312k33 gold badges736 silver badges1.1k bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

JMM Over a year ago

Thanks, I should have caught that... it's been a long day lol.

Ethan Furman · Accepted Answer · 2015-05-26 23:28:15Z

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, 2015 at 23:28

Ethan Furman

70.2k21 gold badges174 silver badges251 bronze badges

answered May 26, 2015 at 23:14

Exception

7858 silver badges8 bronze badges

Collectives™ on Stack Overflow

Recursive Python Function Returns None Always [duplicate]

2 Answers 2

1 Comment

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Linked

Related