Tree traversal algorithms?

Coding
1

Say I want to find a path from a root node to a leaf on a character structure. What would be the best way to do it?

I need to operate on a clone of said path later, so ideally I would pass root and leaf nodes to a search function that would return an array with the nodes of the path. There’s a list of algorithms on Wikipedia, but I dunno which would be best for something like this…

2

Funny i was just reading up on this myself this past week. I found this, might be a good starting point:

Python Patterns - Implementing Graphs

3

Thanks a lot!! That’s more than what I was looking for actually! Quite an easy and quick solution, and just a couple lines to change to make it work with pymel.

def pathFinder(start, end, path=[]):
    path.append(start)
    if start == end:
        return path
    if not ls(start):
        return None
    for lChild in start.getChildren():
        if lChild not in path:
            newpath = pathFinder(lChild, end, path)
            if newpath: return newpath
    return None
4

If you already have the leaf node don’t you already have the full path?


fullPath = maya.cmds.ls('<leaf name>', long=True)

If you needed the intermediate paths you could do something like:


orignalPath = maya.cmds.ls('<leaf name>', long=True) # '|a|b|c|d|e'
intermediatePaths = orignalPath.split('|')
allPaths = list()
for i in xrange(2, len(intermediatePaths)+1):
    allPaths.append('|'.join(intermediatePaths[:i]))
print allPaths

On another note its bad form to initialize a list (or anything mutable) as a default argument. When you do this the list will be shared between by every instance of the function.
More reading on the subject:
http://www.deadlybloodyserious.com/2008/05/default-argument-blunders/

Keir

5

Note that you can generally make your code much, much simpler if you think in terms of higher-order functions. If I understand this Eduardo’s code correctly, he’s basically recursing through all children until he finds ‘end’ and then returns the concatenated path of ‘end’? (Why can’t you work backwards from ‘end’ in this case?) Anyway, more to the point, consider this untested and possibly flawed (implementation-wise, not conceptually) instead:


def enumerateAllNodes(start, yieldStartNode=True, pathToStart=None):
   pathToStart = pathToStart or (start)
   if yieldStartNode:
      yield (start, pathToStart)
   for child in start.getChildren():
      pathToChild = pathToStart + child
      yield (child, pathToChild)
      for nextLvlChild in enumerateAllNodes(child, False, pathToChild):
         yield (nextLvlChild, pathToChild + nextLvlChild)

def first(enumerable, predicate):
   for item in enumerable:
      if predicate(item):
         return item
   return None

#looking for fullPath from startNode to endNode
fullPath = enumerableAllNodes(startNode).first(lambda node: node == endNode)[1]

You end up with far more universal and useful methods you can compose together with an easy lambda to do exactly what you want- rather than having to write a difficult to follow method for a particular task like given above.

6

[QUOTE=Keir Rice;10142]


fullPath = maya.cmds.ls('<leaf name>', long=True)

[/QUOTE]
Curious, that’s indeed handy, although it returns a single long string separated by |. And long=True doesn’t seem to be working with pymel, only with maya.cmds… Is this right? Or am I missing something?

[QUOTE=Keir Rice;10142]
On another note its bad form to initialize a list (or anything mutable) as a default argument. When you do this the list will be shared between by every instance of the function.
More reading on the subject:
http://www.deadlybloodyserious.com/2008/05/default-argument-blunders/
[/QUOTE]
I didn’t know about that, thanks. But at least on that function specifically, and maybe on using recursion generally, it might actually be a feature. I could just return path then, instead of “adding all paths” to newpath.

[QUOTE=Rob Galanakis;10159]
(Why can’t you work backwards from ‘end’ in this case?)
[/QUOTE]
ARGH!

Sometimes your mind gets lost so deep into a problem you don’t realize a possible solution is just to flip it to the other side.

7

[QUOTE=eksimioni;10196]
I didn’t know about that, thanks. But at least on that function specifically, and maybe on using recursion generally, it might actually be a feature. I could just return path then, instead of “adding all paths” to newpath.[/QUOTE]

This is actually explained on that page, seeing as how Guido van Rossum wrote that code, it’s probably that way for a reason :laugh:

The default value for this argument is the empty list, ‘’, meaning no nodes have been traversed yet. This argument is used to avoid cycles (the first ‘if’ inside the ‘for’ loop). The ‘path’ argument is not modified: the assignment “path = path + [start]” creates a new list. If we had written “path.append(start)” instead, we would have modified the variable ‘path’ in the caller, with disastrous results. (Using tuples, we could have been sure this would not happen, at the cost of having to write “path = path + (start,)” since “(start)” isn’t a singleton tuple – it is just a parenthesized expression.)

1 Like