← Back to context

Comment by ninetyninenine

1 year ago

Am I mistaken? Is what you say even possible?

Given two graphs one is a tree you cannot determine if the tree is a subgraph of the other graph in one walk through?

It’s only possible if you’re given additional information? Like a starting node to search from? I’m genuinely confused?

3 comments

ninetyninenine

Reply
jcynix  1 year 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

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  1 year ago

    Thanks. 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.