When graphs become very large, the basic routing approach described in the Calculating the shortest route tutorial might not scale well enough anymore to perform sufficiently fast computations on the graph. Partitioning allows to improve both the memory and CPU usage by using specialized graphs and algorithms.
Initial setup
The initial setup of this tutorial is the same as what was done and explained in the Calculating the shortest route tutorial:
-
Create a graph with nodes and edges
-
Assign values to each edge
-
Implement a heuristic distance function
The resulting code is:
// Set up a model
TLcdXYPoint[] nodes = new TLcdXYPoint[4];
nodes[0] = new TLcdXYPoint(0, 0);
nodes[1] = new TLcdXYPoint(5, 0);
nodes[2] = new TLcdXYPoint(7, 5);
nodes[3] = new TLcdXYPoint(9, 0);
TLcdXYLine[] edges = new TLcdXYLine[4];
edges[0] = new TLcdXYLine(nodes[0], nodes[1]);
edges[1] = new TLcdXYLine(nodes[1], nodes[2]);
edges[2] = new TLcdXYLine(nodes[2], nodes[3]);
edges[3] = new TLcdXYLine(nodes[1], nodes[3]);
// Create graph
TLcdGraph<TLcdXYPoint, TLcdXYLine> graph = new TLcdGraph<>();
// Add nodes to graph
for (TLcdXYPoint aNode : nodes) {
graph.addNode(aNode, ILcdFireEventMode.NO_EVENT);
}
// Add edges to graph
for (TLcdXYLine aEdge : edges) {
graph.addEdge(aEdge,
(TLcdXYPoint) aEdge.getPoint(0),
(TLcdXYPoint) aEdge.getPoint(1),
ILcdFireEventMode.NO_EVENT);
}
// Implement edge value function
ILcdEdgeValueFunction<TLcdXYPoint, TLcdXYLine> edgeValueFunction = new ALcdSimpleEdgeValueFunction<TLcdXYPoint, TLcdXYLine>() {
@Override
public double computeEdgeValue(ILcdGraph<TLcdXYPoint, TLcdXYLine> aGraph, TLcdXYLine aEdge, TLcdTraversalDirection aTraversalDirection) {
//Calculate the cartesian length of the edge
double x = aEdge.getPoint(1).getX() - aEdge.getPoint(0).getX();
double y = aEdge.getPoint(1).getY() - aEdge.getPoint(0).getY();
return Math.sqrt(x * x + y * y);
}
};
// Implement heuristic distance function
ILcdDistanceFunction<TLcdXYPoint, TLcdXYLine> distanceFunction = new ALcdNodeDistanceFunction<TLcdXYPoint, TLcdXYLine>() {
@Override
public double computeDistance(ILcdGraph<TLcdXYPoint, TLcdXYLine> aGraph, TLcdXYPoint aStartNode, TLcdXYPoint aEndNode, TLcdTraversalDirection aTraversalDirection) {
double x = aEndNode.getX() - aStartNode.getX();
double y = aEndNode.getY() - aStartNode.getY();
return Math.sqrt(x * x + y * y);
}
};Partitioning a graph
Partitioning a graph can be done in many ways. The API provides a partitioning algorithm which is optimized for use with the partitioned routing algorithm, which we use in this tutorial:
// Partitioned routing
TLcdClusteredPartitioningAlgorithm partitioningAlgorithm =
new TLcdClusteredPartitioningAlgorithm();
ILcdPartitionedGraph<TLcdXYPoint, TLcdXYLine> partitionedGraph = partitioningAlgorithm.partition(graph);Preprocessing a graph
The main reason why the partitioned routing algorithm is so fast, is because it can take advantage of precomputed information representing a high-level description of the partitioned graph. Preprocessing can be done fully automatically using the partitioned routing preprocessor. The result of the preprocessing is a set of shortest route tables, one per partition in the graph.
TLcdPartitionedShortestRoutePreprocessor preprocessor = new TLcdPartitionedShortestRoutePreprocessor();
ILcdShortestRouteDistanceTableProvider<TLcdXYPoint, TLcdXYLine> distanceTableProvider =
preprocessor.preprocess(partitionedGraph,
edgeValueFunction,
distanceFunction);Computing the shortest route between two nodes
Once the graph has been partitioned and the shortest route tables have been precomputed, shortest routes can be computed the same way as with the basic routing algorithm
TLcdRoute<TLcdXYPoint, TLcdXYLine> precedingRoute = new TLcdRoute<>(graph, nodes[0]);
TLcdRoute<TLcdXYPoint, TLcdXYLine> succeedingRoute = new TLcdRoute<>(graph, nodes[3]);
TLcdPartitionedShortestRouteAlgorithm partitionedRouteAlgorithm = new TLcdPartitionedShortestRouteAlgorithm();
partitionedRouteAlgorithm.setDistanceTableProvider(distanceTableProvider);
ILcdRoute<TLcdXYPoint, TLcdXYLine> partitionedRoute = partitionedRouteAlgorithm.getShortestRoute(partitionedGraph,
precedingRoute,
succeedingRoute,
edgeValueFunction,
distanceFunction);
for (int i = 0; i < partitionedRoute.getEdgeCount(); i++) {
TLcdXYLine edge = partitionedRoute.getEdge(i);
ILcdPoint startPoint = edge.getStartPoint();
ILcdPoint endPoint = edge.getEndPoint();
System.out.println(String.format("Shortest route edge %d: (%.0f,%.0f) - (%.0f,%.0f)", i, startPoint.getX(), startPoint.getY(), endPoint.getX(), endPoint.getY()));
}The output of running this is
Shortest route edge 0: (0,0) - (5,0) Shortest route edge 1: (5,0) - (9,0)
Full code
import com.luciad.network.algorithm.partitioning.TLcdClusteredPartitioningAlgorithm;
import com.luciad.network.algorithm.routing.ILcdShortestRouteDistanceTableProvider;
import com.luciad.network.algorithm.routing.TLcdPartitionedShortestRouteAlgorithm;
import com.luciad.network.algorithm.routing.TLcdPartitionedShortestRoutePreprocessor;
import com.luciad.network.function.ALcdNodeDistanceFunction;
import com.luciad.network.function.ALcdSimpleEdgeValueFunction;
import com.luciad.network.function.ILcdDistanceFunction;
import com.luciad.network.function.ILcdEdgeValueFunction;
import com.luciad.network.graph.ILcdGraph;
import com.luciad.network.graph.TLcdGraph;
import com.luciad.network.graph.TLcdTraversalDirection;
import com.luciad.network.graph.partition.ILcdPartitionedGraph;
import com.luciad.network.graph.route.ILcdRoute;
import com.luciad.network.graph.route.TLcdRoute;
import com.luciad.shape.ILcdPoint;
import com.luciad.shape.shape2D.TLcdXYLine;
import com.luciad.shape.shape2D.TLcdXYPoint;
import com.luciad.util.ILcdFireEventMode;
public class PartitionedGraphTutorial {
public static void main(String[] args) {
// Set up a model
TLcdXYPoint[] nodes = new TLcdXYPoint[4];
nodes[0] = new TLcdXYPoint(0, 0);
nodes[1] = new TLcdXYPoint(5, 0);
nodes[2] = new TLcdXYPoint(7, 5);
nodes[3] = new TLcdXYPoint(9, 0);
TLcdXYLine[] edges = new TLcdXYLine[4];
edges[0] = new TLcdXYLine(nodes[0], nodes[1]);
edges[1] = new TLcdXYLine(nodes[1], nodes[2]);
edges[2] = new TLcdXYLine(nodes[2], nodes[3]);
edges[3] = new TLcdXYLine(nodes[1], nodes[3]);
// Create graph
TLcdGraph<TLcdXYPoint, TLcdXYLine> graph = new TLcdGraph<>();
// Add nodes to graph
for (TLcdXYPoint aNode : nodes) {
graph.addNode(aNode, ILcdFireEventMode.NO_EVENT);
}
// Add edges to graph
for (TLcdXYLine aEdge : edges) {
graph.addEdge(aEdge,
(TLcdXYPoint) aEdge.getPoint(0),
(TLcdXYPoint) aEdge.getPoint(1),
ILcdFireEventMode.NO_EVENT);
}
// Implement edge value function
ILcdEdgeValueFunction<TLcdXYPoint, TLcdXYLine> edgeValueFunction = new ALcdSimpleEdgeValueFunction<TLcdXYPoint, TLcdXYLine>() {
@Override
public double computeEdgeValue(ILcdGraph<TLcdXYPoint, TLcdXYLine> aGraph, TLcdXYLine aEdge, TLcdTraversalDirection aTraversalDirection) {
//Calculate the cartesian length of the edge
double x = aEdge.getPoint(1).getX() - aEdge.getPoint(0).getX();
double y = aEdge.getPoint(1).getY() - aEdge.getPoint(0).getY();
return Math.sqrt(x * x + y * y);
}
};
// Implement heuristic distance function
ILcdDistanceFunction<TLcdXYPoint, TLcdXYLine> distanceFunction = new ALcdNodeDistanceFunction<TLcdXYPoint, TLcdXYLine>() {
@Override
public double computeDistance(ILcdGraph<TLcdXYPoint, TLcdXYLine> aGraph, TLcdXYPoint aStartNode, TLcdXYPoint aEndNode, TLcdTraversalDirection aTraversalDirection) {
double x = aEndNode.getX() - aStartNode.getX();
double y = aEndNode.getY() - aStartNode.getY();
return Math.sqrt(x * x + y * y);
}
};
// Partitioned routing
TLcdClusteredPartitioningAlgorithm partitioningAlgorithm =
new TLcdClusteredPartitioningAlgorithm();
ILcdPartitionedGraph<TLcdXYPoint, TLcdXYLine> partitionedGraph = partitioningAlgorithm.partition(graph);
TLcdPartitionedShortestRoutePreprocessor preprocessor = new TLcdPartitionedShortestRoutePreprocessor();
ILcdShortestRouteDistanceTableProvider<TLcdXYPoint, TLcdXYLine> distanceTableProvider =
preprocessor.preprocess(partitionedGraph,
edgeValueFunction,
distanceFunction);
TLcdRoute<TLcdXYPoint, TLcdXYLine> precedingRoute = new TLcdRoute<>(graph, nodes[0]);
TLcdRoute<TLcdXYPoint, TLcdXYLine> succeedingRoute = new TLcdRoute<>(graph, nodes[3]);
TLcdPartitionedShortestRouteAlgorithm partitionedRouteAlgorithm = new TLcdPartitionedShortestRouteAlgorithm();
partitionedRouteAlgorithm.setDistanceTableProvider(distanceTableProvider);
ILcdRoute<TLcdXYPoint, TLcdXYLine> partitionedRoute = partitionedRouteAlgorithm.getShortestRoute(partitionedGraph,
precedingRoute,
succeedingRoute,
edgeValueFunction,
distanceFunction);
for (int i = 0; i < partitionedRoute.getEdgeCount(); i++) {
TLcdXYLine edge = partitionedRoute.getEdge(i);
ILcdPoint startPoint = edge.getStartPoint();
ILcdPoint endPoint = edge.getEndPoint();
System.out.println(String.format("Shortest route edge %d: (%.0f,%.0f) - (%.0f,%.0f)", i, startPoint.getX(), startPoint.getY(), endPoint.getX(), endPoint.getY()));
}
}
}