java - 子图匹配(JUNG)

Question

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

Answer 1

JUNG 的功能非常齐全，因此如果 JUNG 中没有适合您需要的图形分析算法，通常有一个强有力的理论原因。对我来说，你的问题听起来像是子图同构问题的一个实例，它是 NP-Complete:

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

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

另一方面，NP-Complete 问题被认为没有多项式时间解(我说认为是因为从来没有人证明过它，尽管证据确凿表明是这种情况)。无论如何，这意味着如果不先穷尽所有可能的解决方案，您就无法最终解决 NP 完全问题。 NP-Complete 问题的时间复杂度总是 O(c ^ N) 或更糟，其中 c 是某个常数大于 1。这意味着解决问题所需的时间随着问题规模的每次增加而呈指数增长。

那这跟我的问题有什么关系？？？

我要说的是，如果子图同构问题是 NP 完全问题，那么确定一个图是否是另一个图的子图的唯一方法是穷尽所有可能的解决方案。所以你可以解决这个问题，但可能最多只能解决几个节点左右的图(因为问题的时间复杂度随着图大小的每次增量增加而呈指数增长)。这意味着为您的问题计算一个解决方案在计算上是不可行的，因为一旦您达到特定的图大小时，将需要很长时间才能找到解决方案。

更实际地说，如果你的老板要求你做一些可证明是 NP 完全的事情，你可以简单地说这是不可能的，他将不得不听你的。如果您的教授要求您做一些可证明是 NP-Complete 的事情，请向他展示它是 NP-Complete，您可能会在类(class)中获得 A。如果你想自己做一些 NP-Complete，最好继续下一个项目......;)