TravelingSalesman

MLModule

genre	Marker
author	Ola Friman
package	FMEwork/ReleaseMeVis
dll	MLXMarkerUtils
definition	MLXMarkerUtils.def
see also	XMarkerShortestPath
keywords	xmarker, xmarkerlist, traveling, salesman, optimal, shortest, path, route

Purpose

The module TravelingSalesman tries to find the shortest path that visits all spatial positions of the XMarkers in the input XMarkerList.

In the output XMarkerList, the XMarkers are ordered according to the shortest path found. That is, the TravelingSalesman module can be used to order a set of points in a meaningful way, e.g., to reconstruct a curve from an unordered set of points.

NOTE: The algorithm takes a long time when more than 30 points are connected. Therefore, there is currently a limit of 30 input XMarkers.

Details

An exhaustive search is employed to find the shortest path. The search is pruned connecting only neighboring points. The number of neighbors to consider is given as a parameter by the user. With fewer neighbors to consider, the search is faster. However, a shorter path may be found if more neighbors are considered. Moreover, in some situations it is not possible to find a path at all when too few neighbors are considered.

Windows

Default Panel

Input Fields

inputXMarkerList

name: inputXMarkerList, type: MLBase

An XMarkerList containing 1 to 30 XMarkers. If there are more than 30 input XMarkers, only the first 30 will be considered.

Output Fields

outputXMarkerList

name: outputXMarkerList, type: MLBase

An XMarkerList with the same XMarkers as in the input XMarkerList (max 30), but ordered according to the shortest path.

If no path could be found, the output is empty.

Parameter Fields

Visible Fields

Update

name: updateButton, type: Trigger

If pressed, the module computes anew.

Auto update

name: autoUpdateToggle, type: Bool, default: TRUE

If checked, the module computes anew on any parameter or input change.

Number of Neighbors

name: nbrNeighbors, type: Integer, default: 2

Sets the number of neighbors to consider when searching for the optimal path.

A lower value (2-3) makes the search significantly faster. With a larger number, a better path can in some situations be found. Moreover, with a low number of neighbors values there are situations where there is no path that visits all points. In this case, the output is empty.

Path Length

name: pathLength, type: Double, default: 0

Shows the path length if a shortest path was found.