时间戳

首页 > 解决方案 > 在有向图中查找具有权重限制的两个顶点之间的所有路径

java - 在有向图中查找具有权重限制的两个顶点之间的所有路径

问题描述

我试图在可能有循环但没有自循环的有向加权图中找到两个顶点之间的所有路径，这些顶点的权重小于N。到目前为止，我只能通过使用AllDirectedPaths然后过滤掉权重大于 N 的路径来做到这一点：

SimpleDirectedWeightedGraph<String, DefaultWeightedEdge> g = new SimpleDirectedWeightedGraph<>(DefaultWeightedEdge.class);
AllDirectedPaths<String, DefaultWeightedEdge> allPaths = new AllDirectedPaths<>(g);
int maxWeight = 30;
List<GraphPath<String, DefaultWeightedEdge>> pathsLimitedByWeight = allPaths.getAllPaths(startVertex, endVertex, false, maxWeight / minGraphLatency)
    .filter(graphPath -> graphPath.getWeight() < maxWeight)
    .collect(Collectors.toList());

这种方法显然不是最理想的，因为对于较大的图它很慢。为了限制输出并使其更快，我提供maxPathLength给AllDirectedPaths#getAllPaths，我将其设置为路径可以具有的最大权重除以图中边具有的最小权重，因为在我的情况下，边权重是整数并且总是大于1.

我考虑过使用KShortestSimplePathscustom PathValidator，但它只支持简单的路径，即不允许循环。

如果有的话，我在 jgrapht 中有什么其他选项可以用来解决查找所有路径而不必自己遍历图形。

标签： javagraph-theoryjgrapht

解决方案

没有一种算法可以让您有效地查询一对顶点之间的所有非简单路径。可以有成倍增长的路径。想象一个具有以下边的图：(s,u),(u,v),(v,u),(u,t)，其中所有边的长度为 1。现在找到从 s 到 t 的所有非简单路径，重量限制为 N。您将获得以下路径：

  • s,u,t
  • s,u,v,u,t
  • s,u,v,u,v,u,t
  • s,u,v,u,v,u,v,u,t
  • ……

你可以继续循环 [u,v,u] 直到你最终达到体重限制。如果这确实是您想要的，我建议您实施一个简单的标签算法。标签编码部分路径。标签保留对其前一个标签的引用，对与标签关联的节点的引用，以及等于标签表示的部分路径的总成本的成本。通过为成本为 0 的源节点 s 创建一个标签来启动算法，并将其添加到一个开放标签队列中。在算法的每次迭代中，从打开的队列中轮询一个标签，直到队列耗尽。对于与节点 i 关联且成本为 c 的轮询标签 L，展开标签：对于节点 i 的每个邻居 j，创建一个新标签 L'，该标签指向标签 L，并将其成本设置为 c 加上边权重 d_ij。如果新标签的成本 L' 超出可用预算，丢弃标签。否则，如果 j 是目标节点，我们找到了一条新路径，所以存储标签以便我们以后可以恢复路径。否则，将 L' 添加到打开标签的队列中。可以在下面找到该算法的简单实现。

笔记：

  1. 上述标记算法仅在图相对较小、N 较低或边权重较高时才有效，因为从 s 到 t 的可能路径的数量会增长得非常快。
  2. 上述算法的性能可以通过包含一个可接受的启发式算法来计算完成从给定节点到终端的路径所需的最少预算量来略微提高。这将允许您修剪一些标签。
  3. 所有边的权重都必须大于 0。
import org.jgrapht.*;
import org.jgrapht.graph.*;

import java.util.*;

public class NonSimplePaths<V,E> {

    public List<GraphPath<V, E>> computeNoneSimplePaths(Graph<V,E> graph, V source, V target, double budget){
        GraphTests.requireDirected(graph); //Require input graph to be directed
        if(source.equals(target))
            return Collections.emptyList();

        Label start = new Label(null, source, 0);
        Queue<Label> openQueue = new LinkedList<>(); //List of open labels
        List<Label> targetLabels = new LinkedList<>(); //Labels associated with target node
        openQueue.add(start);

        while(!openQueue.isEmpty()){
            Label openLabel = openQueue.poll();
            for(E e : graph.outgoingEdgesOf(openLabel.node)){
                double weight = graph.getEdgeWeight(e);
                V neighbor = Graphs.getOppositeVertex(graph, e, openLabel.node);

                //Check whether extension is possible
                if(openLabel.cost + weight <= budget){
                    Label label = new Label(openLabel, neighbor, openLabel.cost + weight); //Create new label
                    if(neighbor.equals(target)) //Found a new path from source to target
                        targetLabels.add(label);
                    else //Must continue extending the path until a complete path is found
                        openQueue.add(label);
                }
            }
        }

        //Every label in the targetLabels list corresponds to a unique path. Recreate paths by backtracking labels
        List<GraphPath<V,E>> paths = new ArrayList<>(targetLabels.size());
        for(Label label : targetLabels){ //Iterate over every path
            List<V> path = new LinkedList<>();
            double pathWeight = label.cost;
            do{
                path.add(label.node);
                label=label.pred;
            }while(label != null);
            Collections.reverse(path); //By backtracking the labels, we recoved the path in reverse order
            paths.add(new GraphWalk<>(graph, path, pathWeight));
        }

       return paths;
   }

    private final class Label{
        private final Label pred;
        private final V node;
        private final double cost;

        private Label(Label pred, V node, double cost) {
            this.pred = pred;
            this.node = node;
            this.cost = cost;
        }
    }

    public static void main(String[] args){
        Graph<String,DefaultWeightedEdge> graph = new SimpleDirectedWeightedGraph<>(DefaultWeightedEdge.class);
        Graphs.addAllVertices(graph, Arrays.asList("s","u","v","t"));
        graph.addEdge("s","u");
        graph.addEdge("u","t");
        graph.addEdge("u","v");
        graph.addEdge("v","u");
        graph.edgeSet().forEach(e -> graph.setEdgeWeight(e,1.0)); //Set weight of all edges to 1

        NonSimplePaths<String,DefaultWeightedEdge> nonSimplePaths = new NonSimplePaths<>();
        List<GraphPath<String,DefaultWeightedEdge>> paths = nonSimplePaths.computeNoneSimplePaths(graph, "s", "t", 10);
        for(GraphPath<String,DefaultWeightedEdge> path : paths)
            System.out.println(path+" cost: "+path.getWeight());
    }
}

上述示例代码的输出：

[s, u, t] cost: 2.0
[s, u, v, u, t] cost: 4.0
[s, u, v, u, v, u, t] cost: 6.0
[s, u, v, u, v, u, v, u, t] cost: 8.0
[s, u, v, u, v, u, v, u, v, u, t] cost: 10.0

提高上述实现的性能，例如通过添加一个可接受的启发式，我将作为练习留给 OP。

推荐阅读