任何用于图内子图（路径）匹配的库或建议的解决方案？

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 作为输入，但重新实现它以使用数组应该很简单。

任何用于图内子图（路径）匹配的库或建议的解决方案？

Any library or proposed solution for subgraph (path) matching within a graph?

java

graph

pattern-matching

subgraph