How to traverse a GeListNode tree

[WDP]

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!

[WDP]

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!

[ferdinand]

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

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

[fwilleke80]

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.

[ferdinand]

Hello @WDP,

without any further questions we will consider this topic as solved by Friday, December the 17th.

Thank you for your understanding,
Ferdinand