Using PennyLane

Release news

Development

API

Internals

  1. Docs
  2. qml.labs
  3. qml.labs.intermediate_reps
  4. qml.labs.intermediate_reps.postorder_traverse

qml.labs.intermediate_reps.postorder_traverse

postorder_traverse(tree, source, source_parent=None)[source]

Post-order traverse a tree graph, starting from (but excluding) the node source.

Parameters:

  • tree (nx.Graph) – Tree graph to traverse. Must contain source. Must contain source_parent if it is not None. Typing assumes integer-labeled nodes.

  • source (int) – Node to start the traversal from

  • source_parent (Optional[int]) – Parent node of source in tree. Should not provided manually but is used in recursion.

Returns:

Pairs of nodes that constitute post-order traversal of tree starting at source. Strictly speaking, the traversal is encoded in the first entry of each pair, and the second entry simply is the parent node for each first entry.

Return type:

list[tuple[int]]

A useful illustration of depth-first tree traversals can be found on Wikipedia.

Example

Consider the tree

                  (4)
                   |
(6) - (2) - (0) - (1) - (3) - (8)
       |           |
      (7)         (5)

and consider (0) to be the source, or root, of the tree. We may construct this tree as a nx.Graph by providing the edge data:

>>> import networkx as nx
>>> G = nx.Graph([(0, 1), (0, 2), (1, 3), (1, 4), (1, 5), (2, 6), (2, 7), (3, 8)])

As for every tree traversal, post-order traversal results in a reordering of the nodes of the tree, with each node appearing exactly once. Post-order traversing the graph means that for every node we reach, we first visit its child nodes (in standard sorting of the node labels/indices) and then append the node itself to the ordering.

The post-order traversal reads [8, 3, 4, 5, 1, 6, 7, 2, 0]. For the output convention of this function, each node is accompanied by its parent node, because this is useful information needed down the line, and it is not easy to retrieve from the nx.Graph itself. In addition, the last entry, which always is the root of the tree provided via the source argument, is not included in the output.

>>> from pennylane.labs.intermediate_reps import postorder_traverse
>>> traversal = postorder_traverse(G, 0)
>>> print(traversal)
[(8, 3), (3, 1), (4, 1), (5, 1), (1, 0), (6, 2), (7, 2), (2, 0)]
>>> expected = [8, 3, 4, 5, 1, 6, 7, 2] # Skipping trailing root
>>> all(child == exp for (child, parent), exp in zip(traversal, expected, strict=True))
True

To see how this comes about, start at the root (0) and perform the following steps:

  1. Visit (1), (3) and then (8), without appending any of them.

  2. Append (8) because there are no child nodes to visit (it is a leaf node).

  3. Append (3) because all children of it have been visited.

  4. Visit the next child of (1), which is (4), and append it because it is a leaf node.

  5. Visit the last child of (1), which is (5), and append it because it is a leaf node.

  6. Append (1) because all its children have been visited.

  7. Visit (2) and then (6), the latter of which is appended (leaf node).

  8. Visit the second and last child of (2)), which is (7), and append it (leaf node).

  9. Append (2) becaues all its children have been visited.

  10. Append (0) becaues all its children have been visited.

Note that the source_parent argument should not be provided when calling the function but is used for the internal recursive structure.

Previous
Next