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<>();

for (TLcdXYPoint aNode : nodes) {
}

for (TLcdXYLine aEdge : edges) {
(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;

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<>();

for (TLcdXYPoint aNode : nodes) {
}

for (TLcdXYLine aEdge : edges) {
(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()));
}
}
}``````