subgraphs in a graph

Question

I have a main graph and another small graph, suppose that the small graph could be repeated in the main graph as a subgraph with a degree of similarity(not necessarily the same small graph) What's a good algorithm (or Java library) to find them all?

Answer 1

I think you are trying to solve the Subgraph Isomorphism Problem which is known to be NP-complete. That means, there is likely no fast algorithm to do what you need. Your requirement of similarity (and not only isomorphism) only adds another complexity.

The Wikipedia page talks about Ulmann's algorithm that solves this problem in polynomial time (fast) for certain classes of graphs, you might give it a try.