2 ms·
Take a look at Carl Hewitt's Same-Fringe solution, which flattens structures concurrently and compares the final (aka leave) nodes: http://www.nsl.com/papers/s
by jcynix 1y ago
Take a look at Carl Hewitt's Same-Fringe solution, which flattens structures concurrently and compares the final (aka leave) nodes:
http://www.nsl.com/papers/samefringe.htm http://www.nsl.com/papers/samefringe.htm
If you flatten both of your trees/graphs and regard the output as strings of nodes, you reduce your task to a substring search.
Now if you want to verify if the structures and not just the leave nodes are identical, you might be able to encode structure information into you strings.
- ninetyninenine 1y agoThanks. Good solution. I was thinking in terms of finding all subgraph isomorphisms. But this definitely is O(N) if all you need is one solution. But then I thought about it even further and this reduces to sliding window problem. In this case you still need to travel to each node in the window to see if there’s a match. So it cannot be that you traverse each node once. Not if you want to find all possible subgraph isomorphisms. Imagine a string that is a fractal of substrings: rrrrrrrrrrrrrrrrrrrrrrrrrrrr And the other one: rrrrrrr Right? The sliding window for rrrrrrr will be 7 in length and you need to traverse that entire window every time you move it. So by that fact alone every node is traversed at least 7 times.