How to traverse a GeListNode tree
-
With grouped objects only the view color of the group is changed and not that of the sub-objects i want to change the view color of the sub-objects too! Can you send me a script please.
Thank you! -
Wen man einzelne Objekte aktiviert funktioniert das Script. Wenn ich aber mehrere Objekte aktiviere funktioniert das Script nicht mehr?
Only the group is assigned the view color but not the sub-objects?Thank you!
-
Hello @WDP,
please read the Forum Guidelines as pointed out before. New questions constitute a new topic. We also cannot provide code on demand, as reflected in your request 'Can you send me a script please.' and instead provide answers to questions about our API as also lined out in the Forum Guidelines.
About your question: The traversal of a
GeListNode
tree, e.g., an object tree, can be more complicated than it might seem, as one must deal with stack-overflow problems (or in Python the recursion limit that does prevents them). Which means it cannot be implemented recursively when it should be able to run on scenes with more than 999 objects. I have attached an example which does illustrate the problem.Cheers,
FerdinandAn example output (which does not trigger the recursion limit due to only 500 objects being added to the scene):
sys.getrecursionlimit()=1000 Traversed 500 nodes in 0.01 sec with GetAllNodesRecursively(). Traversed 500 nodes in 0.01001 sec with GetAllNodesSemiIteratively(). Traversed 500 nodes in 0.00199 sec with GetAllNodesIteratively().
The code:
"""Example script comparing different methods of traversal of a GeListNode tree. To be run as a script manger script. The function descriptions contain the explanation for the advantages and disadvantages of each approach. When there is no object in the scene, a worst case object tree with 500 objects will be generated. Modify #count passed to GenerateNullTree() in main() to generate larger trees (and potentially see Cinema 4D crash from trying to traverse these trees recursively). """ import c4d import random import time import sys def GetAllNodesRecursively(node: c4d.GeListNode) -> c4d.GeListNode: """Yields all descendants of ``node`` in a recursive fashion. The passed node itself is yielded as the first node and the node graph is being traversed in depth first fashion. This design is subject to stack overflows and in Python the recursion limit preventing them. When there are more than 999 descendants attached to ``node``, this function will raise a recursion error. The recursion limit of Python is set very conservatively with a value 1000. The recursion limit can be accessed with ``sys.`get/setrecursionlimit``. But it cannot be set to an arbitrary value as the Python interpreter at some point will then cause a stack overflow and crash. This is effectively only viable when one is sure to have less than 1000 nodes attached to the passed in node, as raising the recursion limit is in practice not advisable. """ if node is None: return yield node for child in node.GetChildren(): # The recursion is happening here. For every node in the tree, the # function is calling itself, maxing out the recursion limit rather # quickly. for descendant in GetAllNodesRecursively(child): yield descendant def GetAllNodesSemiIteratively(node: c4d.GeListNode) -> c4d.GeListNode: """Yields all descendants of ``node`` in a semi-iterative fashion. The passed node itself is yielded as the first node and the node graph is being traversed in depth first fashion. This example corrects the flaw of ``GetAllNodesRecursively()`` of maxing out the recursion limit rather quickly by only invoke a recursion for moving down in in the hierarchy of a tree, moving to sibling nodes is done iteratively. Due to executing moving down recursively, the function will still raise a recursion error when there are more than 999 hierarchy levels below node. """ if node is None: return while node: yield node # The recursion moving down. for descendant in GetAllNodesSemiIteratively(node.GetDown()): yield descendant # The iteration in one level. node = node.GetNext() def GetAllNodesIteratively(node: c4d.GeListNode) -> c4d.GeListNode: """Yields all descendants of ``node`` in a truly iterative fashion. The passed node itself is yielded as the first node and the node graph is being traversed in depth first fashion. This will not fail even on the most complex scenes due to truly hierarchical iteration. The lookup table too do this, is here solved with a dictionary which yields favorable look-up times in especially larger scenes but results in a more convoluted code. The look-up could also be solved with a list and then searching in the form ``if node in lookupTable`` in it, resulting in cleaner code but worse runtime metrics due to the difference in lookup times between list and dict collections. """ if node is None: return # The lookup dictionary and a terminal node which is required due to the # fact that this truly iterative, and we otherwise would leak into the # ancestors and siblings of the input node. The terminal node could be # set to a different node, for example ``node.GetUp()`` to also include # siblings of the passed in node. visisted = {} terminal = node while node: # C4DAtom is not natively hashable, i.e., cannot be stored as a key # in a dict, so we have to have to hash them over their unique id. nodeUuid = node.FindUniqueID(c4d.MAXON_CREATOR_ID) if nodeUuid is None: raise RuntimeError(f"Could not retrieve UUID for {node}.") # Yield the node when it has not been encountered before. if visisted.get(bytes(nodeUuid)) is None: yield node visisted[bytes(nodeUuid)] = True # Attempt to get the first child of the node and hash it. getDown = node.GetDown() if getDown: getDownUuid = getDown.FindUniqueID(c4d.MAXON_CREATOR_ID) if getDownUuid is None: raise RuntimeError(f"Could not retrieve UUID for {getDown}.") # Walk the graph in a depth first fashion. if getDown and visisted.get(bytes(getDownUuid)) is None: node = getDown elif node == terminal: break elif node.GetNext(): node = node.GetNext() else: node = node.GetUp() # --- Some helper code, this can be ignored ---------------------------------- def GenerateNullTree( doc: c4d.documents.BaseDocument, count: int = 1000) -> None: """Generates a null object tree and inserts it into the passed document. """ root, depth = c4d.BaseList2D(c4d.Onull), 0 if root is None: raise MemoryError("Could not allocate null object.") root.SetName("root") i, last = 0, root while i < count - 1: null = c4d.BaseList2D(c4d.Onull) if null is None: raise MemoryError("Could not allocate null object.") null.SetName(f"Null.{i}") null.InsertUnderLast(last) last = null i += 1 doc.StartUndo() doc.InsertObject(root) doc.AddUndo(c4d.UNDOTYPE_NEWOBJ, root) doc.EndUndo() doc.SetActiveObject(root, c4d.SELECTION_NEW) c4d.EventAdd() def timeit(func: callable) -> any: """A cheap decorator to time the examples. """ def wrapper(*args, **kwargs) -> tuple[float, any]: """The wrapper logic. """ tStart = time.time() result = func(*args, **kwargs) timing = round(time.time() - tStart, 5) return timing, result return wrapper @timeit def CallTimed(func: callable, node: c4d.GeListNode) -> any: """Times the passed example. """ cnt = 0 # Really making sure the generators are exhausted. for node in func(node): cnt += 1 return cnt def main(): """Entry point. """ print (f"{sys.getrecursionlimit()=}") # When there is no object in the scene, generate a worst case object # tree which contains only out of objects with one child each up to a # depth of count. if doc.GetFirstObject() is None: # WARNING: Setting this value beyond the recursion limit of Python, # i.e., 1000, can crash Cinema 4D. GenerateNullTree(doc, count=500) node = doc.GetFirstObject() else: node = op # Call the examples with timings for func in (GetAllNodesRecursively, GetAllNodesSemiIteratively, GetAllNodesIteratively): t, cnt = CallTimed(func, node) print (f"Traversed {cnt} nodes in {t} sec with {func.__name__}().") if __name__ == '__main__': main()
-
There are also comprehensive articles on the old dev blog about recursive...
[URL-REMOVED]...and non-recursive hierarchy iteration...
[URL-REMOVED]
[URL-REMOVED] @maxon: This section contained a non-resolving link which has been removed.
-
Hello @WDP,
without any further questions we will consider this topic as solved by Friday, December the 17th.
Thank you for your understanding,
Ferdinand -