TrackScheme Branch and Hierarchy Windows Become Buggy After Removing Spots

[maarzt]

Problem Description

They problem can be reproduced like this:

1. Open a Mastodon project
2. Open the TrackScheme Branch window
3. Select any branch
4. Delete the branch by clicking SHIFT+delete
5. Select the branch again
6. 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.

[tinevez]

The incremental solution is very hard to build with mastodon data structures.
It was our initial attempt and we failed to make it work against 100% cases. This failure is the main reason why we have this design currently in mastodon.

But it is also really not great when it comes to performance, and has a measurable cost in responsiveness, even if the user plans not to use the branch graph.

I would be in favor with solutions like "it is the responsibility of the caller to ensure blablabla".
Now we must find a way not too clunky to have this in the UI. Maybe gracefully fail when we have invalid objects?