A tracing algorithm finds:

  • all nodes within a certain distance of a node, and

  • their shortest routes from/to that node.

Searching for a contamination source in a pipeline or a river is a typical example of a tracing application.

Calculating a trace requires the following steps:

  1. Create a graph with nodes and edges

  2. Associate a value with each edge in the graph

  3. Setting up a trace handler to handle the result of the tracing calculations

  4. Calculate the trace

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 tracing algorithm 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 the trace 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);
  }
};

Set up a tracing result handler

The tracing algorithm provides intermediate results: each time a node is found, the algorithm will inform a handler about this node. This way, already found results can be displayed while the algorithm is still running. The tracing result handler should do what is appropriate to handle the results (storing, highlighting on a map, printing out, …​).

The ILcdTracingResultHandler we use in this example will simply print out some information about the found node. 

// Set up a tracing result handler
ILcdTracingResultHandler<TLcdXYPoint, TLcdXYLine> tracingHandler = new ILcdTracingResultHandler<TLcdXYPoint, TLcdXYLine>() {
  @Override
  public void handleNode(TLcdXYPoint aNode, ILcdRoute<TLcdXYPoint, TLcdXYLine> aShortestRoute, double aDistance) {
    StringBuilder s = new StringBuilder();
    s.append(String.format("Trace found to node (%.0f,%.0f). Distance to that node is %.0f\n", aNode.getX(), aNode.getY(), aDistance));
    s.append("The shortest route to that node is:\n");
    for (int i = 0; i < aShortestRoute.getEdgeCount(); i++) {
      TLcdXYLine edge = aShortestRoute.getEdge(i);
      ILcdPoint startPoint = edge.getStartPoint();
      ILcdPoint endPoint = edge.getEndPoint();
      s.append(String.format("Edge %d: (%.0f,%.0f) - (%.0f,%.0f)\n", i, startPoint.getX(), startPoint.getY(), endPoint.getX(), endPoint.getY()));
    }
    System.out.println(s);
  }
};

Trace the node

The route leading to the start node can influence the tracing results, and therefore one should specify the start point as a route. A distance need to be specified, to indicate within which distance traces should be searched (setting this distance too high can result in long computation times and high memory usage for large graphs). 

// Trace a node
TLcdTracingAlgorithm tracingAlgorithm = new TLcdTracingAlgorithm();
TLcdRoute<TLcdXYPoint, TLcdXYLine> precedingRoute = new TLcdRoute<>(graph, nodes[0]);

int distance = 10;
tracingAlgorithm.getSuccessors(graph,
                               precedingRoute,
                               edgeValueFunction,
                               tracingHandler,
                               distance);

This results in

Trace found to node (0,0). Distance to that node is 0
The shortest route to that node is:

Trace found to node (5,0). Distance to that node is 5
The shortest route to that node is:
Edge 0: (0,0) - (5,0)

Trace found to node (9,0). Distance to that node is 9
The shortest route to that node is:
Edge 0: (0,0) - (5,0)
Edge 1: (5,0) - (9,0)

Full code 

import java.io.IOException;

import com.luciad.network.algorithm.routing.ILcdTracingResultHandler;
import com.luciad.network.algorithm.routing.TLcdTracingAlgorithm;
import com.luciad.network.function.ALcdSimpleEdgeValueFunction;
import com.luciad.network.function.ILcdEdgeValueFunction;
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 TracingTutorial {
  public static void main(String[] aArgs) throws IOException {
    // 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);
      }
    };

    // Set up a tracing result handler
    ILcdTracingResultHandler<TLcdXYPoint, TLcdXYLine> tracingHandler = new ILcdTracingResultHandler<TLcdXYPoint, TLcdXYLine>() {
      @Override
      public void handleNode(TLcdXYPoint aNode, ILcdRoute<TLcdXYPoint, TLcdXYLine> aShortestRoute, double aDistance) {
        StringBuilder s = new StringBuilder();
        s.append(String.format("Trace found to node (%.0f,%.0f). Distance to that node is %.0f\n", aNode.getX(), aNode.getY(), aDistance));
        s.append("The shortest route to that node is:\n");
        for (int i = 0; i < aShortestRoute.getEdgeCount(); i++) {
          TLcdXYLine edge = aShortestRoute.getEdge(i);
          ILcdPoint startPoint = edge.getStartPoint();
          ILcdPoint endPoint = edge.getEndPoint();
          s.append(String.format("Edge %d: (%.0f,%.0f) - (%.0f,%.0f)\n", i, startPoint.getX(), startPoint.getY(), endPoint.getX(), endPoint.getY()));
        }
        System.out.println(s);
      }
    };

    // Trace a node
    TLcdTracingAlgorithm tracingAlgorithm = new TLcdTracingAlgorithm();
    TLcdRoute<TLcdXYPoint, TLcdXYLine> precedingRoute = new TLcdRoute<>(graph, nodes[0]);

    int distance = 10;
    tracingAlgorithm.getSuccessors(graph,
                                   precedingRoute,
                                   edgeValueFunction,
                                   tracingHandler,
                                   distance);
  }
}