4 ms·
Why is general graph isomorphism needed for that?
by espes 11y ago
Why is general graph isomorphism needed for that?
- ThePhysicist 11y agoProbably it isn't, but if there was a general-purpose algorithm that I could just use without doing any hand-crafted optimizations that would be a huge win. As you said, finding a good solution is usually possible but it requires applying a lot of (reasonable) approximations and shortcuts.
- espes 11y agoBut it sounds like your model isn't a general graph? DAG and tree isomorphism is in P (and pretty straightforward), and so is tree edit distance...
- ThePhysicist 11y agoASTs are DAGs indeed, but as soon as you add semantic information to the mix the graph usually becomes cyclic.