标签: graph-algorithm

我有一个有向图，其中有两条有向路径。

我想要一种算法来确定两条路径之间的相似性。

这篇文章提到使用编辑距离来确定近似相似度。我还意识到汉明距离使用类似的度量。

我的问题是：

如何处理两条路径彼此平行的情况。也就是说，如果两条路径没有相似的节点，但仍将被视为“相似”，因为它们的路径在相同方向上行进且彼此非常接近。

谢谢

我有一个依赖图，我将其表示为 a Map<Node, Collection<Node>>（用 Java 来说，或者f(Node n) -> Collection[Node]作为函数；这是从给定节点n到依赖于 的节点集合的映射n）。该图可能是循环的*。

给定一个badlist节点列表，我想解决一个可达性问题：即生成一个Map<Node, Set<Node>> badmap表示从列表中的每个节点 Nbadlist到一组节点的映射，该组节点包括 N 或传递依赖于它的其他节点。

例子：

(x -> y means node y depends on node x)
n1 -> n2
n2 -> n3
n3 -> n1
n3 -> n5
n4 -> n2
n4 -> n5
n6 -> n1
n7 -> n1

这可以表示为邻接图{n1: [n2], n2: [n3], n3: [n1, n5], n4: [n2, n5], n6: [n1], n7: …

我正在开发一个程序，将对象分为两组，并且测量每个对象与其他对象的相似程度，并且我想找到将它们匹配在一起的最佳方法。

如果集合是由编辑距离定义的单词和距离，则集合“this”、“is”、“a”、“test”与“and”、“this”、“is”的最佳匹配， “最好”，那么我会将“this”与“this”（得分为0）匹配，“is”与“is”（得分为0），“a”与“and”（得分为0） 2)、“最佳”和“测试”（得分为 1）。

我已将问题简化为寻找最大二分匹配问题。这是一个描述：

给定一个边具有整数权重的二分图，找到一组边，使得 (a) 每个顶点在该组中只有一条边，并且 (b) 该组中的权重总和具有最大大小。

我不相信这个问题是 NP 完全的（或者，即使不是，但如果算法可能非常慢），是否有某种方法可以在一定程度上近似答案？

目前，我选择最小权重边，删除它及其连接的节点，然后重复，但这似乎不是最佳的。我考虑过将其简化为某种流程问题（就像处理正常的二分匹配一样），但在这种情况下它不起作用。

我有一个 DAG（有向无环图），它由边列表表示，例如

edges = [('a','b'),('a','c'),('b','d')]

将给出图表

a - > b -> d
|
v
c

我正在执行许多操作，我必须检查两个节点是否位于同一路径上（b并且d位于同一路径上，b而 和c不是来自上面的示例），这反过来又减慢了我的程序。我希望我能以某种方式遍历该图一次并保存所有路径，这样我就可以在恒定的时间内检查它。

这种加速可能吗？我将如何在 python 中实现它？

编辑：请注意，我需要检查两个方向，因此如果我有一对节点，(a,b)我需要检查atob和bto a。

无向图中的极小极大路径是两个顶点v、w之间的路径 ，其最小化路径上边的最大权重。

令T为给定图G=(V,E)的最小生成树。我如何证明，对于V中的任何一对顶点v, w ，在v和w之间始终存在一条完全在T上的极小极大路径。