时间戳

首页 > 解决方案 > 如何使用jgrapht修剪给定距离K的图？

graph - 如何使用jgrapht修剪给定距离K的图？

问题描述

我使用 jgrapht API 构建了一个图表。我有一个有向图。给定一个节点N，我必须创建一个包含所有距离为K的连接邻居的子图。

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

我有一个想法来手动实现它。

但是，这会导致所有节点之间的比较，想知道是否有更好的方法来做到这一点？

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

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

标签： graphjgrapht

解决方案

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

最简单的方法包括：

  1. 对于给定的输入顶点N，确定最多maxDistance远离 的所有顶点N。
  2. 返回一个诱导子图，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);
}

推荐阅读