Tree Edits

Implements tree edits, i.e. functions which take a tree as input and return a changed tree.

class edist.tree_edits.Deletion(index)
Deletes node self._index and raises all its children to the parent
node. Note that deleting the root node of the tree results in a forest instead of a tree.
_index

The index of the tree node to which this edit is applied.

Type:int
apply(nodes_orig, adj_orig)

Deletes node self._index and raises all its children to the parent node. Note that deleting the root node of the tree results in a forest instead of a tree.

Parameters:
  • nodes (list) – a node list.
  • adj (list) – an adjacency list.
Returns:

  • nodes (list) – a copy of nodes with the applied edit.
  • adj (list) – a copy of adj with the applied edit.
apply_in_place(nodes, adj)

Deletes node self._index and raises all its children to the parent node. Note that deleting the root node of the tree results in a forest instead of a tree.

Parameters:
  • nodes (list) – a node list.
  • adj (list) – an adjacency list.
class edist.tree_edits.Edit

An abstract parent class for all edits.

apply(nodes, adj)

Applies this edit to the given tree and returns a copy of the tree with the applied changes. The original tree remains unchanged.

Parameters:
  • nodes (list) – a node list.
  • adj (list) – an adjacency list.
Returns:

  • nodes (list) – a copy of nodes with the applied edit.
  • adj (list) – a copy of adj with the applied edit.
apply_in_place(nodes, adj)

Applies this edit to the given tree. Note that this changes the input arguments.

Parameters:
  • nodes (list) – a node list.
  • adj (list) – an adjacency list.
class edist.tree_edits.Insertion(parent_index, child_index, label, num_children=0)
Inserts a new node with label self._label as self._child_index’th
child of node self._parent_index and uses the next self._num_children right siblings of itself as its children.
_parent_index

The index of the tree node to which we add a new child.

Type:int
_label

The label for the new child node.

Type:str
_child_index

The new node will be the _child_indexth child of node _parent_index.

Type:int
_num_children

The number of right siblings that will be used as new grandchildren.

Type:int
apply(nodes_orig, adj_orig)

Inserts a new node with label self._label as self._child_index’th child of node self._parent_index and uses the next self._num_children right siblings of itself as its children.

Note that inserting a new child at the root leads to a forest instead of a tree structure.

Parameters:
  • nodes (list) – a node list.
  • adj (list) – an adjacency list.
Returns:

  • nodes (list) – a copy of nodes with the applied edit.
  • adj (list) – a copy of adj with the applied edit.
apply_in_place(nodes, adj)

Inserts a new node with label self._label as self._child_index’th child of node self._parent_index and uses the next self._num_children right siblings of itself as its children.

Note that inserting a new child at the root leads to a forest instead of a tree structure.

Parameters:
  • nodes (list) – a node list.
  • adj (list) – an adjacency list.
class edist.tree_edits.Replacement(index, label)

Replaces the label of node self._index with self._label.

_index

The index of the tree node to which this edit is applied.

Type:int
_label

The new label for the self._indexth node.

Type:str
apply(nodes_orig, adj)

Replaces the label of node self._index with self._label.

Parameters:
  • nodes (list) – a node list.
  • adj (list) – an adjacency list.
Returns:

  • nodes (list) – a copy of nodes with the applied edit.
  • adj (list) – a copy of adj with the applied edit.
apply_in_place(nodes, adj)

Replaces the label of node self._index with self._label.

Parameters:
  • nodes (list) – a node list.
  • adj (list) – an adjacency list.
class edist.tree_edits.Script(lst=[])

A list of Edits.

apply(nodes_orig, adj_orig)

Applies all edits in this script.

Parameters:
  • nodes (list) – a node list.
  • adj (list) – an adjacency list.
Returns:

  • nodes (list) – a copy of nodes with the applied edits.
  • adj (list) – a copy of adj with the applied edits.
apply_in_place(nodes, adj)

Applies all edits in this script.

Parameters:
  • nodes (list) – a node list.
  • adj (list) – an adjacency list.
edist.tree_edits.alignment_to_script(alignment, x_nodes, x_adj, y_nodes, y_adj)

Converts the given alignment into an edit script which maps the given tree x to the given tree y such that all tuples in the alignment correspond to exactly one edit in the script.

Note that the order of operations does change because the script will first apply replacements (in input order), then deletions (in descending order), and finally insertions (in ascending order), which simplifies conversion.

The precise algorithm is described in the paper: https://arxiv.org/abs/1805.06869

Parameters:
  • alignment (class alignment.Alignment) – an Alignment object which maps between the given trees x and y.
  • x_nodes (list) – the node list of tree x.
  • x_adj (list) – the adjacency list of tree x.
  • y_nodes (list) – the node list of tree y.
  • y_adj (list) – the adjacency list of tree y.
Returns:

script – A Script object script such that script.apply(x_nodes, x_adj) = (y_nodes, y_adj) where every Tuple in the alignment has one corresponding edit.
Return type:

class tree_edits.Script
edist.tree_edits.get_roots(adj)

Returns all roots of a forest, described by an adjacency list.

Parameters:adj (list) – an adjacency list
Returns:roots – a list of roots, ascendingly sorted.
Return type:list
edist.tree_edits.num_descendants(adj, filter_set)

Counts the number of descendants of each node which are _not_ members of the given filter set.

Parameters:
  • adj (list) – an adjacency list
  • filter_set (set_like) – a set excluding some node indices
Returns:

out – A list which contains, for each node, the number of descendants not from the filter set.
Return type:

list