Using PennyLane

Release news

Development

API

Internals

  1. Docs
  2. qml.transforms
  3. qml.transforms.intermediate_reps.preorder_traverse

qml.transforms.intermediate_reps.preorder_traverse

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

Pre-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 be provided manually but is used in recursion.

Returns:

Pairs of nodes that constitute pre-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, pre-order traversal results in a reordering of the nodes of the tree, with each node appearing exactly once. Pre-order traversing the graph means that for every node we reach, we first append the node itself to the ordering and then visit its child nodes (in standard sorting of the node labels/indices).

The pre-order traversal reads [0, 1, 3, 8, 4, 5, 2, 6, 7]. 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 first entry, which always is the root of the tree provided via the source argument, is not included in the output.

>>> traversal = qml.transforms.preorder_traverse(G, 0)
>>> print(traversal)
[(1, 0), (3, 1), (8, 3), (4, 1), (5, 1), (2, 0), (6, 2), (7, 2)]
>>> expected = [1, 3, 8, 4, 5, 2, 6, 7] # Skipping leading 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. Append (0), the root.

  2. Visit the first child of (0), which is (1), and append it.

  3. Visit the first child of (1), which is (3), and append it.

  4. Visit the first and only child of (3), which is (8), and append it.

  5. Visit the next child of (1), which is (4), and append it.

  6. Visit the last child of (1), which is (5), and append it.

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

  8. Visit the first child of (2), which is (6), and append it.

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

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

Previous
Next