CostGraphCheapestPath

MLModule

author	Christian Schumann
package	FMEstable/ReleaseMeVis
dll	MLCostGraph
definition	MLCostGraph.def
see also	XMarkerShortestPath, XMarkerListToCostGraph, CostGraphEdgeLengthCostPlugin, CostGraphGenericCostPlugin, CostGraphClosestVertex
keywords	marker, weight, shortest

Purpose

Runs the Dijkstra algorithm on a given cost graph (boost adjacency list) and tries to find the cheapest path connecting the given start and end vertex.

Usage

Connect a XMarkerListToCostGraph or a similar module to inCostGraph and define Start Vertex Index and End Vertex Index. You can use the module CostGraphClosestVertex to determine vertices close to given 3d points.

Details

The cost graph is a base object that carries a Boost graph in the form of an adjacency list. The Dijkstra implementation of Boost is then used to find the cheapest path connecting these two vertices in the graph.

Note: we do not use the term shortest path, but cheapest path as the used cost plugins may use other properties than length to compute edge costs.

Tips

The performance of this module depends on the number of edges in the input cost graph. Try to reduce the number of edges to speed up the computation. This can be done either by reducing the number of markers in the XMarkerList it was derived from or by choosing appropriate filter criteria in the used cost plugins!

Windows

Default Panel

Input Fields

inCostGraph

name: inCostGraph, type: MLBase

Base field containing the cost map in form of a boost graph.

Output Fields

outXMarkerList

name: outXMarkerList, type: MLBase

XMarkerList representing the found path.

Parameter Fields

Field Index

[]: Trigger	Status Code: Enum
Clear: Trigger	Status Message: String
doNotClearOnFailedUpdate: Bool	Update: Trigger
End Vertex Index: Integer
Has Valid Output: Bool
Number of Path Markers: Integer
On Input Change Behavior: Enum
Start Vertex Index: Integer

Visible Fields

Update

name: update, type: Trigger

Initiates update of all output field values.

Clear

name: clear, type: Trigger

Clears all output field values to a clean initial state.

On Input Change Behavior

name: onInputChangeBehavior, type: Enum, default: Clear, deprecated name: shouldAutoUpdate,shouldUpdateAutomatically

Declares how the module should react if a value of an input field changes.

Values:

Title	Name	Deprecated Name
​Update	​Update	​TRUE
​Clear	​Clear	​FALSE

Status Code

name: statusCode, type: Enum, persistent: no

Reflects module’s status (successful or failed computations) as one of some predefined enumeration values.

Values:

Title	Name
​Ok	​Ok
​Invalid input object	​Invalid input object
​Invalid input parameter	​Invalid input parameter
​Internal error	​Internal error

Status Message

name: statusMessage, type: String, persistent: no

Gives additional, detailed information about status code as human-readable message.

Has Valid Output

name: hasValidOutput, type: Bool, persistent: no

Indicates validity of output field values (success of computation).

[]

name: updateDone, type: Trigger, persistent: no

Notifies that an update was performed (Check status interface fields to identify success or failure).

Start Vertex Index

name: inStartVertexIndex, type: Integer, default: 0, minimum: 0

Index of the start vertex for path search.

End Vertex Index

name: inEndVertexIndex, type: Integer, default: 0, minimum: 0

Index of the end vertex for path search.

Number of Path Markers

name: outNumPathMarkers, type: Integer, persistent: no

Number of markers in the found path

Hidden Fields

doNotClearOnFailedUpdate

name: doNotClearOnFailedUpdate, type: Bool, persistent: no

Prevents automated clear after update failed. This does not affect status fields. It enables the developer to analyze module’s state after failure.