Skip to content

traversal

phyllotaxis_analysis.traversal Link

Tree Traversal AlgorithmsLink

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

AcknowledgementsLink

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

Key FeaturesLink

  • Pre-order traversal (root then children)
  • Post-order traversal (leaves to root)
  • Level-order traversal (breadth-first)

Usage ExamplesLink

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 vertex in pre_order(tree, tree.root):
    print(vertex)  # 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 vertex first, then all vertices at depth 1, then all vertices 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

Yields:

Type Description
int

The next vertex identifier in level order.
Source code in src/phyllotaxis_analysis/traversal.py 
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
def level_order(tree: 'Tree', vtx_id: int) -> Iterable[int]:
    """
    Traverse the vertices in a level order (breadth-first).

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

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

    Yields
    ------
    int
        The next vertex identifier in level order.
    """
    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 vertex.

Parameters:

Name Type Description Default
tree Tree

The tree to traverse.

 required
vtx_id int

The vertex identifier to start the traversal from.

 required

Yields:

Type Description
int

The vertex identifier of the current vertex in the traversal.
Source code in src/phyllotaxis_analysis/traversal.py 
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
def post_order(tree: 'Tree', vtx_id: int) -> Iterable[int]:
    """
    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 vertex.

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

    Yields
    ------
    int
        The vertex identifier of the current vertex in the traversal.
    """
    for vid in tree.children(vtx_id):
        for vtx in post_order(tree, vid):
            yield vtx
    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 vertex 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

Yields:

Type Description
int

The vertex identifier being visited in the traversal.
Source code in src/phyllotaxis_analysis/traversal.py 
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
def pre_order(tree: 'Tree', vtx_id: int, edge_type_property: dict|None = None) -> Iterable[int]:
    """
    Traverse a tree in a prefix way (root then children).

    This function performs a pre-order traversal of the tree, visiting
    the root vertex 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.

    Yields
    ------
    int
        The vertex identifier being visited in the traversal.
    """

    if edge_type_property is None:
        yield vtx_id
        for vid in tree.children(vtx_id):
            for vtx in pre_order(tree, vid):
                yield vtx
    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 vtx in pre_order(tree, vid):
                yield vtx

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