图中距离顶点最远的 K 个点 edu.uci.ics.jung
K farthest points from vertex in graph edu.uci.ics.jung
我想在 jung implementation of directed graph 中找到距给定顶点最远的 K 个点。
我认为 BFSDistanceLabeler 可以胜任。但是，它不提供 api 用于返回 K 个最远点，因此我必须通过遍历图形中的所有顶点并调用 getDistance 方法来手动完成。或者有更好的方法吗？
但对我来说还有更大的挑战。尽管该图是有向的，但我想将其视为距离标签器的无向图。是否有可能以某种方式从有向图快速切换到无向图？
为什么我需要将图视为无向图？
我在后续步骤中分析了一个非常大的网络（数百万个顶点）。在每一步中，网络的一小部分（数千个顶点）被加载到图形中并进行分析。此分析需要有向图并提供必须位于加载区域中心的一个特定顶点的结果。
当我从步骤 A 移动到步骤 B 时，我可以删除之前的整个图表并创建一个新图表。然而，这将非常耗时。因为我知道我的新兴趣点与前一个顶点很接近，所以可以重复使用很大一部分图。
这就是为什么我需要为新的主顶点移除 K 个最远的顶点，并用该顶点周围的新顶点替换它们。
让我们看一下带有图形的底部图片，假设顶点 1 是我们感兴趣的顶点。由于该图是有向顶点，因此 6 号顶点最远。但是，如果图被视为无向图，那么顶点 4 将是最远的，这就是我需要的。
没有比查找到所有顶点的距离更快速地找到距给定输入顶点的所有最远顶点的方法。
您可以通过调用getVerticesInOrderVisited()，然后从'tail'开始以相反的顺序遍历列表来更有效地获取最远的顶点：这个列表应该按照距离的递增顺序填充根（集合），所以只需从列表中获取顶点，直到每个顶点的距离开始减小。
（注意：这不会拾取可能与根顶点完全断开连接的顶点，您可能认为这是 "farthest"；getUnvisitedVertices() 会这样做。）
回答你的第二个问题*：本质上你想要做的是将有向边视为无向边。 JUNG 允许您这样做；例如，您可以调用 getNeighbors() 而不是 getSuccessors()/getPredecessors()。
正如您所推断的那样，BFSDistanceLabeler 不会这样做；如果它存在，它想要尊重边缘方向，所以它使用 getSuccessors()。
所以这里有一些选择：
使用jung.algorithms.transformation.DirectionTransformer.toUndirected()。这非常简单，但涉及创建一堆新的（无向）边
创建覆盖 labelDistances() 的 BFSDistanceLabeler 的子类，并将 getSuccessors() 替换为 getNeighbors()。这很简单，即使不是很优雅。
创建一个覆盖 getSuccessors() 的 GraphDecorator 子类以在其委托图上调用 getNeighbors()。然后创建您的子类的一个实例，其中您的原始图形是委托。
这是最优雅和通用的解决方案。 （在某些时候，我们提供为您执行此操作的实用程序可能会有用；请随时在 JUNG GitHub 页面上提交问题：https://github.com/jrtom/jung/issues）
希望对您有所帮助。
*为了将来参考，请将不相关的问题拆分为单独的 Whosebug 问题；这使他们更容易回答和查找。
我想在 jung implementation of directed graph 中找到距给定顶点最远的 K 个点。
我认为 BFSDistanceLabeler 可以胜任。但是，它不提供 api 用于返回 K 个最远点，因此我必须通过遍历图形中的所有顶点并调用 getDistance 方法来手动完成。或者有更好的方法吗？
但对我来说还有更大的挑战。尽管该图是有向的，但我想将其视为距离标签器的无向图。是否有可能以某种方式从有向图快速切换到无向图？
为什么我需要将图视为无向图？
我在后续步骤中分析了一个非常大的网络（数百万个顶点）。在每一步中，网络的一小部分（数千个顶点）被加载到图形中并进行分析。此分析需要有向图并提供必须位于加载区域中心的一个特定顶点的结果。
当我从步骤 A 移动到步骤 B 时，我可以删除之前的整个图表并创建一个新图表。然而，这将非常耗时。因为我知道我的新兴趣点与前一个顶点很接近，所以可以重复使用很大一部分图。
这就是为什么我需要为新的主顶点移除 K 个最远的顶点，并用该顶点周围的新顶点替换它们。
让我们看一下带有图形的底部图片，假设顶点 1 是我们感兴趣的顶点。由于该图是有向顶点，因此 6 号顶点最远。但是，如果图被视为无向图，那么顶点 4 将是最远的，这就是我需要的。
没有比查找到所有顶点的距离更快速地找到距给定输入顶点的所有最远顶点的方法。
您可以通过调用getVerticesInOrderVisited()，然后从'tail'开始以相反的顺序遍历列表来更有效地获取最远的顶点：这个列表应该按照距离的递增顺序填充根（集合），所以只需从列表中获取顶点，直到每个顶点的距离开始减小。
（注意：这不会拾取可能与根顶点完全断开连接的顶点，您可能认为这是 "farthest"；getUnvisitedVertices() 会这样做。）
回答你的第二个问题*：本质上你想要做的是将有向边视为无向边。 JUNG 允许您这样做；例如，您可以调用 getNeighbors() 而不是 getSuccessors()/getPredecessors()。
正如您所推断的那样，BFSDistanceLabeler 不会这样做；如果它存在，它想要尊重边缘方向，所以它使用 getSuccessors()。
所以这里有一些选择：
使用
jung.algorithms.transformation.DirectionTransformer.toUndirected()。这非常简单，但涉及创建一堆新的（无向）边创建覆盖
labelDistances()的BFSDistanceLabeler的子类，并将getSuccessors()替换为getNeighbors()。这很简单，即使不是很优雅。创建一个覆盖
getSuccessors()的GraphDecorator子类以在其委托图上调用getNeighbors()。然后创建您的子类的一个实例，其中您的原始图形是委托。 这是最优雅和通用的解决方案。 （在某些时候，我们提供为您执行此操作的实用程序可能会有用；请随时在 JUNG GitHub 页面上提交问题：https://github.com/jrtom/jung/issues）
希望对您有所帮助。
*为了将来参考，请将不相关的问题拆分为单独的 Whosebug 问题；这使他们更容易回答和查找。