Given a directed acyclic graph
G and a path made up from its set of nodes
N, what is the closest approximate match to N, equipped with an intuitive notion of distance?
A path in a directed acyclic graph is essentially a string (that uses the set of nodes as the alphabet), so when comparing paths one can make use of edit distances developed for approximate string matching:
There are many algorithms for approximate string matching:
This string matching answers the question when the
G itself is also a path.. then we're merely asking to compare two strings.
Asking if an arbitrary graph
A built from the same set of nodes is a sub-graph of
G is the general case of the problem, but I'm only interested in the case where
A is a path and
G is directed & acyclic.
Any general pointers are also welcome.
Edit: I ended up using a dynamic programming algorithm, independently also suggested in the accepted answer. Good call! It is probably the most accurate option as well, and barely more "complex" than the string-to-string case when the average # of edges per node is low.