在JGrapht中计算DijkstraShortestPath时出错 [英] Error when computing DijkstraShortestPath in JGrapht

问题描述

我正在编写Google Cloud Function，以从多边形中的给定源顶点返回多边形中的距离边界.我收到一条错误消息:

I am writing a Google Cloud Function to return a distance frontier in a Polygon from a given source Vertex within the polygon. I am getting an error message saying:

java.lang.IllegalArgumentException:图形必须包含源顶点！在org.jgrapht.alg.shortestpath.DijkstraShortestPath.getPaths(DijkstraShortestPath.java:154)中.

java.lang.IllegalArgumentException: Graph must contain the source vertex! at org.jgrapht.alg.shortestpath.DijkstraShortestPath.getPaths(DijkstraShortestPath.java:154).

上面的错误发生在下面的代码的以下行:

The above error occurs at the following line in the code below:

var paths = shortestPaths.getPaths(originVertex);

我收到的代码从HTTP请求接收JSON，其中定义了多边形，距离和原点.

The code I have receives JSON from the HTTP request defining the Polygon, the Distance and the Origin Vertex.

测试HTTP请求JSON是:

The test HTTP request JSON is:

{"polygon": [[30.0, 100.0], [50.0, 200.0], [220.0, 240.0], [440.0, 240.0], [430.0, 40.0], [230.0, 30.0], [85.0, 40.0]], "holes": [], "distance": 30, "origin": [50.0, 200.0]}

代码是:

package com.example;

import com.google.cloud.functions.HttpFunction;
import com.google.cloud.functions.HttpRequest;
import com.google.cloud.functions.HttpResponse;
import com.google.gson.Gson;
import com.google.gson.JsonElement;
import com.google.gson.JsonObject;
import com.google.gson.JsonArray;
import com.google.gson.JsonParseException;
import java.io.BufferedWriter;
import java.io.PrintWriter;
import java.util.logging.Logger;
import java.util.ArrayList;
import org.jgrapht.*;
import org.jgrapht.graph.*;
import org.jgrapht.traverse.*;
import org.jgrapht.alg.shortestpath.*;
import org.tinfour.common.IIncrementalTin;
import org.tinfour.common.IQuadEdge;
import org.tinfour.common.Vertex;
import org.tinfour.standard.IncrementalTin;
import org.tinfour.interpolation.NaturalNeighborInterpolator;
import org.tinfour.interpolation.IInterpolatorOverTin;



public class Example implements HttpFunction {
  Gson gson = new Gson();
  Logger logger = Logger.getLogger(Example.class.getName());
  @Override
  public void service(HttpRequest request, HttpResponse response) throws Exception {

    ArrayList<Vertex> polygon = new ArrayList<>();
    ArrayList<Vertex> holes = new ArrayList<>();
    double distance = 0;
    double greatestX = 0;
    double greatestY = 0;
    // ArrayList<double> origin = new ArrayList<>();
    double[] origin = {0, 0};

    // Parse JSON request and check for "name" field
    try {
      JsonElement requestParsed = gson.fromJson(request.getReader(), JsonElement.class);
      JsonObject requestJson = null;

      if (requestParsed != null && requestParsed.isJsonObject()) {
        requestJson = requestParsed.getAsJsonObject();
      }

      if (requestJson != null && requestJson.has("polygon")) {
        JsonArray polygonJA = requestJson.get("polygon").getAsJsonArray();
        for (JsonElement element : polygonJA) {
          JsonArray point = element.getAsJsonArray();
          double x = point.get(0).getAsDouble();
          double y = point.get(1).getAsDouble();
          double z = Double.NaN;
          if (x > greatestX) {
            greatestX = x;
          }
          if (y > greatestY) {
            greatestY = y;
          }
          polygon.add(new Vertex(x, y, z));
        }
      }
      if (requestJson != null && requestJson.has("holes")) {
        JsonArray holesJA = requestJson.get("holes").getAsJsonArray();
        for (JsonElement element : holesJA) {
          JsonArray point = element.getAsJsonArray();
          double x = point.get(0).getAsDouble();
          double y = point.get(1).getAsDouble();
          double z = Double.NaN;
          holes.add(new Vertex(x, y, z));
        }
      }
      if (requestJson != null && requestJson.has("distance")) {
        distance = requestJson.get("distance").getAsDouble();
      }
      if (requestJson != null && requestJson.has("origin")) {
        JsonArray distanceJA = requestJson.get("origin").getAsJsonArray();
        double x = distanceJA.get(0).getAsDouble();
        double y = distanceJA.get(1).getAsDouble();
        origin[0] = x;
        origin[1] = y;
        logger.severe("x is: " + origin[0]);
        logger.severe("y is: " + origin[1]);
      }
    } catch (JsonParseException e) {
      logger.severe("Error parsing JSON: " + e.getMessage());
    }

    IncrementalTin tin = new IncrementalTin();
    tin.add(polygon, null); // triangulates upon insertion

    Graph<Vertex, IQuadEdge> graph = new DefaultUndirectedWeightedGraph<>(IQuadEdge.class);

    tin.edges().forEach(e -> {
        if (e.isConstrainedRegionInterior() || e.isConstrainedRegionBorder()) {
            graph.addVertex(e.getA());
            graph.addVertex(e.getB());
            graph.addEdge(e.getA(), e.getB(), e);
            graph.setEdgeWeight(e.getA(), e.getB(), e.getLength());
        }
    });

    DijkstraShortestPath<Vertex, IQuadEdge> shortestPaths = new DijkstraShortestPath<>(graph);
    Vertex originVertex = tin.getNavigator().getNearestVertex(origin[0], origin[1]);

      logger.severe(graph.toString());
      logger.severe(originVertex.toString());
      logger.severe(polygon.toString());
    var paths = shortestPaths.getPaths(originVertex);

    IncrementalTin distanceMesh = new IncrementalTin();
    for (Vertex v : graph.vertexSet()) {
        var d = paths.getWeight(v);
        distanceMesh.add(new Vertex(v.x, v.y, d)); // add vertices with Z to new tin
    }

    IInterpolatorOverTin interpolator = new NaturalNeighborInterpolator(distanceMesh);

    JsonObject json = new JsonObject();
    JsonArray array = new JsonArray();
    
    for (double x = 0; x < greatestX; x++) {
        for (double y = 0; y < greatestY; y++) {
            double z = interpolator.interpolate(x, y, null);
            if (!Double.isNaN(z)) {
              JsonObject item = new JsonObject();
              item.addProperty("x", x);
              item.addProperty("y", y);
              array.add(item);
                // pixels[y * greatestX + x] = someColour;
            }
        }
    }
    json.add("pixels", array);

    var writer = new PrintWriter(response.getWriter());
    writer.printf(json.toString());

    // BufferedWriter writer = response.getWriter();
    // writer.write("Hello world!");
  }
}

pom.xml是:

<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
         xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
  <modelVersion>4.0.0</modelVersion>

  <groupId>cloudfunctions</groupId>
  <artifactId>http-function</artifactId>
  <version>1.0-SNAPSHOT</version>


  <properties>
    <maven.compiler.target>11</maven.compiler.target>
    <maven.compiler.source>11</maven.compiler.source>
  </properties>

  <dependencyManagement>
      <dependencies>
          <dependency>
              <groupId>org.tinfour</groupId>
              <artifactId>Tinfour</artifactId>
              <version>2.1.5</version>
              <scope>import</scope>
              <type>pom</type>
          </dependency>   
      </dependencies>
  </dependencyManagement>

  <dependencies>
    <dependency>
      <groupId>com.google.cloud.functions</groupId>
      <artifactId>functions-framework-api</artifactId>
      <version>1.0.1</version>
    </dependency>
    <dependency>
      <groupId>org.jgrapht</groupId>
      <artifactId>jgrapht-core</artifactId>
      <version>1.5.1</version>
    </dependency>
    <dependency>
        <groupId>org.tinfour</groupId>
        <artifactId>TinfourCore</artifactId>
        <version>2.1.5</version>
        <scope>provided</scope>
    </dependency>  
    <dependency>
      <groupId>org.jgrapht</groupId>
      <artifactId>jgrapht-ext</artifactId>
      <version>1.5.1</version>
    </dependency>
    <dependency>
      <groupId>com.google.code.gson</groupId>
      <artifactId>gson</artifactId>
      <version>2.8.6</version>
    </dependency>
  </dependencies>

  <!-- Required for Java 11 functions in the inline editor -->
  <build>
    <plugins>
      <plugin>
        <groupId>org.apache.maven.plugins</groupId>
        <artifactId>maven-compiler-plugin</artifactId>
        <version>3.8.1</version>
        <configuration>
          <excludes>
            <exclude>.google/</exclude>
          </excludes>
        </configuration>
      </plugin>
    </plugins>
  </build>
</project>

推荐答案

发生错误是因为 graph 中未包含 originVertex .

The error is occurring because the originVertex is not included in the graph.

tin.getNavigator().getNearestVertex()返回的顶点不包含在图形中，因为它没有考虑顶点是否受约束.它会返回最近的全局顶点，该顶点恰好是不受约束的(因此尚未插入图中).

tin.getNavigator().getNearestVertex() is returning a vertex that isn't included in the graph because it doesn't take into account whether a vertex is constrained or not. It's returning the nearest global vertex which happens to be unconstrained (and therefore hasn't been inserted into the graph).

您有两种选择可以避免该错误.

You have two options to avoid the error.

1. 在调用其余代码之前检查图形是否包含顶点(但是，仅当给定的原点位置在受约束区域内(或非常接近)时才会执行):

if (graph.containsVertex(originVertex)) {
   var paths = shortestPaths.getPaths(originVertex);
   ....
}

1. 始终查找最近的受约束的顶点；在这种情况下，您不能使用 tin.getNavigator().getNearestVertex().取而代之的是，遍历图顶点以找到最接近给定原点位置的顶点，或者将受约束的顶点插入到 k-d树之类的对象中，并查询该顶点以进行快速有效的最近邻计算.

1. Always find the nearest constrained vertex; in this case you can't use tin.getNavigator().getNearestVertex(). Instead, iterate over graph vertices to find the one closest to the given origin position, or insert the constrained vertices into something like a k-d tree and query that for fast and efficient nearest neighbour calculation.

这篇关于在JGrapht中计算DijkstraShortestPath时出错的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！