如何使用 jgrapht 修剪给定距节点 K 距离的图形？

Question

我使用 jgrapht API 构建了一个图表。我有一个有向图。给定一个节点 N，我必须创建一个子图，其中包含距离为 K.

的所有相连邻居

所以基本上给定一个节点和距离 K，我必须修剪图形，以便只保留距离为 K 的连接节点。

我有一个想法，动手实现。

我可以从节点列表中生成所有对之间的最短路径。
之后，我可以去掉超出距离K的节点。

但是这样会造成所有节点之间的比较，想知道有没有更好的方法呢？

此外，想知道 jgrapht 已经有一个 API 可以做到这一点。

（我已经查看了 jgrapht 的 API 但没有找到任何这样的 API）

Answer 1

我假设distance被定义为加权图中最短路径的长度，其中路径的长度由其边权重之和给出。我还假设只需要所有邻居都在输入顶点 N 的给定 maxDistance 内，并且不需要其中两个邻居也必须在 maxDistance 内彼此。

最简单的方法包括：

对于给定的输入顶点N，确定距离N最多maxDistance的所有顶点。
Return N 上的诱导子图加上它的（间接）邻居最多 maxDistance 个单位。

public <V,E> Graph<V, E> getSubgraph(Graph<V,E> graph, V source, double maxDistance){
   
    //Compute a shortest. Optionally we can limit the search to vertices that are maxDistance away
    DijkstraShortestPath<V,E> ds = new DijkstraShortestPath<>(graph, maxDistance);
    ShortestPathAlgorithm.SingleSourcePaths<V, E> shortestPaths = ds.getPaths(source);
    
    //Collect all neighboring vertices that are at most maxDistance units away
    Set<V> neighbors = graph.vertexSet().stream().filter(v -> shortestPaths.getWeight(v) <= maxDistance).collect(Collectors.toSet());
    
    //Return an induced subgraph on those vertices
    return new AsSubgraph<>(graph, neighbors);
}

如何使用 jgrapht 修剪给定距节点 K 距离的图形？

How to prune a graph given distance K from a node with jgrapht?

graph

jgrapht