1

我想在有向图的 jung 实现中找到离给定顶点最远的 K 点。

我假设BFSDistanceLabeler完成了这项工作。但是，它没有提供返回 K 最远点的 api，所以我必须通过遍历图中的所有顶点并调用 getDistance 方法来手动完成。或者，还有更好的方法？

但对我来说还有一个更大的挑战。尽管该图是有向的，但我想将其视为距离标注器的无向。是否有可能以某种方式从有向图快速切换到其无向版本？

为什么我需要将图视为无向？

我在随后的步骤中分析了一个非常大的网络（数百万个顶点）。在每一步中，都会将一小部分网络（数千个顶点）加载到图中并进行分析。该分析需要有向图，并为必须位于加载区域中心的一个特定顶点提供结果。

当我从步骤 A 移动到步骤 B 时，我可以删除整个先前的图表并创建一个新图表。然而，这将非常耗时。因为我知道我感兴趣的新顶点接近前一个顶点，所以图的很大一部分可以重复使用。

这就是为什么我需要为新的主顶点删除 K 个最远的顶点，并用这个顶点周围的新顶点替换它们。

让我们看一下带有图形的底部图片，假设顶点 1 是我们感兴趣的顶点。由于图是有向的，6 号顶点是最远的。但是，如果图形被视为无向，那么顶点 4 将是最远的，这就是我需要的。

在此处输入图像描述

4

1 回答 1

2

没有比找到到所有顶点的距离更快的方法来找到距给定输入顶点最远的所有顶点。

您可以通过调用 更有效地获得最远的顶点getVerticesInOrderVisited()，然后从“尾部”开始以相反的顺序遍历列表：此列表应按与根（集合）的距离递增的顺序填充，因此只需从列表中获取顶点直到每个人的距离开始减少。

（注意：这不会拾取可能与根顶点完全断开的顶点，您可能认为它是“最远的”；getUnvisitedVertices()会这样做。）

回答你的第二个问题*：基本上你想要做的是将有向边视为无向的。JUNG 允许您这样做；例如，您可以调用，而不是使用getSuccessors()/ 。getPredecessors()getNeighbors()

正如您所推断的那样，BFSDistanceLabeler不要这样做；如果它存在，它想要尊重边缘方向，所以它使用getSuccessors(). 所以这里有一些选择：

  1. 使用jung.algorithms.transformation.DirectionTransformer.toUndirected(). 这很容易，但需要创建一堆新的（无向的）边

  2. 创建一个BFSDistanceLabeler覆盖的子类labelDistances()，并替换getSuccessors()为getNeighbors()。这很容易，即使不是很优雅。

  3. 创建一个GraphDecorator覆盖getSuccessors()调用getNeighbors()其委托图的子类。然后创建您的子类的实例，其中您的原始图是委托。这是最优雅和通用的解决方案。（在某些时候，我们为您提供执行此操作的实用程序可能会很有用；请随时在 JUNG GitHub 页面上提出问题：https ://github.com/jrtom/jung/issues ）

希望这可以帮助。

*为了将来参考，请将不相关的问题拆分为单独的 StackOverflow 问题；它使他们更容易回答和找到。

于 2016-06-03T17:12:51.590 回答