首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >图中的子图(路径)匹配的库或建议的解决方案?

问图中的子图(路径)匹配的库或建议的解决方案?
EN

Stack Overflow用户
提问于 2015-02-04 15:25:23
回答 1查看 184关注 0票数 0

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

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

因此,有四个定向边:

代码语言:javascript
复制
node_1 to node_2, node_2 to node_3, node_2 to node_1 and node_3 to node_1.

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

我最能找到的是子图同构问题,它试图确定一个子图是否与一个较大的图相匹配。这不是我的愿望。

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

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

提前谢谢。

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2015-02-04 15:48:19

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

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

代码语言:javascript
复制
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));
}

然而,这是低效的,因为它重新计算了许多子序列的距离。在distance#Java中可以找到更有效的实现。注意,它使用String作为输入,但是重新实现它以使用数组应该很简单。

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/28325024

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档