TrackScheme Branch and Hierarchy Windows Become Buggy After Removing Spots

Problem Description

They problem can be reproduced like this:

Open a Mastodon project
Open the TrackScheme Branch window
Select any branch
Delete the branch by clicking SHIFT+delete
Select the branch again
The branch won't get selected, but a exception gets printed:

Exception in thread "AWT-EventQueue-0" java.lang.IndexOutOfBoundsException: bitIndex < 0: -1
    at java.util.BitSet.get(BitSet.java:623)
    at org.mastodon.model.DefaultSelectionModel.isSelected(DefaultSelectionModel.java:124)
    at org.mastodon.model.DefaultSelectionModel.setSelected(DefaultSelectionModel.java:157)
    at org.mastodon.model.branch.BranchGraphSelectionAdapter.setVertexSelected(BranchGraphSelectionAdapter.java:142)
    at org.mastodon.model.branch.BranchGraphSelectionAdapter.setSelected(BranchGraphSelectionAdapter.java:127)
    at org.mastodon.adapter.SelectionModelAdapter.setSelected(SelectionModelAdapter.java:91)
    at org.mastodon.views.trackscheme.display.TrackSchemeNavigationBehaviours.select(TrackSchemeNavigationBehaviours.java:252)
    at org.mastodon.views.trackscheme.display.TrackSchemeNavigationBehaviours.access$1100(TrackSchemeNavigationBehaviours.java:63)
    at org.mastodon.views.trackscheme.display.TrackSchemeNavigationBehaviours$ClickSelectionBehaviour.click(TrackSchemeNavigationBehaviours.java:393)
    at org.scijava.ui.behaviour.MouseAndKeyHandler.mouseClicked(MouseAndKeyHandler.java:265)
    at java.awt.AWTEventMulticaster.mouseClicked(AWTEventMulticaster.java:270)
    at java.awt.Component.processMouseEvent(Component.java:6542)
    at javax.swing.JComponent.processMouseEvent(JComponent.java:3324)
    at java.awt.Component.processEvent(Component.java:6304)
    at java.awt.Container.processEvent(Container.java:2239)
    at java.awt.Component.dispatchEventImpl(Component.java:4889)
    at java.awt.Container.dispatchEventImpl(Container.java:2297)
    at java.awt.Component.dispatchEvent(Component.java:4711)
    at java.awt.LightweightDispatcher.retargetMouseEvent(Container.java:4904)
    at java.awt.LightweightDispatcher.processMouseEvent(Container.java:4544)
    at java.awt.LightweightDispatcher.dispatchEvent(Container.java:4476)
    at java.awt.Container.dispatchEventImpl(Container.java:2283)
    at java.awt.Window.dispatchEventImpl(Window.java:2746)
    at java.awt.Component.dispatchEvent(Component.java:4711)
    at java.awt.EventQueue.dispatchEventImpl(EventQueue.java:760)
    at java.awt.EventQueue.access$500(EventQueue.java:97)
    at java.awt.EventQueue$3.run(EventQueue.java:709)
    at java.awt.EventQueue$3.run(EventQueue.java:703)
    at java.security.AccessController.doPrivileged(Native Method)
    at java.security.ProtectionDomain$JavaSecurityAccessImpl.doIntersectionPrivilege(ProtectionDomain.java:74)
    at java.security.ProtectionDomain$JavaSecurityAccessImpl.doIntersectionPrivilege(ProtectionDomain.java:84)
    at java.awt.EventQueue$4.run(EventQueue.java:733)
    at java.awt.EventQueue$4.run(EventQueue.java:731)
    at java.security.AccessController.doPrivileged(Native Method)
    at java.security.ProtectionDomain$JavaSecurityAccessImpl.doIntersectionPrivilege(ProtectionDomain.java:74)
    at java.awt.EventQueue.dispatchEvent(EventQueue.java:730)
    at java.awt.EventDispatchThread.pumpOneEventForFilters(EventDispatchThread.java:205)
    at java.awt.EventDispatchThread.pumpEventsForFilter(EventDispatchThread.java:116)
    at java.awt.EventDispatchThread.pumpEventsForHierarchy(EventDispatchThread.java:105)
    at java.awt.EventDispatchThread.pumpEvents(EventDispatchThread.java:101)
    at java.awt.EventDispatchThread.pumpEvents(EventDispatchThread.java:93)
    at java.awt.EventDispatchThread.run(EventDispatchThread.java:82)

Workaround

Update the branch graph after deleting spots or links: Click the "Regen. branch-graph" button.

Insights from investigating the problem

The ModelBranchGraph gets outdated when making changes to the ModelGraph. After deleting spots the ModelBranchGraph methods getFirstLinkedVertex, getLastLinkedVertex and getLinkedEdge will return references to no longer existing spots and links. The VertexBranchIterator and EdgeBranchIterator return wrong spot and edge references and might not terminate.

The exception listed above is triggered because the EdgeBranchIteration returns wrong link references.

Ideas how to fix this issue

Regenerate the branch graph whenever a spot or link is delete. (This will have horrible performance)
Delete branch spots that get outdated because related spots & edges are deleted.
Have an incremental branch graph that updates incrementally when changes are made to the ModelGraph. (Kind of hard to implement.)

Here is an example that demonstrates how the branchGraph.edgeBranchIterator(...) gives wrong results after deleting a spot in the ModelGraph:

package org.mastodon;

import static org.junit.Assert.assertEquals;

import java.util.Iterator;

import org.junit.Test;
import org.mastodon.mamut.model.Link;
import org.mastodon.mamut.model.Model;
import org.mastodon.mamut.model.ModelGraph;
import org.mastodon.mamut.model.Spot;
import org.mastodon.mamut.model.branch.BranchSpot;
import org.mastodon.mamut.model.branch.ModelBranchGraph;

public class BranchGraphProblem
{

    @Test
    public void test() {
        // create simple example graph
        final Model model = new Model();
        final ModelGraph graph = model.getGraph();
        final Spot a = graph.addVertex().init( 0, new double[] { 1, 2, 3 }, 1 );
        final Spot b = graph.addVertex().init( 1, new double[] { 1, 2, 3 }, 1 );
        final Spot c = graph.addVertex().init( 2, new double[] { 1, 2, 3 }, 1 );
        graph.addEdge( a, b ).init();
        graph.addEdge( b, c ).init();

        // rebuilt branch graph
        ModelBranchGraph branchGraph = model.getBranchGraph();
        branchGraph.graphRebuilt();

        // remove spot
        graph.remove( c );
        final Spot d = graph.addVertex().init( 2, new double[] { 1, 2, 3 }, 1 );

        // test
        BranchSpot bvA = branchGraph.getBranchVertex( a, branchGraph.vertexRef() );
        Spot bvA_end = branchGraph.getLastLinkedVertex( bvA, graph.vertexRef() ); // BUG: returns a spot that is no longer part of the graph
        System.out.println( bvA_end );
        assertEquals( d, bvA_end );
        Iterator< Link > edges = branchGraph.edgeBranchIterator( bvA );
        System.out.println( "link pool index: " + edges.next().getInternalPoolIndex() );
        System.out.println( "link pool index: " + edges.next().getInternalPoolIndex() ); // BUG: returns -1, this edge does not exist
    }

}

TODOs

[ ] Ask Jean-Yves about his opinion on this problem. Is he in favor of having an incremental branch graph?

Acceptance Criteria

Deleting spots no longer causes exceptions to be triggered, when using the TrackScheme Branch.
TrackScheme Branch remains functions / works as expected after deleting spots in the ModelGraph.

mastodon-sc / mastodon