AlgoTree package

Submodules

AlgoTree.flat_forest module

class AlgoTree.flat_forest.FlatForest(*args: Any, **kwargs: Any)

Bases: dict

A forest class that is also a standard dictionary.

This class represents a forest using a flat dictionary structure where each node has a unique name (key) and an optional ‘parent’ name (keY) to reference its parent node.

Nodes without a ‘parent’ key (or with a ‘parent’ key set to None) are root nodes of trees in the forest. Nodes with a ‘parent’ key set to a valid name (key) in the forest are children of the node with that name. Each node represents a tree rooted at that node, which we expose through the FlatForestNode class, which provides a proxy interface to the structure centered around nodes abstracted away from the dictionary structure.

The FlatForest class is a dictionary whose data represents a forest-like structure. It provides methods to manipulate the forest structure and validation methods to check its integrity, but is essentially a view of the dict object passed into it (or created with it).

We provide a FlatForestNode class which provides an interface centered around nodes in a tree. See flat_forest_node.py for more details.

DETACHED_KEY = '__DETACHED__'

The name used to represent a detached node. This is a special name that is assumed to not exist in the tree. When a node is detached, its parent name is set to this value. Any descendants of the detached node are also detached.

PARENT_KEY = 'parent'

The key used to store the parent key of a node. Modify this if you want to use a different key to store the parent key.

add_child(name: str | None = None, *args, **kwargs) → FlatForestNode

Add a child node to the preferred root node.

Parameters:

• name – The name of the child node.

• payload – The payload of the child node.

Returns:

The child node.

as_tree(root_name='__ROOT__') → FlatForestNode

Retrieve the forest as a single tree rooted at a logical root node.

static check_valid(data) → None

Validate the forest structure to ensure the structural integrity of the trees.

This function performs the following validation checks:

1. No cycles exist in any trees.

2. All names (unique node identifiers) map to dictionary values.

3. All nodes have a parent key that is either None or a valid key in the tree.

Parameters:

data – The forest data to validate.

Returns:

None

Raises:

ValueError – If the forest structure is invalid.

child_names(name: str) → List[str]

Get the children names of a node with the given name.

Parameters:

name – The name of the node to get the children of.

Returns:

List of names of the children of the node.

property children

Get the children of the preferred root node.

Returns:

The children of the preferred root node.

contains(name: str) → bool

Check if the tree rooted at the preferred root node contains a node with the given name.

Parameters:

name – The name of the node.

Returns:

True if the node is in the forest, False otherwise.

detach(name: str) → FlatForestNode

Detach subtree rooted at node with the given name by setting its parent to FlatForest.DETACHED_KEY, which denotes a special name (key) that we assume doesn’t exist in the forest.

Parameters:

name – The name of the node to detach.

Returns:

The detached subtree rooted at the node.

Raises:

KeyError – If the node is not found in the tree.

property detached: FlatForestNode

Retrieve the detached tree. This is a special tree for which detached nodes are rooted at a logical node with the name FlatForest.DETACHED_KEY.

Returns:

The detached logical root node.

interior_node_names() → List[str]

Get interior node names, i.e., nodes that are not root nodes or logical nodes.

Returns:

List of interior node names.

static is_valid(data) → bool

Check if the given data is a valid FlatForest.

Parameters:

data – The data to check.

Returns:

True if the data is a valid FlatForest, False otherwise.

logical_root_names() → List[str]

Get the logical nodes of the forest. These occur when a node has a parent that is not in the forest. A special case for this is the DETACHED_KEY which is used for detached nodes, i.e., when we detach a node, we set its parent to DETACHED_KEY.

Returns:

List of logical root names.

property name: str

Get the name of the preferred root node. This is just self.preferred_root.

Returns:

The name of the preferred root node.

node(name: str) → FlatForestNode

Get an ancestor node with the given name under the preferred root node.

Parameters:

name – The name of the node.

Returns:

The node.

node_names() → List[str]

Get the unique names in the tree, even if they are not nodes in the tree but only parent names without corresponding nodes.

Returns:

List of unique names in the tree.

nodes() → List[FlatForestNode]

Get all the nodes in the forest.

Returns:

A list of all the nodes in the forest.

property parent: FlatForestNode | None

Get the parent of the preferred root node. This is always None since the preferred root node is a root node.

property payload: dict

Get the payload of the preferred root node.

Returns:

The payload of the preferred root node.

property preferred_root: str

Get the preferred root node of the forest.

Returns:

The preferred root node.

Raises:

KeyError – If the preferred root node is not found.

purge() → None

Purge detached nodes (tree rooted at FlatForest.DETACHED_KEY).

property root: FlatForestNode

Get the tree rooted at the preferred root node.

Returns:

The root node.

root_key(name: str) → str

Get the root key of the node with given name.

Parameters:

key – The key of the node.

Returns:

The key of the root node.

Raises:

KeyError – If the key is not found in the tree.

property root_names: List[str]

Retrieve the names of the root nodes. These are the nodes that have no parent.

Returns:

The names of the root nodes.

property roots: List[FlatForestNode]

Get the root nodes of the forest.

Returns:

The root nodes of the forest.

static spec() → dict

Get the JSON specification of the FlatForest data structure.

This method returns a dictionary representing the structure of the FlatForest. This is useful for documentation purposes and for understanding the structure of the data. The structure is as follows:

:return: A dict pattern representing the structure of the FlatForest.

subtree(name: str | None = None) → FlatForestNode

Get sub-tree rooted at the node with the name name with the current node also set to that node. If name is None, the preferred root node is used.

NOTE: This behavior is different from the expected behavior of a tree, since this is a forest. If the forest has multiple trees, this method will return any subtree under any root node. We could instead return the subtree under the preferred root node, which would then replicate the expected behavior and be consistent with the other node-centric methods like node and children. However, we choose to return the subtree under any root node to provide more flexibility. Once you return a subtree, the FlatForestNode class provides a node-centric interface to the tree structure consistent with the expected behavior.

Parameters:

name – The unique name of the node.

Returns:

FlatForestNode proxy representing the node.

to_dict() → dict

Convert the forest to a dictionary. Note this since this is already a dictionary, we just return a copy of the dictionary.

Returns:

A dictionary representation of the forest.

property trees: List[FlatForestNode]

Retrieve the trees in the forest.

Returns:

The trees in the forest.

AlgoTree.flat_forest_node module

class AlgoTree.flat_forest_node.FlatForestNode(name: str | None = None, parent: FlatForestNode | str | None = None, forest: FlatForest | None = None, payload: Dict | None = None, *args, **kwargs)

Bases: MutableMapping

add_child(name: str | None = None, *args, **kwargs) → FlatForestNode

Add a child node. See __init__ for details on the arguments.

Returns:

The child node, from the perspective of the subtree that contains the parent.

property children: List[FlatForestNode]

Get the children of the node.

Returns:

List of child nodes.

clone(parent=None, clone_children=False) → FlatForestNode

Clone the node and, optionally, its children. If you want to clone the entire forest, see deepcopy. We allow the parent to be set to a new parent node to facilitate flexible cloning of nodes into new forest structures.

Returns:

A new node (or subtree rooted at the node if clone_children is True)

contains(name) → bool

Check if the the subtree rooted at the node contains any children with the given name

Parameters:

key – The key to check.

Returns:

True if the child node is present, False otherwise.

detach() → FlatForestNode

Detach the node.

Returns:

The detached node.

property forest: FlatForest

Get the underlying FlatForest object.

Returns:

The FlatForest object.

property name

Get the unique name of the node.

Returns:

The unique name of the node.

node(name: str) → FlatForestNode

Get an ancestor node with the given name.

Parameters:

name – The name of the node.

Returns:

The node.

property parent: FlatForestNode | None

Get the parent node of the node.

Returns:

The parent node.

property payload: Dict

Get the payload data of the node.

Returns:

Dictionary representing the data of the node.

static proxy(forest: FlatForest, node_key: str, root_key: str | None = None) → FlatForestNode

Create a proxy node for a node in a forest. The proxy node is a lightweight object that provides a node-centric abstraction of the tree that a node is a part of.

We do not check do any checks on the validity of the keys or the structure of the tree. This is a low-level method that should be used with caution. For instance, if node_key is not a descendent of root_key, the proxy node will not behave as expected.

Parameters:

• forest – The forest in which the proxy node exists (or logically exists).

• node_key – The key of the node.

• root_key – The key of the (real or logical) root node.

property root: FlatForestNode

Get the root node of the subtree.

Returns:

The root node.

subtree(name: str | None = None) → FlatForestNode

Get a subtree rooted at the node with the name name. If name is None, the subtree is rooted at the current node.

Parameters:

name – The name of the root node.

Returns:

A subtree rooted at the given node.

to_dict()

Convert the subtree rooted at node to a dictionary.

Returns:

A dictionary representation of the subtree.

AlgoTree.node_hasher module

class AlgoTree.node_hasher.NodeHasher(hash_fn=None)

Bases: object

A class providing various hash functions for tree nodes.

static name(node: Any) → int

Compute a hash based on the name of the node.

Use Case: - Useful when you want to compare nodes solely based on their names, ignoring their position and other attributes.

Example: - Checking if two nodes represent the same entity based on their name.

Parameters:

node – The node for which to compute the hash.

Returns:

The hash value for the node’s name.

static node(node: Any) → int

Compute a hash based on the name and payload of the node.

Use Case: - This is the most common notion of node equality, focusing on the node’s intrinsic properties and ignoring its position in the tree. - Useful when you want to compare nodes by both name and payload, but not their position in the tree.

Example: - Checking if two nodes are equivalent in terms of both their name and the data they carry, without considering their location in the tree structure.

Parameters:

node – The node for which to compute the hash.

Returns:

The hash value for the node’s name and payload.

static path(node: Any) → int

Compute a hash based on the path of the node in the tree.

Use Case: - Useful when the position of the node in the tree is more important than its name or payload.

Example: - Determining if two nodes occupy the same position in the same or different trees.

Parameters:

node – The node for which to compute the hash.

Returns:

The hash value for the node’s path in the tree.

static payload(node: Any) → int

Compute a hash based on the payload of the node.

Use Case: - Useful when comparing nodes based on their payload, ignoring their name and position in the tree.

Example: - Identifying nodes that carry the same data.

Parameters:

node – The node for which to compute the hash.

Returns:

The hash value for the node’s payload.

AlgoTree.tree_hasher module

class AlgoTree.tree_hasher.TreeHasher(hash_fn=None)

Bases: object

A class that provides various hash functions for trees, with a default hashing strategy.

static isomorphic(tree: Any) → int

Hash based on tree structure only, ignoring node names and payloads.

static tree(tree: Any) → int

Hash based on the entire tree structure.

Parameters:

tree – The tree to hash.

Returns:

The hash value for the tree.

AlgoTree.pretty_tree module

class AlgoTree.pretty_tree.PrettyTree(style: ~typing.Dict[str, str] | None = None, node_name: ~typing.Callable[[~typing.Any], str] = <function PrettyTree.<lambda>>, indent: int = 7, mark: ~typing.List[str] | None = None, node_details: ~typing.Callable[[~typing.Any], ~typing.Any] | None = None)

Bases: object

A class to print a tree in a more readable way.

default_style = {'child_connector': '├', 'horizontal': '─', 'last_child_connector': '└', 'markers': ['🔵', '🔴', '🟢', '🟣', '🟠', '🟡', '🟤', '⚫', '⚪', '⭕', '🔘'], 'payload_connector': '◄', 'spacer': ' ', 'vertical': '│'}

static mark(name: str, markers: List[str]) → str

Get the marker for a node based on the hash of the node name.

Parameters:

name – The name of the node.

Returns:

The marker for the node.

AlgoTree.pretty_tree.pretty_tree(node, **kwargs) → str

Converts a tree to a pretty string representation.

Parameters:

kwargs – Key-word arguments. See PrettyTree for more details.

Returns:

A pretty string representation of the tree.

AlgoTree.tree_converter module

class AlgoTree.tree_converter.TreeConverter

Bases: object

Utility class for converting between tree representations.

static convert(source, target_type: ~typing.Type, node_name: ~typing.Callable = <staticmethod(<function TreeConverter.default_node_name>)>, extract: ~typing.Callable = <staticmethod(<function TreeConverter.default_extract>)>) → Any

Convert a tree rooted at node to a target tree type representation.

Parameters:

• src_node – The root node of the tree to convert.

• target_type – The target tree type to convert to.

• node_name – The function to map nodes to unique keys.

• extract – A callable to extract relevant data from a node.

Returns:

The converted tree.

static copy_under(node, under, node_name: ~typing.Callable = <staticmethod(<function TreeConverter.default_node_name>)>, extract: ~typing.Callable = <staticmethod(<function TreeConverter.default_extract>)>, max_tries: int = 1000) → Any

Copy the subtree rooted at node as a child of under, where the copy takes on the node type of under. It returns the subtree that contains under with current node at under.

Parameters:

• node – The subtree rooted at node to copy.

• under – The node to copy the subtree under.

• node_name – The function to map nodes to names.

• extract – A callable to extract relevant payload from a node.

• max_tries – The maximum number of tries to generate a unique name if a name conflict occurs.

Returns:

A subtree extending under with the copied nodes.

static default_extract(node)

Default extractor of relevant payload from a node.

Parameters:

node – The node to extract payload data from.

Returns:

The extracted data.

static default_node_name(node)

Default function to map nodes to unique keys. If the node has a name attribute, then it is used as the unique key. Otherwise, a random UUID is generated.

Parameters:

node – The node to map to a unique key.

Returns:

The unique key for the node.

static to_dict(node, node_name: ~typing.Callable = <staticmethod(<function TreeConverter.default_node_name>)>, extract: ~typing.Callable = <staticmethod(<function TreeConverter.default_extract>)>, **kwargs) → Dict

Convert the subtree rooted at node to a dictionary.

Parameters:

• node – The root node of the subtree to convert.

• node_name – The function to map nodes to unique keys.

• extract – A callable to extract relevant data from a node.

Returns:

A dictionary representation of the subtree.

AlgoTree.treenode module

class AlgoTree.treenode.TreeNode(parent: TreeNode | None = None, name: str | None = None, payload: Any | None = None, *args, **kwargs)

Bases: dict

A tree node class. This class stores a nested representation of the tree. Each node is a TreeNode object, and if a node is a child of another node, it is stored in the parent node’s children attribute.

add_child(name: str | None = None, payload: Any | None = None, *args, **kwargs) → TreeNode

Add a child node to the tree. Just invokes __init__. See __init__ for details.

clone() → TreeNode

Clone the tree node (sub-tree) rooted at the current node.

Returns:

A new TreeNode object with the same data as the current node.

static from_dict(data: Dict) → TreeNode

Create a TreeNode from a dictionary.

Parameters:

data – The dictionary to convert to a TreeNode.

Returns:

A TreeNode object.

static is_valid(data) → bool

Check if the given data is a valid TreeNode data.

Parameters:

data – The data to check.

Returns:

True if the data is a valid TreeNode, False otherwise.

node(name: str) → TreeNode

Get the node with the given name in the current sub-tree. The sub-tree remains the same, we just change the current node position. If the name is not found, raise a KeyError.

Parameters:

name – The name of the node.

Returns:

The node with the given name.

nodes() → List[TreeNode]

Get all the nodes in the current sub-tree.

Returns:

A list of all the nodes in the current sub-tree.

property parent: TreeNode | None

Get the parent of the node.

Returns:

The parent of the node.

property root: TreeNode

Get the root of the tree.

Returns:

The root node of the tree.

subtree(name: str) → TreeNode

Get the subtree rooted at the node with the given name. This is not a view, but a new tree rooted at the node with the given name. This is different from the node method, which just changes the current node position. It’s also different from the subtree method in the FlatForestNode class, which returns a view of the tree.

Parameters:

name – The name of the node.

Returns:

The subtree rooted at the node with the given name.

to_dict()

Convert the subtree rooted at node to a dictionary.

Returns:

A dictionary representation of the subtree.

AlgoTree.treenode_api module

class AlgoTree.treenode_api.TreeNodeApi

Bases: object

A class to check if a tree object models the concept of a tree node. The tree node concept is defined as follows:

• children property

  Represents a list of child nodes for the current node that can be accessed and modified.

• parent property

  Represents the parent node of the current node that can be accessed and modified.

  Suppose we have the subtree G at node G:

  B (root)
  ├── D
  └── E (parent)
      └── G (current node)
  

  Then, G.parent should refer node E. G.root.parent should be None since root is the root node of subtree G and the root node has no parent. This is true even if subtree G is a subtree view of a larger tree.

  If we set G.parent = D, then the tree structure changes to:

  B (root)
  ├── D
  │   └── G (current node)
  └── E
  

  This also changes the view of the sub-tree, since we changed the underlying tree structure. However, the same nodes are still accessible from the sub-tree.

  If we had set G.parent = X where X is not in the subtree G, then we would have an invalid subtree view even if is is a well-defined operation on the underlying tree structure. It is undefined behavior to set a parent that is not in the subtree, but leave it up to each implementation to decide how to handle such cases.

• node(name: str) -> NodeType method.

  Returns a node in the current subtree that the current node belongs to. The returned node should be the node with the given name, if it exists. If the node does not exist, it should raise a KeyError.

  The node-centric view of the returned node should be consistent with the view of the current node, i.e., if the current node belongs to a specific sub-tree rooted at some other node, the returned node should also belong to the same sub-tree (i.e., with the same root), just pointing to the new node, but it should be possible to use parent and children to go up and down the sub-tree to reach the same nodes. Any node that is an ancestor of the root of the sub-tree remains inaccessible.

  Example: Suppose we have the sub-tree t rooted at A and the current node is B:

  A (root)
  ├── B (current node)
  │   ├── D
  │   └── E
  |       └── G
  └── C
      └── F
  

  If we get node F, t.node(F), then the sub-tree t remains the same, but the current node is now F:

  A (root)
  ├── B
  │   ├── D
  │   └── E
  |       └── G
  └── C
      └── F (current node)
  

• subtree(node: Optional[NodeType] = None) -> NodeType method.

  Returns a view of another sub-tree rooted at node where node is contained in the original sub-tree view. If node is None, the method will return the sub-tree rooted at the current node.

  subtree is a partial function over the the nodes in the sub-tree, which means it is only well-defined when node is a descendant of the root of the sub-tree. We do not specify how to deal with the case when this condition is not met, but one approach would be to raise an exception.

  Example: Suppose we have the sub-tree t rooted at A and the current node is C:

  A (root)
  ├── B
  │   ├── D
  │   └── E
  |       └── G
  └── C (current node)
      └── F
  

  The subtree t.subtree(B) returns a new subtree:

  B (root, current node)
  ├── D
  └── E
      └── G
  

• root property

  An immutable property that represents the root node of the sub-tree.

  Suppose we have the subtree G at node G:

  B (root)
  ├── D
  └── E
      └── G (current node)
  

  Then, G.root should refer node B.

• payload property

  Returns the payload of the current node. The payload is the data associated with the node but not with the structure of the tree, e.g., it does not include the parent or children of the node.

• name property

  Returns the name of the current node. The name is an identifier for the node within the tree. It is not necessarily unique, and nor is it necessarily even a meaningful identifier, e.g., a random UUID.

• contains(name) -> bool method.

  Returns True if the sub-tree contains a node with the given name, otherwise False.

static check(node, require_props=['name', 'root', 'children', 'parent', 'node', 'subtree', 'payload', 'contains']) → Any

static is_valid(value, require_props=['name', 'root', 'children', 'parent', 'node', 'subtree', 'payload', 'contains']) → bool

static missing(node, require_props=['name', 'root', 'children', 'parent', 'node', 'subtree', 'payload', 'contains'])

properties = ['name', 'root', 'children', 'parent', 'node', 'subtree', 'payload', 'contains']

AlgoTree.utils module

AlgoTree.utils.ancestors(node) → List

Get the ancestors of a node.

We could have used the path function, but we want to show potentially more efficient use of the parent property. As a tree, each node has at most one parent, so we can traverse the tree by following the parent relationship without having to search for the path from the root to the node. If parent pointers are not available but children pointers are, we can use the path function. In our implementations of trees, we implement both parent and children pointers.

Parameters:

node – The root node.

Returns:

List of ancestor nodes.

AlgoTree.utils.average_distance(node: Any) → float

Compute the average distance between all pairs of nodes in the subtree rooted at the current node.

Parameters:

node – The node.

Returns:

The average distance between all pairs of nodes.

AlgoTree.utils.breadth_first(node: Any, func: Callable[[Any], bool], max_lvl=None, **kwargs) → bool

Traverse the tree in breadth-first order. The function func is called on each node and level. The function should have a side-effect you want to achieve, and if it returns True, the traversal will stop. The keyword arguments are passed to func.

If func returns True, the traversal will stop and the traversal will return True immediately. Otherwise, it will return False after traversing all nodes. This is useful if you want to find a node that satisfies a condition, and you want to stop the traversal as soon as you find it.

Requirement:

• This function requires that the node has a children property that is iterable.

• The function func should have the signature:

  func(node: Any, **kwargs) -> bool
  

Parameters:

• node – The root node.

• func – The function to call on each node and any additional keyword arguments. We augment kwargs with a level key, too, which specifies the level of the node in the tree.

• max_lvl – The maximum number of levels to descend. If None, the traversal will continue until all nodes are visited or until func returns True.

• kwargs – Additional keyword arguments to pass to func.

Raises:

• TypeError – If func is not callable.

• AttributeError – If the node does not have a ‘children’.

Returns:

None

AlgoTree.utils.breadth_first_undirected(node, max_hops=inf)

Traverse the tree in breadth-first order. It treats the tree as an undirected graph, where each node is connected to its parent and children.

AlgoTree.utils.depth(node) → int

Get the depth of a node in its subtree view.

Parameters:

node – The node.

Returns:

The depth of the node.

AlgoTree.utils.descendants(node) → List

Get the descendants of a node.

Parameters:

node – The root node.

Returns:

List of descendant nodes.

AlgoTree.utils.distance(node1: Any, node2: Any) → int

Find the distance between two nodes.

Parameters:

• node1 – The first node.

• node2 – The second node.

Returns:

The distance between the two nodes.

AlgoTree.utils.find_node(node: Any, pred: Callable[[Any], bool], **kwargs) → Any

Find closest descendent node of node that satisfies a predicate (where distance is defined with respect to path length). Technically, an order defined by path length is a partial order, sine many desendents that satisfy the condition may be at the same distance from node. We leave it up to each implementation to define which among these nodes to return. Use find_nodes if you want to return all nodes that satisfy the condition (return all the nodes in the partial order).

The predicate function pred should return True if the node satisfies the condition. It can also accept any additional keyword arguments, which are passed to the predicate. Note that we also augment the keyword arguments with a level key, which specifies the level of the node in the tree, so you can use this information in your predicate function.

Parameters:

• pred – The predicate function which returns True if the node satisfies the condition.

• kwargs – Additional keyword arguments to pass to pred.

Returns:

The node that satisfies the predicate.

AlgoTree.utils.find_nodes(node: Any, pred: Callable[[Any], bool], **kwargs) → List[Any]

Find nodes that satisfy a predicate.

Parameters:

• pred – The predicate function.

• kwargs – Additional keyword arguments to pass to pred.

Returns:

List of nodes that satisfy the predicate.

AlgoTree.utils.find_path(source: Any, dest: Any, bidirectional: bool = False) → List

Find the path from a source node to a destination node.

Parameters:

• source – The source node.

• dest – The destination node.

Returns:

The path from the source node to the destination node.

AlgoTree.utils.height(node) → int

Get the height of a subtree (containing the node node, but any other node in the subtree would return the same height)

Parameters:

node – The subtree containing node.

Returns:

The height of the subtree.

AlgoTree.utils.is_internal(node) → bool

Check if a node is an internal node.

Parameters:

node – The node to check.

Returns:

True if the node is an internal node, False otherwise.

AlgoTree.utils.is_isomorphic(node1, node2)

Check if two (sub)trees are isomorphic. To check if two trees are isomorphic, just pass in the root nodes of the trees.

This is another kind of equivalence: two nodes are equivalent if they have the same substructure (extensic relations), but the names and payloads of the nodes (intrinsic relations) can be different.

We ignore the parents of the nodes in this comparison. If we also included the parents, this would be the same as calling is_isomorphic on the root nodes of the trees.

Parameters:

• node1 – The root node of the first tree.

• node2 – The root node of the second tree.

Returns:

True if the trees are isomorphic, False otherwise.

AlgoTree.utils.is_leaf(node) → bool

Check if a node is a leaf node.

Parameters:

node – The node to check.

Returns:

True if the node is a leaf node, False otherwise.

AlgoTree.utils.is_root(node) → bool

Check if a node is a root node.

Parameters:

node – The node to check.

Returns:

True if the node is a root node, False otherwise.

AlgoTree.utils.lca(node1, node2, hash_fn=None) → Any

Find the lowest common ancestor of two nodes.

Parameters:

• node1 – The first node.

• node2 – The second node.

Returns:

The lowest common ancestor of the two nodes.

AlgoTree.utils.leaves(node) → List

Get the leaves of a node.

Parameters:

node – The root node.

Returns:

List of leaf nodes.

AlgoTree.utils.map(node: Any, func: Callable[[Any], Any], order: str = 'post', **kwargs) → Any

Map a function over the nodes in the tree rooted at node. It is a map operation over trees. In particular, the function func, of type:

func : Node -> Node,

is called on each node in pre or post order traversal. The function should return a new node. The tree rooted at node will be replaced (in-place) with the tree rooted at the new node. The order of traversal can be specified as ‘pre’ or ‘post’.

Requirement:

• This function requires that the node has a children property that is iterable and assignable, e.g., node.children = [child1, child2, …].

Parameters:

• node – The root node to start the traversal.

• func – The function to call on each node. The function should take a single argument, the node, and return a new node (or have some other side effect you want to achieve).

• order – The order of traversal (pre or post).

• kwargs – Additional keyword arguments to pass to func.

Raises:

• ValueError – If the order is not ‘pre’ or ‘post’.

• TypeError – If func is not callable.

Returns:

The modified node. If func returns a new node, the tree rooted at node will be replaced with the tree rooted at the new node.

AlgoTree.utils.node_stats(node, node_name: ~typing.Callable = <function <lambda>>, payload: ~typing.Callable = <function <lambda>>) → dict

Gather statistics about the current node and its subtree.

Parameters:

• node – The current node in the subtree.

• node_name – A function that returns the name of a node. Defaults to returning the node’s name property.

• payload – A function that returns the payload of a node. Defaults to returning the node’s payload property.

Returns:

A dictionary containing the statistics.

AlgoTree.utils.node_to_leaf_paths(node: Any) → List

List all node-to-leaf paths in a tree. Each path is a list of nodes from the current node node to a leaf node.

Example: Suppose we have the following sub-tree structure for node A:

A
├── B
│   ├── D
│   └── E
└── C
    └── F

Invoking node_to_leaf_paths(A) enumerates the following list of paths:

[[A, B, D], [A, B, E], [A, C, F]]

Parameters:

node – The current node.

Returns:

List of paths in the tree under the current node.

AlgoTree.utils.path(node: Any) → List

Get the path from the root node to the given node.

Parameters:

node – The node.

Returns:

The path from the root node to the given node.

AlgoTree.utils.paths_to_tree(paths: List, type: Type, max_tries: int = 1000) → type

Convert a list of paths to a tree structure. Each path is a list of nodes from the root to a leaf node. (A tree can be uniquely identified by this list of paths.)

Example: Suppose we have the following list of paths:

paths = [ ["A", "B", "D"], ["A", "B", "E"], ["A", "C", "F"] ]

We can convert this list of paths to a tree structure using the following code:

tree = paths_to_tree(paths, TreeNode)

This will create the following tree structure:

A
├── B
│   ├── D
│   └── E
└── C
    └── F

For some tree-like data structures, it may be the case that the names of nodes must be unique. We can use the max_tries parameter to try to create a node with a unique name like the one provided by suffixing the name with an integer.

Parameters:

• paths – The list of paths.

• type – The type of the tree node.

• max_tries – The maximum number of tries to create a node with a unique name.

AlgoTree.utils.prune(node: Any, pred: Callable[[Any], bool], **kwargs) → Any

Prune the tree rooted at node by removing nodes that satisfy a predicate. The predicate function should return True if the node should be pruned. It can also accept any additional keyword arguments, which are passed to the predicate.

Parameters:

• node – The root node.

• pred – The predicate function which returns True if the node should be pruned.

• kwargs – Additional keyword arguments to pass to pred.

Returns:

The pruned tree.

AlgoTree.utils.siblings(node) → List

Get the siblings of a node.

Parameters:

node – The node.

Returns:

List of sibling nodes.

AlgoTree.utils.size(node: Any) → int

Get the size of the subtree under the current node.

Parameters:

node – The node.

Returns:

The number of descendents of the node.

AlgoTree.utils.subtree_centered_at(node: Any, max_hops: int) → Any

Get the subtree centered at a node within a certain number of hops from the node. We return a subtree rooted at some ancestor of the node, or the node itself, that contains all nodes within max_hops hops from the node.

Parameters:

node – The node.

Returns:

The subtree centered at the node.

AlgoTree.utils.subtree_rooted_at(node: Any, max_lvl: int) → Any

Get the subtree rooted at a node whose descendents are within a certain number of hops it. We return a subtree rooted the node itself, that contains all nodes within max_hops hops from the node.

Parameters:

node – The node.

Returns:

The subtree centered at the node.

AlgoTree.utils.visit(node: Any, func: Callable[[Any], bool], order: str = 'post', max_hops: int = inf, **kwargs) → bool

Visit the nodes in the tree rooted at node in a pre-order or post-order traversal. The procedure proc should have a side-effect you want to achieve, such as printing the node or mutating the node in some way.

If func returns True, the traversal will stop and the traversal will return True immediately. Otherwise, it will return False after traversing all nodes.

Requirement:

• This function requires that the node has a children property that is iterable.

Parameters:

• node – The root node to start the traversal.

• func – The function to call on each node. The function should take a single argument, the node. It should have some side-effect you want to achieve. See map if you want to return a new node to rewrite the sub-tree rooted at node.

• max_hops – The maximum number of hops to traverse.

• order – The order of traversal (pre, post, or level).

• kwargs – Additional keyword arguments to pass to func.

Raises:

• ValueError – If the order is not valid.

• TypeError – If func is not callable.

• AttributeError – If the node does not have a ‘children’.

Module contents