Matrix to Tree Algorithm

Question

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}},
}

• Janne Karila: 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.
• Colton Allen: @JanneKarila Name your matrix 'x' and try again. Or just use the code on GitHub. This was written for Python 3.4.
• user59236: @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.

Answer 1

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()).