Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More
Socket
Sign inDemoInstall
Socket

abstracttree

Package Overview
Dependencies
Maintainers
1
Alerts
File Explorer

Advanced tools

Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

abstracttree

Abstract base classes for tree data structures

  • 0.0.5
  • PyPI
  • Socket score

Maintainers
1

This Python package contains a few abstract base classes for tree data structures. Trees are very common data structure that represents a hierarchy of common nodes. This package defines abstract base classes for these data structure in order to make code reusable.

Abstract base classes

from abstracttree import to_mermaid

to_mermaid(AbstractTree)
graph TD;
AbstractTree[AbstractTree];
UpTree[UpTree];
Tree[Tree];
MutableTree[MutableTree];
DownTree[DownTree];
Tree[Tree];
MutableTree[MutableTree];
MutableDownTree[MutableDownTree];
MutableTree[MutableTree];
BinaryDownTree[BinaryDownTree]
BinaryTree[BinaryTree]
AbstractTree-->UpTree;
UpTree-->Tree;
Tree-->MutableTree;
AbstractTree-->DownTree;
DownTree-->Tree;
DownTree-->MutableDownTree;
MutableDownTree-->MutableTree;
DownTree-->BinaryDownTree
BinaryDownTree-->BinaryTree
Tree-->BinaryTree

Downtrees are trees that have links to their direct children. Uptrees are trees that link to their parent. A Tree has links in both directions.

ABCInherits fromAbstract MethodsMixin Methods
AbstractTreenid, eqv()
UpTreeAbstractTreeparentroot, is_root, ancestors, path
DownTreeAbstractTreechildrennodes, descendants, leaves, levels, is_leaf, transform(), nodes.preorder(), nodes.postorder(), nodes.levelorder()
TreeUpTree, DownTreesiblings
MutableDownTreeDownTreeadd_child(), remove_child()add_children()
MutableTreeTree, MutableDownTreedetach()
BinaryDownTreeDownTreeleft_child, right_childchildren, nodes.inorder(), descendants.inorder()
BinaryTreeBinaryDownTree, Tree

In your own code, you can inherit from these trees. For example, if your tree only has links to children:

import abstracttree
from abstracttree import print_tree

class MyTree(abstracttree.DownTree):
    def __init__(self, value, children=()):
        self.value = value
        self._children = children
    
    def __str__(self):
        return "MyTree " + str(self.value)

    @property
    def children(self):
        return self._children

tree = MyTree(1, children=[MyTree(2), MyTree(3)])
print_tree(tree)

# This generates the following output:
# MyTree 1
# ├─ MyTree 2
# └─ MyTree 3

Adapter

In practice, not all existing tree data structures implement one of these abstract classes. As a bridge, you can use astree to convert these trees to a Tree instance. However, whenever possible, it's recommended to inherit from Tree directly for minimal overhead.

Examples:

# Trees from built-ins and standard library
astree(int)
astree(ast.parse("1 + 1 == 2"))
astree(pathlib.Path("abstracttree"))

# Anything that has parent and children attributes (anytree / bigtree / littletree)
astree(anytree.Node())

# Nested list
astree([[1, 2, 3], [4, 5, 6]])

# Tree from json-data
data = {"name": "a",
        "children": [
            {"name": "b", "children": []},
            {"name": "c", "children": []}
]}
astree(data, children=operator.itemgetter["children"])

# pyqt.QtWidget
astree(widget, children=lambda w: w.children(), parent = lambda w: w.parent())

# Tree from treelib
astree(tree.root, children=lambda nid: tree.children(nid), parent=lambda nid: tree.parent(nid))

# itertree
astree(tree, children=iter, parent=lambda t: t.parent)

# Infinite binary tree
inf_binary = astree(0, children=lambda n: (2*n + 1, 2*n + 2))

Utility functions

Pretty printing

tree = astree(seq, children=lambda x: [x[:-2], x[1:]] if x else [])
print_tree(tree)
print(to_string(tree))

# ['a', 'b', 'c', 'd']
# ├─ ['a', 'b']
# │  └─ ['b']
# └─ ['b', 'c', 'd']
#    ├─ ['b']
#    └─ ['c', 'd']
#       └─ ['d']

Plotting with matplotlib

import matplotlib.pyplot as plt

expr = ast.parse("y = x*x + 1")
plot_tree(expr)
plt.show()

images/tree_calc_plot.png

Export to various formats

to_dot(tree)
to_mermaid(tree)
to_latex(tree)

to_image(Path('.'), "filetree.png", how="dot")
to_image(AbstractTree, "class_hierarchy.svg", how="mermaid")
to_pillow(tree).show()

Find distance between nodes

import heapq

from abstracttree import HeapTree, Route

tree = HeapTree([5, 4, 3, 2, 1])
heapq.heapify(tree.heap)
left_child = tree.children[0]
right_child = tree.children[1]

route = Route(left_child, right_child)
print(f"{route.lca = }")  # => HeapTree([1, 2, 3, 5, 4], 0)
print(f"{route.nodes.count() = }")  # => 3
print(f"{route.edges.count() = }")  # => 2

A few concrete tree implementations

  • anytree
  • treelib
  • bigtree
  • itertree
  • dendropy
  • ete
  • littletree - also by me

Tree visualisation

Keywords

FAQs


Did you know?

Socket

Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.

Install

Related posts

SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

Packages

npm

Stay in touch

Get open source security insights delivered straight into your inbox.


  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc