java - 图 edu.uci.ics.jung 中距顶点最远的 K 个点

Question

我想在 jung implementation of directed graph 中找到距给定顶点最远的 K 个点。

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

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

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

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

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

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

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

Answer 1

与查找到所有顶点的距离相比，没有一种渐近更快的方法来查找距给定输入顶点的所有最远顶点。

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

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

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

正如您所推断的，BFSDistanceLabeler 不会执行此操作；它希望尊重边缘方向(如果存在)，因此它使用 getSuccessors()。 所以这里有一些选择:

1. 使用jung.algorithms.transformation.DirectionTransformer.toUndirected()。这非常简单，但涉及创建一堆新的(无向的)边

2. 创建 BFSDistanceLabeler 的子类，重写 labelDistances()，并将 getSuccessors() 替换为 getNeighbors() 。这很简单，即使不是很优雅。

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

希望这有帮助。

*为了将来引用，请将不相关的问题分成单独的 StackOverflow 问题；这使他们更容易回答和找到。