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: 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);
The code I have receives JSON from the HTTP request defining the Polygon, the Distance and the Origin Vertex.
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]}
The code is:
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!");
}
}
The pom.xml is:
<?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>
The error is occurring because the originVertex is not included in the graph.
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.
if (graph.containsVertex(originVertex)) {
var paths = shortestPaths.getPaths(originVertex);
....
}
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.