如何找到两条路径的相同边缘？

Question

路径由向量表示，包含节点 ID。路径中的边缘有方向。

给定两条路径，例如：<1,6,11,7,2,5 ...> 和 <3, 4, 8, 2, 7,3, 1,6...>，这里 <1,6> 是同一条边。有时边缘是连续的，有时不是。最好在这些边缘之间放置一个标志。例如， (1,2) * (5,7,9) * (6,11,12), 是相同的边 1->2, 5->7,7->9, 6->11, 11->12,但是从 2 到 5 或 9 到 6 没有边。所以放一个 '*' 或其他符号作为标志。

有没有人有一些想法？我将不胜感激。

Answer 1

假设每个节点只有一条入边和一条出边。将 P1 称为长度为 n 的第一条路径，将 P2 称为长度为 m 的第二条路径。您可以将 P2 变成哈希图 startEdge -> endEdge（例如 <3,4,5> 将变成 [3->4, 4->5]）。

然后对于 P1 的每个元素，比如数字 i，您将 P1(i+1) 与 Hashmap(key= P1(i)) 进行比较。如果 hashmap 没有键或有键但具有不同的值，则您没有共同边，否则您有。

（如果一个节点有多个边，hashmap 的值可以是 Ints 的集合，你会检查 P1(i+1) 是否包含在 Hashmap(key=P1(i)) 中）。

Answer 2

这是 Clojure 中的示例解决方案：

(defn same-edges [& paths]
  (->> paths
       (map (comp set (partial partition 2 1)))
       (apply clojure.set/intersection)))

因此，对于每条路径（map 在所有 paths 中），您 partition 将路径分成 2 元素子路径（使用步长 1 来获取所有对的相邻项)，然后计算从该分区获得的所有 unique 对的 set。然后你找到所有这些集合的intersection。

示例：

(same-edges [1 6 11 7 2 5] [3 4 8 2 7 3 1 6])
;=> #{(1 6)}

换句话说，由向量[1 6 11 7 2 5]和[3 4 8 2 7 3 1 6]表示的两条路径之间的共享边集只包含一项：对(1 6).

如何找到两条路径的相同边缘？

How to find same edges of two paths?

graph-algorithm