How to use a dictionary of dictionaries as output from Python?

Question

This function is driving me insane!

def CCAD1 (tree)
    leaves = []
    for otu in tree:
        if tree[otu][2]== None and tree[otu][1]== None:
                leaves += [otu]
    ccad = {}
    for leaf in leaves:
            otuX = leaf
            otu1 = leaf
            for leaf2 in leaves:
                otuY = leaf2
                otu2 = leaf2
                while tree[otu1][0] is not None and tree[otu2][0] is not None and tree[otu1][0][0] != tree[otu2][0][0]:
                        otu1,otu2,tree = tree[otu1][0][0],tree[otu2][0][0],tree
                if tree[otu1][0] is not None:
                    ccad[otuX] = {otuY:tree[otu1][0]}
    return ccad

This is the input to the function

{'A': [('AD', 4.0), None, None], 'C': [('ADBFGC', 14.5), None, None], 'B': [('BF', 0.5), None, None], 'E': [('ADBFGCE', 17.0), None, None], 'D': [('AD', 4.0), None, None], 'G': [('BFG', 6.25), None, None], 'F': [('BF', 0.5), None, None], 'ADBFG': [('ADBFGC', 6.25), ('AD', 4.25), ('BFG', 2.0)], 'BF': [('BFG', 5.75), ('B', 0.5), ('F', 0.5)], 'ADBFGC': [('ADBFGCE', 2.5), ('ADBFG', 6.25), ('C', 14.5)], 'ADBFGCE': [None, ('ADBFGC', 2.5), ('E', 17.0)], 'BFG': [('ADBFG', 2.0), ('BF', 5.75), ('G', 6.25)], 'AD': [('ADBFG', 4.25), ('A', 4.0), ('D', 4.0)]}

The output should be in the structure of something like {"A":{"B":("AB",4)}}, in the code above this is the dictionary 'CCAD'. I've literally been trying all night to do it but it's not working and I have no idea why.

Basically what I'm trying to do is to build a function that will output a dictionary of dictionaries where for each distinct pair of elements in the list leaves it will calculate an ancestor (I got some great help calculating that previously here) along with the distance, which in that link there would be a matter of keeping a running total each time the function iterates.

It's outputting a dictionary of dictionaries like I need, but it's not doing it for every pair, only certain ones. The 'tree' data structure is in that link too if you need to see it.

Any help is appreciated, I'm getting pretty desperate at this stage :/

The fix of this function is a too localized request. You should ask about a problem that you're facing. Please read the faq. — Rik Poggi
– Rik Poggi, Commented Apr 3, 2012 at 8:27
on this line: otu1,otu2,tree = tree[otu1][0][0],tree[otu2][0][0],tree you are redefining tree as the same object. It is either an error or a useless assignement — Simon Bergot
– Simon Bergot, Commented Apr 3, 2012 at 8:32
Sorry guys, I'll rephrase it all in a minute, please check again. Sorry again, this has me extremely frustrated — TheFoxx
– TheFoxx, Commented Apr 3, 2012 at 8:42

MattH · Accepted Answer · 2012-04-03 09:25:23Z

Okay, I think you want to calculate the distances between every leaf node. So I'm having a go at solving your problem, not answering your question.

Your commonAncestor algorithm is flawed as it assumes that the leaf nodes are all at the same depth. They are not.

The first solution that springs to mind is to determine all of the leaf nodes and calculate the path to the root node for each of them. Determine the closest common ancestor by comparing both paths in reverse.

The output from this is a dictionary of pairs of nodes and the number of hops between them.

from itertools import combinations

data = {'A': [('AD', 4.0), None, None], 'C': [('ADBFGC', 14.5), None, None], 'B': [('BF', 0.5), None, None], 'E': [('ADBFGCE', 17.0), None, None], 'D': [('AD', 4.0), None, None], 'G': [('BFG', 6.25), None, None], 'F': [('BF', 0.5), None, None], 'ADBFG': [('ADBFGC', 6.25), ('AD', 4.25), ('BFG', 2.0)], 'BF': [('BFG', 5.75), ('B', 0.5), ('F', 0.5)], 'ADBFGC': [('ADBFGCE', 2.5), ('ADBFG', 6.25), ('C', 14.5)], 'ADBFGCE': [None, ('ADBFGC', 2.5), ('E', 17.0)], 'BFG': [('ADBFG', 2.0), ('BF', 5.75), ('G', 6.25)], 'AD': [('ADBFG', 4.25), ('A', 4.0), ('D', 4.0)]}

def get_path(tree,leaf):
  path = []
  location = leaf
  while True:
    path.append(location)
    parent = tree.get(location)[0]
    if parent:
      location = parent[0]
    else:
      break
  return path

def get_leaves(tree):
  return [ x for (x,y) in tree.items() if y[1] is None and y[2] is None ]

def leafDistances(tree):
  paths = {}
  leaves = get_leaves(tree)
  for leaf in leaves:
    paths[leaf] = get_path(tree,leaf)
  results = {}
  for l1,l2 in combinations(leaves,2):
    commonAncestor = [ x for (x,y) in zip(paths[l1][::-1],paths[l2][::-1]) if x == y ][-1]
    distance = paths[l1].index(commonAncestor) + paths[l2].index(commonAncestor)
    results[(l1,l2)] = distance
    print "%s <-> %s Ancestor == %s, distance == %s\nPath of %s == %s\nPath of %s == %s" % (l1,l2,commonAncestor,distance,l1,paths[l1],l2,paths[l2])
  return results

leafDistances(data)

This prints out for clarity:

A <-> C Ancestor == ADBFGC, distance == 4
Path of A == ['A', 'AD', 'ADBFG', 'ADBFGC', 'ADBFGCE']
Path of C == ['C', 'ADBFGC', 'ADBFGCE']
A <-> B Ancestor == ADBFG, distance == 5
Path of A == ['A', 'AD', 'ADBFG', 'ADBFGC', 'ADBFGCE']
Path of B == ['B', 'BF', 'BFG', 'ADBFG', 'ADBFGC', 'ADBFGCE']
A <-> E Ancestor == ADBFGCE, distance == 5
Path of A == ['A', 'AD', 'ADBFG', 'ADBFGC', 'ADBFGCE']
Path of E == ['E', 'ADBFGCE']
A <-> D Ancestor == AD, distance == 2
Path of A == ['A', 'AD', 'ADBFG', 'ADBFGC', 'ADBFGCE']
Path of D == ['D', 'AD', 'ADBFG', 'ADBFGC', 'ADBFGCE']
A <-> G Ancestor == ADBFG, distance == 4
Path of A == ['A', 'AD', 'ADBFG', 'ADBFGC', 'ADBFGCE']
Path of G == ['G', 'BFG', 'ADBFG', 'ADBFGC', 'ADBFGCE']
A <-> F Ancestor == ADBFG, distance == 5
Path of A == ['A', 'AD', 'ADBFG', 'ADBFGC', 'ADBFGCE']
Path of F == ['F', 'BF', 'BFG', 'ADBFG', 'ADBFGC', 'ADBFGCE']
C <-> B Ancestor == ADBFGC, distance == 5
Path of C == ['C', 'ADBFGC', 'ADBFGCE']
Path of B == ['B', 'BF', 'BFG', 'ADBFG', 'ADBFGC', 'ADBFGCE']
C <-> E Ancestor == ADBFGCE, distance == 3
Path of C == ['C', 'ADBFGC', 'ADBFGCE']
Path of E == ['E', 'ADBFGCE']
C <-> D Ancestor == ADBFGC, distance == 4
Path of C == ['C', 'ADBFGC', 'ADBFGCE']
Path of D == ['D', 'AD', 'ADBFG', 'ADBFGC', 'ADBFGCE']
C <-> G Ancestor == ADBFGC, distance == 4
Path of C == ['C', 'ADBFGC', 'ADBFGCE']
Path of G == ['G', 'BFG', 'ADBFG', 'ADBFGC', 'ADBFGCE']
C <-> F Ancestor == ADBFGC, distance == 5
Path of C == ['C', 'ADBFGC', 'ADBFGCE']
Path of F == ['F', 'BF', 'BFG', 'ADBFG', 'ADBFGC', 'ADBFGCE']
B <-> E Ancestor == ADBFGCE, distance == 6
Path of B == ['B', 'BF', 'BFG', 'ADBFG', 'ADBFGC', 'ADBFGCE']
Path of E == ['E', 'ADBFGCE']
B <-> D Ancestor == ADBFG, distance == 5
Path of B == ['B', 'BF', 'BFG', 'ADBFG', 'ADBFGC', 'ADBFGCE']
Path of D == ['D', 'AD', 'ADBFG', 'ADBFGC', 'ADBFGCE']
B <-> G Ancestor == BFG, distance == 3
Path of B == ['B', 'BF', 'BFG', 'ADBFG', 'ADBFGC', 'ADBFGCE']
Path of G == ['G', 'BFG', 'ADBFG', 'ADBFGC', 'ADBFGCE']
B <-> F Ancestor == BF, distance == 2
Path of B == ['B', 'BF', 'BFG', 'ADBFG', 'ADBFGC', 'ADBFGCE']
Path of F == ['F', 'BF', 'BFG', 'ADBFG', 'ADBFGC', 'ADBFGCE']
E <-> D Ancestor == ADBFGCE, distance == 5
Path of E == ['E', 'ADBFGCE']
Path of D == ['D', 'AD', 'ADBFG', 'ADBFGC', 'ADBFGCE']
E <-> G Ancestor == ADBFGCE, distance == 5
Path of E == ['E', 'ADBFGCE']
Path of G == ['G', 'BFG', 'ADBFG', 'ADBFGC', 'ADBFGCE']
E <-> F Ancestor == ADBFGCE, distance == 6
Path of E == ['E', 'ADBFGCE']
Path of F == ['F', 'BF', 'BFG', 'ADBFG', 'ADBFGC', 'ADBFGCE']
D <-> G Ancestor == ADBFG, distance == 4
Path of D == ['D', 'AD', 'ADBFG', 'ADBFGC', 'ADBFGCE']
Path of G == ['G', 'BFG', 'ADBFG', 'ADBFGC', 'ADBFGCE']
D <-> F Ancestor == ADBFG, distance == 5
Path of D == ['D', 'AD', 'ADBFG', 'ADBFGC', 'ADBFGCE']
Path of F == ['F', 'BF', 'BFG', 'ADBFG', 'ADBFGC', 'ADBFGCE']
G <-> F Ancestor == BFG, distance == 3
Path of G == ['G', 'BFG', 'ADBFG', 'ADBFGC', 'ADBFGCE']
Path of F == ['F', 'BF', 'BFG', 'ADBFG', 'ADBFGC', 'ADBFGCE']

Wow, you put in a lot of work. Thanks, I'll run through this now and let you know how I get on.
Glad this was helpful to you. If you have huge datasets, then there are probably more efficient algorithms you could use. I was just aiming for functional.

Mihai · Accepted Answer · 2012-04-03 08:56:13Z

2

Since you did not give the desired output it's quite hard to debug the code, but I have a feeling that the last if condition should be under the while.

answered Apr 3, 2012 at 8:56

Mihai

2,1652 gold badges15 silver badges16 bronze badges

3 Comments

TheFoxx Over a year ago

Thanks, I didn't put in the final return statement at the end of the code. If you wouldn't mind having another look? Sorry again

Simon Bergot Over a year ago

since tree is not modified by this block it would be an infinite loop wouldn't it?

TheFoxx Over a year ago

Well the whole point of the function is to extract certain information from 'tree' not to change it.

Collectives™ on Stack Overflow

How to use a dictionary of dictionaries as output from Python?

2 Answers 2

2 Comments

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related