1

在 Java 中寻找 VF2 的实现，它可以确定有向无环图 G1 是否同构于有向图 G2 的子图（不一定是诱导子图）。我相信在图同构问题的背景下，正确的术语是单态。任何算法还需要返回创建单态的顶点之间的映射。

正式地让 H = (VH, EH) 和 G = (V, E) 是有向图。是否存在函数 f : VH → V 使得如果 (u, v) ∈ EH, 那么 (f(u), f(v)) ∈ E。

如果它在java中不存在，c++中的VFLib会做我需要的。（我坚信它应该，但是术语让我陷入了一个循环，我希望在重新做我在 C++ 中所做的一切之前真正理解他们在说什么的人得到确认。）

有许多关于类似问题的建议，特别是 S-Space https://github.com/fozziethebeat/S-Space 但是 S-Space 仅指图同构而不是子图同构/单态。尝试在 https://github.com/fozziethebeat/S-Space/blob/master/src/main/java/edu/ucla/sspace/graph/isomorphism/VF2State.java阅读代码发现以下行：

/**
 * The number of nodes in {@code g1}
 */
private final int n1;

/**
 * The number of nodes in {@code g2}
 */
private final int n2;

public boolean isDead() {
    return n1 != n2 
        || t1bothLen != t2bothLen
        || t1outLen != t2outLen
        || t1inLen != t2inLen;        
}

这似乎表明它仅适用于图同构（因为具有不同数量节点的图将被拒绝）。但我距离真正感受代码还有很长的路要走。

除了 VFLib 和 networkx（python 并且不支持单态）之外，我无法判断给定的实现支持三个 VF2 选项（同构、子图同构、单态）中的哪一个。

任何帮助将不胜感激，谢谢

4

0 回答 0