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

java graph-theory jgrapht

2022-09-04 04:38:03

我试图在有向加权图中找到权重小于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());

这种方法显然是次优的，因为对于较大的图形，它很慢。为了限制输出并使其更快，我将其设置为路径的最大权重除以图形中边缘的最小权重，因为在我的情况下，边缘权重是整数并且始终大于1。maxPathLengthAllDirectedPaths#getAllPaths

我考虑过将KShortestSimplePaths与自定义PathValidator一起使用，但它只支持简单路径，即不允许循环。

在jgrapht中，我还有哪些其他选项（如果有的话）可以用来解决查找所有路径的问题，而不必自己遍历图形。

答案 1

没有任何算法可以让您有效地查询一对顶点之间的所有非简单路径。可以有指数级的路径。想象一个具有以下边缘的图形：（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' 添加到打开的标签队列中。可以在下面找到此算法的简单实现。

笔记：

上述标记算法仅在图形相对较小、N 较低或边缘权重较高时才有效，因为从 s 到 t 的可能路径数可以增长得非常快。
通过包含允许的启发式算法来计算完成从给定节点到终端的路径所需的最少预算，可以略微提高上述算法的性能。这将允许您修剪一些标签。
所有边权重都必须大于 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作为练习。

答案 2