Autochrome

Created on 2022-12-13T03:34:07-06:00

Return to the Index

This card pertains to a resource available on the internet.

This card can also be read via Gemini.

Adapts Djikstra's pathfinding algorithm to determine the minimum edit distance of two trees.

Location: cursor pointers in to source and target trees.

Cost: total size of all trees added or removed.

Source and target cursors have independent position stacks as they move, ascend, and descend indepdently.

Adjacency rules

When source and target cursors point to identical trees they may both advance.

Source cursor may advance without the target cursor: this is interpreted as deleting a tree.

Target cursor may advance without source cursor: this is interpreted as adding a new tree.

When both cursors are over a collection: descend in to the collection.

When both cursors are nil: ascend out of the collection.

When the source xor target cursor are nil: ascend only the nil cursor.

When the source or target cursor is over a branch: descend that cursor to first child node.