Investigate approximate matching

[ESultanik]

Allow the user to specify a given epsilon of matching cost, and find a matching that is at most that epsilon from the cost of the optimal matching.

[ivanistheone]

How do you plan to make approximate matching work? User provides a function that takes two nodes and returns a "distance" factor?

I have a use case in mind for a tree of content nodes that have a special content_id attribute on them which I can use for exact matching, e.g. if nodeA.content_id == nodeB.content_id the match is 100% (or distance 0).

I posted some links about that here and looking forward to trying graphtage on the tree fixtures I have.

[ESultanik]

Graphtage already has an internal notion of edit distance, which is what it uses to output its progress bar when run from a TTY. The idea would be to:

1. allow the user to specify a maximum edit distance (defaulting to zero), and produce a result that is at most that distance from optimal; and/or
2. immediately print out the best solution found thus far when Graphtage receives a SIGTERM.

It sounds like you might be trying to do something slightly different, though. You might actually be able to do what you want using Graphtage's not-yet-very-well-documented --match-if argument. If you can provide a more detailed example of input files, I could try and give you an example of its usage.

[ESultanik]

Status check against master (9fe0d58, v0.4.0): neither half of my 2020 plan is on master.

There is no epsilon option. Grepping the package for epsilon, approximat, and tolerance turns up only unrelated docstrings about memory estimates. And KeyboardInterrupt still discards whatever the search had found (graphtage/__main__.py:408), so there is no way to stop a long diff and keep the best result so far.

Both were prototyped at the time, on the 14-approximate-matching branch: df79da4 "Options to short-circuit the optimization when close to optimal" and 969b9af "Handle KeyboardInterrupt and return current progress". That branch is now 370 commits behind master and was never merged, so treat it as a sketch of the approach rather than something to rebase.

@ivanistheone, to answer the question you asked here: what you described is a different feature, and it exists now. --match-if and --match-unless take a Python expression over the plain values of two nodes and constrain which pairs the matcher will consider. For your content nodes, --match-if "from['content_id'] == to['content_id']" pairs only nodes that share an identifier. They were undocumented when you asked; they are described in --help now, and #168 corrected --match-if so it constrains matching the way --match-unless always did.

Keeping this open for the epsilon-bounded matching it originally described.