Skip to content

traversal

phyllotaxis_analysis.tree.traversal Link

Tree Traversal Algorithms

This module provides different traversal algorithms for tree data structures implemented in the tree module.

Acknowledgements: This is a port of the original openalea.container.traversal.tree Python2 implementation by Christophe Pradal christophe.pradal@cirad.fr.

Key Features: - Pre-order traversal (root then children) - Post-order traversal (leaves to root) - Level-order traversal (breadth-first)

Usage Examples: 

from phyllotaxis_analysis.tree import Tree
from phyllotaxis_analysis.tree.traversal import pre_order, post_order, level_order

# Create a simple tree
tree = Tree()
child1 = tree.add_child(tree.root)
child2 = tree.add_child(tree.root)

# Traverse the tree in pre-order
for node in pre_order(tree, tree.root):
    print(node)  # Will print: root, child1, child2

level_order Link

level_order(tree, vtx_id)

Traverse the vertices in a level order (breadth-first).

This function performs a breadth-first traversal of the tree, visiting the root node first, then all nodes at depth 1, then all nodes at depth 2, and so on.

Parameters:

Name Type Description Default
tree Tree

The tree to traverse.

 required
vtx_id int

The vertex identifier to start the traversal from.

 required

Returns:

Type Description
iterator

An iterator over vertex identifiers in level order.

Examples:

>>> from phyllotaxis_analysis.tree import Tree
>>> tree = Tree()
>>> child1 = tree.add_child(tree.root)
>>> child2 = tree.add_child(tree.root)
>>> grandchild = tree.add_child(child1)
>>> list(level_order(tree, tree.root))
[0, 1, 2, 3]
Source code in src/phyllotaxis_analysis/tree/traversal.py 
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
def level_order(tree: 'Tree', vtx_id: int) -> iter:
    """
    Traverse the vertices in a level order (breadth-first).

    This function performs a breadth-first traversal of the tree, visiting
    the root node first, then all nodes at depth 1, then all nodes at depth 2,
    and so on.

    Parameters
    ----------
    tree : Tree
        The tree to traverse.
    vtx_id : int
        The vertex identifier to start the traversal from.

    Returns
    -------
    iterator
        An iterator over vertex identifiers in level order.

    Examples
    --------
    >>> from phyllotaxis_analysis.tree import Tree
    >>> tree = Tree()
    >>> child1 = tree.add_child(tree.root)
    >>> child2 = tree.add_child(tree.root)
    >>> grandchild = tree.add_child(child1)
    >>> list(level_order(tree, tree.root))
    [0, 1, 2, 3]
    """
    queue = deque()
    queue.append(vtx_id)

    while queue:
        vid = queue.popleft()
        yield vid
        queue.extend(tree.children(vid))

post_order Link

post_order(tree, vtx_id)

Traverse a tree in a postfix way (from leaves to root).

This function performs a post-order traversal of the tree, recursively visiting all subtrees before visiting the root node.

Parameters:

Name Type Description Default
tree Tree

The tree to traverse.

 required
vtx_id int

The vertex identifier to start the traversal from.

 required

Returns:

Type Description
iterator

An iterator over vertex identifiers in post-order.

Examples:

>>> from phyllotaxis_analysis.tree import Tree
>>> tree = Tree()
>>> child1 = tree.add_child(tree.root)
>>> child2 = tree.add_child(tree.root)
>>> grandchild = tree.add_child(child1)
>>> list(post_order(tree, tree.root))
[3, 1, 2, 0]
Source code in src/phyllotaxis_analysis/tree/traversal.py 
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
def post_order(tree: Tree, vtx_id: int) -> iter:
    """Traverse a tree in a postfix way (from leaves to root).

    This function performs a post-order traversal of the tree, recursively
    visiting all subtrees before visiting the root node.

    Parameters
    ----------
    tree : phyllotaxis_analysis.tree.Tree
        The tree to traverse.
    vtx_id : int
        The vertex identifier to start the traversal from.

    Returns
    -------
    iterator
        An iterator over vertex identifiers in post-order.

    Examples
    --------
    >>> from phyllotaxis_analysis.tree import Tree
    >>> tree = Tree()
    >>> child1 = tree.add_child(tree.root)
    >>> child2 = tree.add_child(tree.root)
    >>> grandchild = tree.add_child(child1)
    >>> list(post_order(tree, tree.root))
    [3, 1, 2, 0]
    """
    for vid in tree.children(vtx_id):
        for node in post_order(tree, vid):
            yield node
    yield vtx_id

pre_order Link

pre_order(tree, vtx_id, edge_type_property=None)

Traverse a tree in a prefix way (root then children).

This function performs a pre-order traversal of the tree, visiting the root node first, then recursively visiting all subtrees.

Parameters:

Name Type Description Default
tree Tree

The tree to traverse.

 required
vtx_id int

The vertex identifier to start the traversal from.

 required
edge_type_property dict

A dictionary mapping vertex identifiers to edge types. If provided, vertices with edge type '<' are visited after vertices with other edge types.

 None

Returns:

Type Description
iterator

An iterator over vertex identifiers in pre-order.

Examples:

>>> from phyllotaxis_analysis.tree import Tree
>>> tree = Tree()
>>> child1 = tree.add_child(tree.root)
>>> child2 = tree.add_child(tree.root)
>>> grandchild = tree.add_child(child1)
>>> list(pre_order(tree, tree.root))
[0, 1, 3, 2]
Source code in src/phyllotaxis_analysis/tree/traversal.py 
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
def pre_order(tree: Tree, vtx_id: int, edge_type_property: dict = None) -> iter:
    """
    Traverse a tree in a prefix way (root then children).

    This function performs a pre-order traversal of the tree, visiting
    the root node first, then recursively visiting all subtrees.

    Parameters
    ----------
    tree : phyllotaxis_analysis.tree.Tree
        The tree to traverse.
    vtx_id : int
        The vertex identifier to start the traversal from.
    edge_type_property : dict, optional
        A dictionary mapping vertex identifiers to edge types.
        If provided, vertices with edge type '<' are visited after vertices with other edge types.

    Returns
    -------
    iterator
        An iterator over vertex identifiers in pre-order.

    Examples
    --------
    >>> from phyllotaxis_analysis.tree import Tree
    >>> tree = Tree()
    >>> child1 = tree.add_child(tree.root)
    >>> child2 = tree.add_child(tree.root)
    >>> grandchild = tree.add_child(child1)
    >>> list(pre_order(tree, tree.root))
    [0, 1, 3, 2]
    """

    if edge_type_property is None:
        yield vtx_id
        for vid in tree.children(vtx_id):
            for node in pre_order(tree, vid):
                yield node
    else:
        # 1. select first '+' edges
        successor = []
        yield vtx_id
        for vid in tree.children(vtx_id):
            if edge_type_property.get(vid) == '<':
                successor.append(vid)
                continue

            for node in pre_order(tree, vid):
                yield node

        # 2. select then '<' edges
        for vid in successor:
            for node in pre_order(tree, vid):
                yield node