Skip to main content

Python library for manipulating infinite trees.

# Lazy Tree

Table of Contents

# Installation

If you just need to use `lazytree`, you can just run:

`\$ pip install lazytree`

For developers, note that this project uses the poetry python package/dependency management tool. Please familarize yourself with it and then run:

`\$ poetry install`

# Usage

A `LazyTree` is a triple, `(root, child_map, view)` where `root : A` and a child map, `child_map`, which maps `a` to a (finite) list of children `child_map : A -> List[A]` define the tree's structure and `view : A -> B` defines what the tree represents. The default view is the identity map, `lambda x: x`.

This structure is useful for modeling infinite (or really large) trees where only a finite number of nodes need to be accessed. For example, the following Binary tree represents the recursive subdivision of the interval [0, 1].

```from lazytree import LazyTree

def split(itvl):
lo, hi = itvl
mid = lo + (hi - lo)/2
return (lo, mid), (mid, hi)

tree = LazyTree(
root=(0, 1),  # Initial Itvl
child_map=split  # Itvl -> [Itvl]
)
```

Conceptually a `LazyTree` object can be thought of as containing the pieces of data.

1. The `root` of the tree.
2. The data represented by the `root`, accessed via the `view` method.
3. The child subtrees - computed using `child_map` and accessed through the `.children` attribute.

For example, in our interval example, each node corresponds to an interval of `(0, 1)` and has two child subtrees.

```# View the current root.
assert tree.view() == tree.root

subtrees = tree.children
assert len(subtrees) == 2
```

Often, for each node in a tree, one is interested in computing a particular function. This can be done using the `map` and `view` methods. For example, below `map` each interval in the tree to it's size. This results in a new `LazyTree` object.

```tree2 = tree.map(lambda itvl: itvl - itvl)  # Change view to itvl size.
assert tree2.view() == 1

# Access the root's subtrees
subtrees = tree2.children
assert len(subtrees) == 2
assert subtrees.root == (0, 0.5)
assert subtrees.view() == 0.5
```

Travesals of a `LazyTree` object are also implemented. For example,

```# Breadth First Search through tree.
## Note: calls .view() before returning.
itvls = tree.bfs()  # returns a generator.
sizes = tree2.bfs()  # returns a generator.

assert next(itvls) == (0, 1)
assert next(sizes) == 1

assert next(itvls) == (0, 0.5)
assert next(sizes) == 0.5

assert next(itvls) == (0.5, 1)
assert next(sizes) == 0.5

# Cost guided traversal.
## Note: Smaller means higher priority.
sizes = tree2.cost_guided_refinement(cost=lambda x: x)
assert next(sizes)  == 1  # (0, 1)
assert next(sizes)  == 0.5  # (0, 0.5)
assert next(sizes)  == 0.25  # (0, 0.25)

# Iterative Deepening Depth First Traversal
sizes = tree2.iddfs(max_depth=3)  # returns a generator.
assert list(sizes) == [1, 0.5, 0.5, 0.25, 0.25, 0.25, 0.25, 0.125, 0.125, 0.125, 0.125, 0.125, 0.125, 0.125, 0.125]

# Note, you can reset the current view.
tree3 = tree2.with_identity_view()
assert tree3.view() == tree.view()
```

Finally, one can "prune" away subtrees by labeling them as leaf nodes using the `prune` method. If you are sure that the resulting tree is finite (either due to pruning or the provided `child_map`) then one can compute the leaves of the tree.

```# Prune subtrees with a root of size less than 0.1.
tree4 = tree2.prune(isleaf=lambda s: s < 0.2)
sizes = tree.bfs()
assert all(s > 0.001 for s in sizes)  # Note that sizes is now finite.

# Compute leafs of tree. Careful! Could be infinite!
assert all(s == 0.125 for s in tree4.leaves())
assert len(list(tree4.leaves())) == 8
```

## Release history Release notifications | RSS feed

This version 0.3.2 0.3.1 0.3.0 0.2.1 0.2.0 0.1.0

## Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Files for lazytree, version 0.3.2
Filename, size File type Python version Upload date Hashes
Filename, size lazytree-0.3.2-py3-none-any.whl (5.6 kB) File type Wheel Python version py3 Upload date Hashes
Filename, size lazytree-0.3.2.tar.gz (5.5 kB) File type Source Python version None Upload date Hashes