例如,有一个图,它可以用邻接矩阵表示为
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.我想要的是计算子图(path) {node_2到node_3}和子图(path) {node_2到node_3到node_1}之间的node_2相似性。
我最能找到的是子图同构问题,它试图确定一个子图是否与一个较大的图相匹配。这不是我的愿望。
我的主要任务是确定两个子图(路径)是如何相似的,这两个子图都存在于我已知的一个图中。
您可以推荐现有的方法吗?文件?示例代码?
提前谢谢。
发布于 2015-02-04 15:48:19
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));
}然而,这是低效的,因为它重新计算了许多子序列的距离。在distance#Java中可以找到更有效的实现。注意,它使用String作为输入,但是重新实现它以使用数组应该很简单。
https://stackoverflow.com/questions/28325024
复制相似问题