Module: Bottlenecks

Description:

Finds bottlenecks in a graph from source to target. Each point of the graph contains a value corresponding to a size (e.g. a radius from a distance map computation), and the idea is to find, from each source point of the graph, the path to a target point having the largest bottleneck. Or in math speak, finding the max for all paths of the min along each path.

An example, shown with the Draw_Cubes module. Notes

There must be non-zero intersections between source and graph, and between target and graph.
The idea is to look at all paths for all the source points, but I cheat. I start looking for all paths in a breadth-first search like Dijkstra, but once I've found a path to a target (the shortest in terms of number of points), I set a limit path length. That way I don't look at the whole of the graph for each source point, it would take too long. The limit path length is the shortest path length multiplied by a user-specified limit factor.

Connections:

All connections are of type HxUniformScalarField3.

Graph

[required]
The input graph. I had in mind a curvilinear skeleton.

Source

[required]
The source points.

Target

[required]
The target points.

Ports:

Source threshold

Value that defines whether a pixel belong to the source or not.

Source comparison

Defines how the threshold is used to define the pixels of the source: should the pixel value be lower, lower or equal, greater, etc. than the threshold?

Target threshold

idem for the target.

Source comparison

idem for the target.

Graph threshold

idem for the graph.

Source comparison

idem for the graph.

Connectivity

Adjacency for the graph points.

Illustration of the different connectivities. (a): 6-, (b): 18-, and (c): 26-connectivity (in case you didn't figure it out, n-connectivity means n pixels in the neighbourhood).

Limit factor

Factor by which the shortest path length is multiplied to set a length limit to search for, for each source point. See Notes.

Action button

Push this button to start the computation.

Commands:

Additional options can be accessed when typing in the console Bottlenecks COMMAND_NAME.

`verbose`

Displays timing information after the computation. Retype to hide info.

`create`

Runs the computation. Returns the name of the output, so it can be used in a script, such as set RESULT [Bottlenecks create].