ConvexBranchesDecomposition (Fiji Javadocs 0-SNAPSHOT API)

java.lang.Object
- fiji.plugin.trackmate.graph.ConvexBranchesDecomposition

All Implemented Interfaces:

Algorithm, Benchmark
```
public class ConvexBranchesDecomposition
extends Object
implements Algorithm, Benchmark
```
A class that can decompose the tracks of a Model in convex branches.
A convex branch is a portion of a track for which all spots - but the first and last one - have exactly one predecessor and one successor (in time). The first and last spots of a branch may have 0 or 1 or more predecessors or successors respectively, depending on they are the start or the end of a track, or a fusion or merging point, or a gap (see below).
Schematically, if a track is arranged as follow:
```
 A
 |
 B--+
 |  |
 C  I
 |  |
 D  J
 |  |
 E  K
 |  |
 F  L
 |  |
 G--+
 |
 H
 
```
then
```
 A - B,
 C - D - E - F,
 I - J - K - L,
 G - H
 
```
are convex branches. This class generates the decomposition of a track in these branches.
In the example above, note that another acceptable decomposition could be:
```
 A,
 B - C - D - E - F - G,
 I - J - K - L,
 H
 
```
depending on to what branch you choose to attach splitting or merging points. This class attaches split points to the end of the early branch, and merge points to the beginning of the late branch. So that for our example above, the output is indeed:
```
 A - B,
 C - D - E - F,
 I - J - K - L,
 G - H
 
```
The behavior of this algorithm can be tuned using two boolean flags. The first one specifies whether we can violate the convex branch contract and have branches that contain a spot with more than one predecessor and one successor. For instance, if a track is as follow:
```
 A
 |
 B
 |
 C--+
 |  |
 D  F
 |  |
 E  G
 
```
the default output would be:
```
 A - B - C,
 D - E,
 F - G
 
```
Setting the forbidMiddleLinks flag to false would give instead:
```
 A - B - C - D - E,
 F - G
 
```
which yields fewer and longer branches.
Some branches may have gaps in them, that is two spots separated by more than one frame. By default this does not lead to cutting the branch in two. If you want to force branches to contain spots that are separated by exactly only one frame, set the forbidGaps flag to true. In that case, a track arranged as following (ø is a missing detection in a frame, or a gap):
```
 A - B - C - ø - D - E - F
 
```
will be split in two branches.
```
 A - B - C,
 D - E - F
 
```
It is ensured that each spot in the model is present in exactly one branch of the decomposition. Only spots belonging to visible tracks are taken into account. This class also outputs the links that were cut in the source model to generate these branches.
Author:

Jean-Yves Tinevez - 2014

Nested Class Summary

Nested Classes
Modifier and Type	Class and Description
`static class`	`ConvexBranchesDecomposition.TrackBranchDecomposition` A two public fields class used to return the convex branch decomposition of a track.

Constructor Summary

Constructors
Constructor and Description
`ConvexBranchesDecomposition(Model model)` Creates a new track splitter.
`ConvexBranchesDecomposition(Model model, boolean forbidMiddleLinks, boolean forbidGaps)` Creates a new track splitter.

Method Summary

All Methods Static Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`static org.jgrapht.graph.SimpleDirectedGraph<List<Spot>,org.jgrapht.graph.DefaultEdge>`	`buildBranchGraph(ConvexBranchesDecomposition.TrackBranchDecomposition branchDecomposition)` Builds a directed graph made of a convex branch decomposition.
`boolean`	`checkInput()`
`Collection<List<Spot>>`	`getBranches()` Returns the collection of branches built by this algorithm.
`Map<Integer,Collection<List<Spot>>>`	`getBranchesPerTrack()` Returns the mapping of each source track ID to the branches it was split in.
`String`	`getErrorMessage()`
`Collection<List<Spot>>`	`getLinks()` Returns the links cut by this algorithm when splitting the model in linear, convex branches.
`Map<Integer,Collection<List<Spot>>>`	`getLinksPerTrack()` Returns the mapping of each source track ID to the links that were cut in it to split it in branches.
`long`	`getProcessingTime()`
`boolean`	`process()`
`static ConvexBranchesDecomposition.TrackBranchDecomposition`	`processTrack(Integer trackID, TrackModel tm, TimeDirectedNeighborIndex neighborIndex, boolean forbidMiddleLinks, boolean forbidGaps)` A static utility that generates the convex branch decomposition of a specific track in a model.

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Constructor Detail
  - ConvexBranchesDecomposition
```
public ConvexBranchesDecomposition(Model model,
                                   boolean forbidMiddleLinks,
                                   boolean forbidGaps)
```
    Creates a new track splitter.
    
    Parameters:
    
    model - the Model from which tracks are to be split. Only tracks marked visible will be processed.
    
    forbidMiddleLinks - specifies whether we enforce links between branches to be between an end point of a branch and a start point of another branch. If true, links will only reach for these spots. If false, a link can target a spot within a branch, which can lead to fewer and longer branches.
    
    forbidGaps - specifies whether we forbid gaps in tracks. If true, a track containing a gap (detections missing in at least 1 consecutive frames) will be split in 2 branches. If false, branches may contain gaps.
  - ConvexBranchesDecomposition
```
public ConvexBranchesDecomposition(Model model)
```
    Creates a new track splitter. Links between spots from within branches and gaps within convex branches are forbidden.
    
    Parameters:
    
    model - the Model from which tracks are to be split. Only tracks marked visible will be processed.
- Method Detail
  - getProcessingTime
```
public long getProcessingTime()
```
    Specified by:
    
    getProcessingTime in interface Benchmark
  - checkInput
```
public boolean checkInput()
```
    Specified by:
    
    checkInput in interface Algorithm
  - process
```
public boolean process()
```
    Specified by:
    
    process in interface Algorithm
  - processTrack
```
public static final ConvexBranchesDecomposition.TrackBranchDecomposition processTrack(Integer trackID,
                                                                                      TrackModel tm,
                                                                                      TimeDirectedNeighborIndex neighborIndex,
                                                                                      boolean forbidMiddleLinks,
                                                                                      boolean forbidGaps)
```
    A static utility that generates the convex branch decomposition of a specific track in a model.
    
    Parameters:
    
    trackID - the ID of the track to decompose.
    
    tm - the TrackModel in which the track is stored.
    
    neighborIndex - a TimeDirectedNeighborIndex needed to quickly retrieve neighbors in the mother graph.
    
    forbidMiddleLinks - if true, the decomposition will include branches where only the first and last spots may have more than one predecessor and one successor respectively. If false, some spots inside a branch may be a fusion or splitting point. This leads to fewer and longer branches.
    
    forbidGaps - if true, two neighbor spots in a branch will be separated by exactly one frame. If false, branches will include gaps.
    
    Returns:
    
    a new ConvexBranchesDecomposition.TrackBranchDecomposition.
    
    See Also:
    
    ConvexBranchesDecomposition
  - buildBranchGraph
```
public static final org.jgrapht.graph.SimpleDirectedGraph<List<Spot>,org.jgrapht.graph.DefaultEdge> buildBranchGraph(ConvexBranchesDecomposition.TrackBranchDecomposition branchDecomposition)
```
    Builds a directed graph made of a convex branch decomposition.
    In the graph, the vertices are made of the branches of the decomposition, and the edges are the links between each branch.
    
    Parameters:
    
    branchDecomposition - the convex branch decomposition to transform.
    
    Returns:
    
    a new simple directed graph. The direction of the edges in the graph are taken as the end of a branch is the source, and the beginning of a branch as the target, following time.
  - getErrorMessage
```
public String getErrorMessage()
```
    Specified by:
    
    getErrorMessage in interface Algorithm
  - getBranches
```
public Collection<List<Spot>> getBranches()
```
    Returns the collection of branches built by this algorithm.
    Branches are returned as list of spot. It is ensured that the spots are ordered in the list by increasing frame number, and that two consecutive spot are separated by exactly one frame.
    
    Returns:
    
    the collection of branches.
  - getBranchesPerTrack
```
public Map<Integer,Collection<List<Spot>>> getBranchesPerTrack()
```
    Returns the mapping of each source track ID to the branches it was split in.
    Branches are returned as list of spot. It is ensured that the spots are ordered in the list by increasing frame number, and that two consecutive spot are separated by exactly one frame.
    
    Returns:
    
    a mapping of collections of branches.
  - getLinks
```
public Collection<List<Spot>> getLinks()
```
    Returns the links cut by this algorithm when splitting the model in linear, convex branches.
    These links are returned as a collection of 2-elements list. If the instance was created with forbidMiddleLinks sets to true, it is ensured that the first element of all links is the last spot of a branch, and the second element of this link is the first spot of another branch. Otherwise, a link can target a spot within a branch.
    
    Returns:
    
    a collection of links as a 2-elements list.
  - getLinksPerTrack
```
public Map<Integer,Collection<List<Spot>>> getLinksPerTrack()
```
    Returns the mapping of each source track ID to the links that were cut in it to split it in branches.
    These links are returned as a collection of 2-elements list. If the instance was created with forbidMiddleLinks sets to true, it is ensured that the first element of all links is the last spot of a branch, and the second element of this link is the first spot of another branch. Otherwise, a link can target a spot within a branch.
    
    Returns:
    
    the mapping of track IDs to the links.

Class ConvexBranchesDecomposition

Nested Class Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Constructor Detail

ConvexBranchesDecomposition

ConvexBranchesDecomposition

Method Detail

getProcessingTime

checkInput

process

processTrack

buildBranchGraph

getErrorMessage

getBranches

getBranchesPerTrack

getLinks

getLinksPerTrack