{"id":6993,"library":"apted","title":"APTED Algorithm for Tree Edit Distance","description":"APTED (All Path Tree Edit Distance) is a Python library that implements the state-of-the-art algorithm for computing the tree edit distance between two ordered, labeled trees. It is a pure Python port of the original Java implementation. The current stable version is 1.0.3, with updates primarily focusing on maintenance due to its long-standing stability.","status":"maintenance","version":"1.0.3","language":"en","source_language":"en","source_url":"https://github.com/JoaoFelipe/apted","tags":["tree edit distance","algorithm","tree similarity","data structures","APTED"],"install":[{"cmd":"pip install apted","lang":"bash","label":"Install stable version"}],"dependencies":[],"imports":[{"symbol":"APTED","correct":"from apted import APTED"},{"note":"While 'from apted import Node' might work in some contexts, the canonical path is 'from apted.nodes import Node' for clarity and future compatibility.","wrong":"from apted import Node","symbol":"Node","correct":"from apted.nodes import Node"},{"note":"For parsing tree strings into Node objects.","symbol":"BracketStringInputParser","correct":"from apted.parser import BracketStringInputParser"},{"note":"The Python apted library (version 1.x) is a pure Python port and does not use or require JPype or a JVM. This pattern is from older, Java-dependent implementations and will cause errors.","wrong":"import jpype; apted.StartJVM()","symbol":"StartJVM"}],"quickstart":{"code":"from apted import APTED\nfrom apted.nodes import Node\n\n# Define a custom configuration for costs (optional, unit costs are default)\nclass CustomConfig(object):\n    def rename(self, node1, node2):\n        return 0 if node1.label == node2.label else 1\n    def cost_insert(self, node):\n        return 1\n    def cost_delete(self, node):\n        return 1\n\n# Create trees using the bracket notation string format\ntree1 = Node.from_string('{a{b}{c}}')\ntree2 = Node.from_string('{a{b{d}}}')\n\n# Initialize APTED with the two trees and the custom config\napted = APTED(tree1, tree2, CustomConfig())\n\n# Compute the tree edit distance\ndistance = apted.compute_edit_distance()\n\nprint(f\"Tree 1: {tree1.root.to_string()}\")\nprint(f\"Tree 2: {tree2.root.to_string()}\")\nprint(f\"Edit distance: {distance}\")","lang":"python","description":"This example demonstrates how to calculate the tree edit distance between two trees represented in bracket notation strings. It shows how to define a custom cost model for rename, insert, and delete operations, and then use the APTED class to compute the distance."},"warnings":[{"fix":"Do not attempt to import or use `jpype` or `StartJVM()` with the Python `apted` library. It is designed to run natively in Python.","message":"The `apted` Python library is a pure Python implementation and does not rely on Java or `jpype`. Older examples or discussions might refer to a `StartJVM()` function, which is not applicable to this Python package and will result in errors.","severity":"gotcha","affected_versions":"All Python `apted` 1.x versions"},{"fix":"Ensure your input tree strings strictly adhere to the bracket notation. For other formats (like JSON), you must implement your own conversion logic to the `Node` object structure or bracket notation.","message":"The library primarily supports tree input in a specific 'bracket notation' string format (e.g., `{A{B}{C}}`). Using malformed strings or attempting other formats directly will lead to parsing errors.","severity":"gotcha","affected_versions":"All Python `apted` 1.x versions"},{"fix":"Be aware that the Python version's feature set and performance are tied to its last release. If you need the absolute latest features or optimizations, consider looking at the original Java implementation or other tree similarity libraries.","message":"The `apted` library's primary Python package has not been updated since November 2017, meaning new features or significant performance improvements found in the actively developed Java version might not be present. While stable, development is slow for the Python port.","severity":"gotcha","affected_versions":"All Python `apted` 1.x versions"}],"env_vars":null,"last_verified":"2026-04-16T00:00:00.000Z","next_check":"2026-07-15T00:00:00.000Z","problems":[{"fix":"Remove any `import jpype` or calls to `apted.StartJVM()`. The Python `apted` library does not require a JVM.","cause":"Attempting to use a `StartJVM()` function that exists in Java-dependent APTED implementations but not in the pure Python `apted` library.","error":"AttributeError: module 'apted' has no attribute 'StartJVM'"},{"fix":"Carefully review your tree string for correct bracket notation syntax. Ensure all labels are properly enclosed (or not) and all braces are matched. If you have labels containing '{' or '}', they must be escaped as '\\{' or '\\}'.","cause":"The input tree string does not conform to the expected bracket notation. Common issues include unescaped curly braces within labels, unmatched braces, or incorrect nesting.","error":"apted.parser.errors.ParseError: Unexpected character 'X' at position Y"},{"fix":"Pass a configuration object to `APTED`. You can use the default `apted.config.Config()` for unit costs, or define your own custom class inheriting from `object` (or `Config`) and implement `rename`, `cost_insert`, and `cost_delete` methods.","cause":"The `APTED` constructor requires a `config` object (even if it's the default unit cost configuration). You might have forgotten to pass it or tried to initialize `APTED` with only the trees.","error":"TypeError: __init__() missing 1 required positional argument: 'config'"}]}