Calculating a route requires the following steps:

  1. Create a graph with nodes and edges

  2. Associate a value with each edge in the graph

  3. Optionally implement a heuristic distance function to speed up the route calculation

  4. Calculate the route

Creating the graph with nodes and edges

We start by setting up a model which represents all domain objects modelling the real world. This step requires no special actions, and can be done as in every other LuciadLightspeed application: 

// 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]);

The route calculation requires the creation of an ILcdGraph, fitting the needs of the application. This can be the default graph, TLcdGraph, a partitioned graph, TLcdPartitionedGraph, or an application-specific implementation like, e.g., a database-based graph.

For this tutorial, the default TLcdGraph is sufficient. 

// Create graph
TLcdGraph<TLcdXYPoint, TLcdXYLine> graph = new TLcdGraph<>();

This graph is still empty. We need to add nodes and edges to it. The minimum requirement for an object to become a valid node or edge object is to have a correct equals() and hashCode() implementation. Though this is enough for the default graph implementations provided with LuciadLightspeed, user-specific implementations can add extra requirements.

We first add the nodes to the graph:

// Add nodes to graph
for (TLcdXYPoint aNode : nodes) {
  graph.addNode(aNode, ILcdFireEventMode.NO_EVENT);
}

After that, we add the edges. An edge can only be added to a graph if the two nodes it connects are part of the graph. 

// Add edges to graph
for (TLcdXYLine aEdge : edges) {
  graph.addEdge(aEdge,
                (TLcdXYPoint) aEdge.getPoint(0),
                (TLcdXYPoint) aEdge.getPoint(1),
                ILcdFireEventMode.NO_EVENT);
}

Associate values with each edge of the graph

Our graph currently contains all nodes and edges, but there are no values associated with it. We call this an unweighted graph.

Before we can calculate a route, we need to convert this graph to a weighted graph. This is done by associating a value with each edge in the graph. Once a graph is weighted, the length of each route in the graph is defined, and shortest route problems can be computed.

Associating a value with each each requires the implementation of an ILcdEdgeValueFunction. In this example, we use the cartesian length of the edge as value: 

// 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);
  }
};

This is sufficient to calculate the shortest route. But to speed up the calculation, we also define a heuristic distance function before performing the calculation.

Add a heuristic distance function

A heuristic distance function is used to (significantly) speed up the calculation. This function should not return an exact value of a distance, but can perform a fast estimation.

The heuristic distance function should never overestimate the real distance between two nodes.

If not, an optimal solution cannot be guaranteed when calculating a route.

As heuristic function, we calculate the distance between two nodes in a straight line. This will result in:

  • An exact match for the distance when the two nodes are connected by a single edge

  • An underestimation of the distance when the two nodes are not connected by an edge

// 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);
  }
};

Calculate the shortest route

All information to compute the shortest route is now available. A shortest route is always computed between a preceding and a succeeding route, as in some cases, not only the start node and end node, but also the route leading to the start node and/or the route following the end node can influence the resulting route. One can easily create a zero-length TLcdRoute for the start and end node. 

// Compute the shortest route between two nodes
TLcdShortestRouteAlgorithm routeAlgorithm = new TLcdShortestRouteAlgorithm();

TLcdRoute<TLcdXYPoint, TLcdXYLine> precedingRoute = new TLcdRoute<>(graph, nodes[0]);
TLcdRoute<TLcdXYPoint, TLcdXYLine> succeedingRoute = new TLcdRoute<>(graph, nodes[3]);

ILcdRoute<TLcdXYPoint, TLcdXYLine> route =
    routeAlgorithm.getShortestRoute(graph,
                                    precedingRoute,
                                    succeedingRoute,
                                    edgeValueFunction,
                                    distanceFunction);

Now that the route is calculated, we can for example loop over its edges:

// Show the resulting route
StringBuilder s = new StringBuilder();
for (int i = 0; i < route.getEdgeCount(); i++) {
  TLcdXYLine edge = route.getEdge(i);
  ILcdPoint startPoint = edge.getStartPoint();
  ILcdPoint endPoint = edge.getEndPoint();
  s.append(String.format("Shortest route edge %d: (%.0f,%.0f) - (%.0f,%.0f)\n", i, startPoint.getX(), startPoint.getY(), endPoint.getX(), endPoint.getY()));
}
System.out.println(s);

resulting in:

Shortest route edge 0: (0,0) - (5,0)
Shortest route edge 1: (5,0) - (9,0)

Full code 

import com.luciad.network.algorithm.routing.TLcdShortestRouteAlgorithm;
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.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 ShortestRouteTutorial {
  public static void main(String[] aArgs) {
    // 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);
      }
    };

    // Compute the shortest route between two nodes
    TLcdShortestRouteAlgorithm routeAlgorithm = new TLcdShortestRouteAlgorithm();

    TLcdRoute<TLcdXYPoint, TLcdXYLine> precedingRoute = new TLcdRoute<>(graph, nodes[0]);
    TLcdRoute<TLcdXYPoint, TLcdXYLine> succeedingRoute = new TLcdRoute<>(graph, nodes[3]);

    ILcdRoute<TLcdXYPoint, TLcdXYLine> route =
        routeAlgorithm.getShortestRoute(graph,
                                        precedingRoute,
                                        succeedingRoute,
                                        edgeValueFunction,
                                        distanceFunction);

    // Show the resulting route
    StringBuilder s = new StringBuilder();
    for (int i = 0; i < route.getEdgeCount(); i++) {
      TLcdXYLine edge = route.getEdge(i);
      ILcdPoint startPoint = edge.getStartPoint();
      ILcdPoint endPoint = edge.getEndPoint();
      s.append(String.format("Shortest route edge %d: (%.0f,%.0f) - (%.0f,%.0f)\n", i, startPoint.getX(), startPoint.getY(), endPoint.getX(), endPoint.getY()));
    }
    System.out.println(s);
  }
}