问题标签 [isomorphism]

可能的重复：
VF2 子图同构

我想用Java实现图同构算法，但由于编程经验少（也许逻辑也是如此），我面临很多问题。经过一些研究，我发现三种启发式算法可用：Ullman、Nauty 和 VF2。正如一些博士生告诉我的那样，VF2 被认为是最快且最容易实现的。我阅读了致力于 VF2 的论文，但不幸的是不了解它是如何工作的（在代码中）以及如何处理可行性规则。这里很多人参考C++代码实现，但不幸的是，链接打不开。此外，一位用户 (Rich Apodaca) 建议查看他的 VF2 实现 (MX) 供化学家使用，但没有指出哪些文件，只是大项目...... 请帮助我在 Java 中实现同构算法（更好的 VF2 因为速度）并指出 Java 或 C++ 中的工作代码（不是整个项目，我很难理解结构）（我不知道但至少我可以试试）。谢谢你。

我已经对平面 3 连通图的图同构主题进行了一些研究，但是有大量不同限制、理论复杂性和使用频率的算法，我很难找到一个突出的算法：

• 容易明白
• 可以以最大的清晰度实施
• 在小图（最多几十个顶点）上具有良好的实际性能

如果我自己不了解不同的算法，很难知道我是否更适合使用旧的、更专业的算法来解决这个问题，还是使用更新的、更通用的算法。在所有可能的候选人中，哪一个是最合适的？

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

我将开始一个关于自动机和图论的科学项目，我正在寻找一个支持以下功能的图形库：

• 有向/无向图
• 图同构测试（即图 g1 与 g2 同构吗？）
• 子图同构测试（即图 g1 是否与 g2 的子图同构？）
• 图表搜索、访问等
• 可能，非常快，因为我需要进行一些认真的计算

我知道Boost Graph Library，但据我从其文档中了解，它缺乏子图测试。

所以，我的问题是：请问哪个是最好的 c++ 图形库？他们不必为我需要的每个功能提供支持，我知道肯定有可能没有现有的库完全适合我的需求。

在算法设计手册中，它说

您是否在测试两棵树是否同构？– 对于图同构的某些特殊情况，例如树和平面图，存在更快的算法。也许最重要的案例是检测树之间的同构，这是语言模式匹配和解析应用程序中出现的问题。解析树通常用于描述文本的结构；如果基础文本对具有相同的结构，则两个解析树将是同构的。

我只是希望有人能给我一个例子，说明如何使用树同构来解决语言模式匹配问题。即，如何将语言模式匹配映射到树同构问题？

通常，如何将字符串或文本构造为树并比较它们的身份？

谢谢

我正在使用 *.jar 文件和图同构。我想检查两个 *.jar 文件之间的图形同构。是否有用于 python 或 ruby​​ 的库。我可以用 igraph 或什么来做吗？

谢谢。

简短的问题：同构函数在编程（即函数式编程）中的重要性是什么？

长问题：我试图根据我不时听到的一些术语，在函数式编程和类别理论中的概念之间进行一些类比。本质上，我试图将这些术语“解包”成具体的东西，然后我可以扩展。然后，我将能够使用术语，了解我在说什么。这总是很好。

我一直听到的这些术语之一是Isomorphism，我认为这是关于函数或函数组合之间等价的推理。我想知道是否有人可以提供一些关于同构属性派上用场的常见模式（在函数式编程中）的一些见解，以及获得的任何副产品，例如对同构函数进行推理的编译器优化。

具体来说，受 J 的共轭运算符 (g&.f = (f inverse)(g)(f)) 的启发，我需要一种方法来增加具有附加信息的函数。显而易见的方法是使用 ADT。就像是：

但是当大多数时候你只需要 forward 函数时，对应用程序函数的需求确实会损害代码的可读性。非常有用的是一个类：

（我认为 b 可以用存在量词隐含，但我不能确定我不会弄错签名）

现在应用程序将被隐式化，因此您可以只写

就像任何其他功能一样。前任：

那么你可以写这样的东西：

理想情况下，可以推断出类型签名

但是，这些语义似乎很复杂，因为您还需要修改 (.) 以支持 Applyable 而不是函数。有没有办法简单地欺骗类型系统将可应用数据类型视为所有正常目的的函数？是否有根本原因表明这是不可能的/一个坏主意？

有人可以向我展示如何将 Boost Graph Library 同构函数与顶点不变量一起使用的示例吗？我正在查看http://www.boost.org/doc/libs/1_50_0/libs/graph/example/isomorphism.cpp上的示例，它使用 degree_vertex_invariant()。但是，我想定义自己的不变函数，一个例子真的可以帮助我理解如何做到这一点。

以下是更多细节：

我在顶点上定义了一组离散属性，以便我可以用整数标记每个顶点。所以我有一个从任何顶点（g，v）到它的不变标签的映射，这是一个无符号整数。这些标签不一定是唯一的，即同一个图中的几个顶点可以共享同一个标签。所以假设我定义了一个函数：

我想这样称呼同构：

...但我收到一个错误：

定义discrete_vertex_invariant() 的正确方法是什么？

假设我有 2 个图 A 和 B，我想知道 A 是否是 B 的子图。节点包含属性，比如“大小”和“材料”。

当我运行时：

这仅按边匹配图，而不是按边和属性匹配。

关于如何检查属性的任何线索？

此外，假设 B 包含 A 的 2 个连通图。

当我运行时：

这将只输出 A 的一个子图。关于如何输出每个子图的任何想法？