# Matrix to Tree Algorithm

The code takes a matrix and turns it into a tree of all the possible combinations. It then "maps" the tree by setting the value of the ending nodes to the total distance of the nodes from beginning node to ending node.

It seems to work fairly well but I've got a couple questions:

1. Is a Python dict the best way to represent a tree?
2. Any ways to simplify, speed up, or otherwise make it more clean and legible?

Keep in mind I'll need to sort the set so I can display the most attractive routes.

You can find the code on my GitHub page (starts at line 61).

def matrix_to_tree(nodes):
"""
Creates a tree of all possible combinations of
provided nodes in dict format
"""
tree = {}
for node in nodes:
children = nodes[:]
children.remove(node)
tree[node] = matrix_to_tree(children)
return tree

def set_start(tree, start):
"""
Removes extraneous starting nodes if only one
starting location is desired.
"""
tree = tree[start]
return tree

def set_end(tree, end):
"""
Removes ending nodes when they are not the
last node of the branch.  Used when one
ending location is desired.
"""
if tree[end]:
del tree[end]
nodes = tree.keys()
if len(nodes) > 1:
for node in nodes:
set_end(tree[node], end)
return tree

def map_tree(tree, matrix, start, distance=0):
"""
Maps the distance from the root to each
ending node.
"""
for node in tree:
new_distance = distance + node_distance(matrix, start, node)
if tree[node]:
map_tree(tree[node], matrix, node, new_distance)
else:
tree[node] = new_distance
return tree

def node_distance(matrix, start, end):
"""
Searches a matrix for the value of two
points.
"""
return matrix[start][end]

nodes = [key for key in x.keys()]
a = matrix_to_tree(nodes)
b = set_start(a, 'A')
c = set_end(b, 'G')
d = map_tree(c, x, 'A')
print(d)


Input example:

{ A: {B:1, C:2}, B: {A:1, C:3}, C: {A:2, B:3}, }

Output example:

# 'A' being the root node with no ending node specified
{
A: {B:{C:4}, C:{B:5}},
}

• Even if I try to adapt the input example by adding quotes etc. I can't get the example output by running the code. Please add a runnable example. – Janne Karila Dec 3 '14 at 20:16
• @JanneKarila Name your matrix 'x' and try again. Or just use the code on GitHub. This was written for Python 3.4. – Colton Allen Dec 3 '14 at 21:39
• @ColtonAllen as A, B, C are no valid variables. Please change your example to {'A': {'B':1, 'C':2}, 'B': {'A':1, 'C':3}, 'C': {'A':2, 'B':3}}. Also your code with that input example does not yield your output example. – lummax Dec 4 '14 at 9:41

The code is clean, modular and readable. You could try to work with generators to make the calculations lazy.

I think the namedtuple are a better choice than your dict approach, something like:

Node = collections.namedtuple('Node', ['name', 'distance', 'children'])


You can look into the way a functional language like Hskell or Clojure represents trees. It is weird that you mark the leaves of your tree by empty dicts and replace them with the calculated distance.

• PEP8:

• Use 4 spaces per indentation level.
• Separate top-level function and class definitions with two blank lines.
• set_start(): Why not just return tree[start]?

• set_end():

• tree[end] can result in a KeyError
• Why the if len(nodes) > 1?

if end in tree:
del tree[end]
for child in tree.values():
set_end(child, end)
return tree

• node_distance(): This is an internal function and can be inlined in map_tree().

• Please do not place code on module level, but wrap it in a main() or test() function.

nodes = [key for key in x.keys()] can be simplified to nodes = list(x.keys()).