I deal with a lot of hierarchies in my day to day development. File systems, nested DAG nodes in Autodesk Maya, etc.
I'm wondering, are there any good modules for Python specifically designed to traverse and compare hierarchies of objects?
Of particular interest would be ways to do 'fuzzy' comparisons between two nearly identical hierarchies. Some of the reasons for doing this would be for matching two node hierarchies in Maya from two different characters in order to transfer animation from one to the other.
Based on what I've been reading, I'd probably need something with a name threshold (which I could build myself) for comparing how close two node names are to each other. I'd then need a way to optionally ignore the order that child nodes appear in the hierarchy. Lastly, I'd need to deal with a depth threshold, in cases where a node may have been slightly moved up or down the hierarchy.
I'm not sure I see the need for a complete module -- hierarchies are a design pattern, and each hierarchy has enough unique features that it's hard to generalize.
class Node( object ):
def __init__( self, myData, children=None )
self.myData= myData
self.children= children if children is not None else []
def visit( self, aVisitor ):
aVisitor.at( self )
aVisitor.down()
for c in self.children:
aVisitor.at( c )
aVisitor.up()
class Visitor( object ):
def __init__( self ):
self.depth= 0
def down( self ):
self.depth += 1
def up( self ):
self.depth -= 1
I find that this is all I need. And I've found that it's hard to make a reusable module out of this because (a) there's so little here and (b) each application adds or changes so much code.
Further, I find that the most commonly used hierarchy is the file system, for which I have the os module. The second most commonly used hierarchy is XML messages, for which I have ElementTree (usually via lxml). After those two, I use the above structures as templates for my classes, not as a literal reusable module.