java - 任何用于图中子图(路径)匹配的库或建议的解决方案？

Question

例如，有一个图，可以表示为邻接矩阵为

G = {{ 0, 1, 0 }, { 1, 0, 1 }, { 1, 0, 0 }}

因此，有四个有向边:

node_1 to node_2, node_2 to node_3, node_2 to node_1 and node_3 to node_1.

我想要的是计算子图(路径) {node_2 到 node_3} 和子图(路径) {node_2 到 node_3 到 node_1} 之间的相似度。

我发现最多的是子图同构问题，它试图确定子图是否与更大的图匹配(是其一部分)。这不是我的愿望。

我的主要任务是确定两个子图(路径)的相似程度，这两个子图都存在于我已知的图中。

您可以推荐任何现有的方法吗？文件？示例代码？

提前致谢。

Answer 1

Levenshtein distance通过计算将一个序列更改为另一个序列所需的单元素版本的数量来测量两个序列之间的差异。

如果您将每个路径的顶点序列存储在列表或数组中，您可以使用以下实现来计算距离(假设您有一个 Vertex 类型):

int levenshteinDistance(List<Vertex> path, int lenPath, List<Vertex> other, int lenOther) {
    if (path.equals(other)) return 0;
    if (lenPath == 0) return lenOther;
    if (lenOther == 0) return lenPath;

    int cost;
    if (path.get(lenPath - 1).equals(other.get(lenOther - 1))) {
        cost = 0;
    } else {
        cost = 1;
    }

    int dist1 = levenshteinDistance(path, lenPath - 1, other, lenOther) + 1;
    int dist2 = levenshteinDistance(path, lenPath, other, lenOther - 1) + 1;
    int dist3 = levenshteinDistance(path, lenPath - 1, other, lenOther - 1) + cost;
    return Math.min(dist1, Math.min(dist2, dist3));
}

但是，这是低效的，因为它重新计算许多子序列的距离。更有效的实现可以在 http://rosettacode.org/wiki/Levenshtein_distance#Java 找到。 。请注意，它使用 String 作为输入，但重新实现它以使用数组应该很简单。