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:


Is a Python dict the best way to represent a tree?
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) &gt; 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}},
}
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) &gt; 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()).