开发者

subgraphs in a graph

开发者 https://www.devze.com 2023-02-17 04:19 出处:网络
I have a main graph and another small graph, suppose that the small graph could be repeated in the main graph as a su开发者_开发技巧bgraph with a degree of similarity(not necessarily the same small gr

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


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.

0

精彩评论

暂无评论...
验证码 换一张
取 消

关注公众号