0

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

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} 之间的相似性。

我能发现最多的是子图同构问题，它试图确定一个子图是否匹配（是一个更大的图的一部分）。这不是我的愿望。

我的主要任务是确定两个子图（路径）有多相似，它们都存在于我知道的图中。

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

提前致谢。

4

1 回答 1

1

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

如果将每个路径的顶点序列存储在列表或数组中，则可以使用以下实现计算距离（假设您有一个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用作输入，但重新实现它以使用数组应该很简单。

于 2015-02-04T15:48:19.590 回答