子图匹配(JUNG)

Question

我有一组子图，我需要将它们与提取它们的图进行匹配。我还需要计算每个子图在这样的图中出现的次数(我需要存储所有可能的匹配)。考虑到子图和图的边的标签，必须有一个完美的匹配，但是顶点的标签不需要相互匹配。我使用JUNG api构建我的系统，所以我想要一个解决方案(api，算法等)，可以处理JUNG提供的图形结构。有什么想法吗？

Answer 1

嗯，我必须通过从头开始实现它来解决这个问题。我遵循了主题Any working example of VF2 algorithm?中建议的策略。因此，如果有人对这个问题也有疑问，我建议看看Rich Apodaca在前述主题中的答案。

Answer 2

JUNG的功能非常齐全，所以如果JUNG中没有您需要的图形分析算法，通常有很强的理论原因。对我来说，你的问题听起来像是子图同构问题的一个实例，这是NP-完全的：

http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem

您可能不熟悉NP-完备性(我花了7年的大学时间和计算机科学硕士学位才理解它！)，所以我在这里给出一个高层次的描述。某些问题，如排序，可以在相对于其输入大小的多项式时间内解决。例如，如果我有一个包含N个元素的列表，我可以在O(N log(N))时间内对其进行排序。更具体地说，如果我可以在多项式时间内解决问题，这意味着我可以在不耗尽所有可能的解决方案的情况下解决问题。在排序的情况下，我可以遍历列表的每个可能的排列，如果我找到了排序的列表的排列，则返回它。不过，这显然不是解决问题的最快方法！一些非常聪明的数学家能够将其降到理论上的最小值O(N log(N))，因此我们今天可以使用计算机非常快速地对非常大的列表进行排序。

另一方面，NP-Complete问题被认为没有多项式时间的解决方案(我说是因为从来没有人证明过这一点，尽管有证据表明确实是这样的)。无论如何，这意味着如果不首先用尽所有可能的解决方案，您就不能最终解决NP-Complete问题。NP完全问题的时间复杂度总是O(c ^ N)或更差，其中c是大于1的常数。这意味着解决问题所需的时间随着问题大小的增加而指数增长。

所以这和我的问题有什么关系？

这里我的意思是，如果子图同构问题是NP完全的，那么确定一个图是否是另一个图的子图的唯一方法就是穷尽所有可能的解决方案。因此，您可以解决这个问题，但可能最多只有几个节点的图(因为问题的时间复杂度随着图大小的增加而呈指数级增长)。这意味着为你的问题计算一个解决方案在计算上是不可行的，因为一旦你达到了一定的图大小，它就会花费很长的时间来寻找解决方案。

更实际的情况是，如果你的老板要求你做一件可以证明是NP完全的事情，你可以简单地说这是不可能的，他将不得不听你的。如果你的教授要求你做一件可以证明是NP-Complete的事情，向他证明这是NP-Complete，那么你很可能会在这门课上得到A。如果你想自己做一些NP-Complete的事情，最好是直接进入下一个项目……;)