FindRoots called multiple times in Virtual Tree


I have a tree diagram that was having performance issues and I am trying to convert it over to a virtual tree. I am using the Virtualization sample as a guide. I have built the sample code and it works just fine for me. However, I am having a problem with my application. For starters, the FindRoots() method in the VirtualizingTreeLayout class is called more than once and it’s causing a problem.

Here is the code from the sample for FindRoots():

// need to find root Node(s); which in this case means creating the actual Nodes,
// since they would otherwise not exist
protected override void FindRoots()
foreach (VirtualizingTreeVertex v in this.Network.Vertexes)
if ((this.Path == TreePath.Destination && v.SourceEdgesCount == 0) ||
(this.Path == TreePath.Source && v.DestinationEdgesCount == 0))
var node = this.Diagram.PartManager.AddNodeForData(v.Data, _Model);
if (node == null) throw new Exception("Root node data doesn’t have Location at (0,0): " + v.Data.ToString());
((VirtualizingTreeNetwork)this.Network).SetNode(v, node);
if (this.Roots.Count == 0) throw new Exception(“Found no root node for tree”);

The first time FindRoots() is called the node variable is returned from AddNodeForData(), but in the subsequent time it is null and the exception is thrown.

My call stack looks like this for the 2nd call to FindRoots():
<span =“Apple-tab-span” style="white-space: pre; "> WindchillQualitySolutions.Web.Silverlight!MyApp.Web.MyTree.VirtualizingTreeLayout.FindRoots() Line 129<span =“Apple-tab-span” style="white-space: pre; "> C#

<span =“Apple-tab-span” style=“white-space:pre”> Northwoods.GoSilverlight!Northwoods.GoXam.Layout.TreeLayout.CreateTrees() + 0x413 bytes<span =“Apple-tab-span” style=“white-space:pre”>
<span =“Apple-tab-span” style=“white-space:pre”> Northwoods.GoSilverlight!Northwoods.GoXam.Layout.TreeLayout.DoLayout(System.Collections.Generic.IEnumerable<Northwoods.GoXam.Node> nodes = {System.Linq.Enumerable.WhereEnumerableIterator<Northwoods.GoXam.Node>}, System.Collections.Generic.IEnumerable<Northwoods.GoXam.Link> links = {System.Linq.Enumerable.WhereEnumerableIterator<Northwoods.GoXam.Link>}) + 0x46a bytes<span =“Apple-tab-span” style=“white-space:pre”>
<span =“Apple-tab-span” style=“white-space:pre”> WindchillQualitySolutions.Web.Silverlight!MyApp.Web.MyTree.FTDiagramTreeLayout.DoLayout(System.Collections.Generic.IEnumerable<Northwoods.GoXam.Node> nodes = {System.Linq.Enumerable.WhereEnumerableIterator<Northwoods.GoXam.Node>}, System.Collections.Generic.IEnumerable<Northwoods.GoXam.Link> links = {System.Linq.Enumerable.WhereEnumerableIterator<Northwoods.GoXam.Link>}) Line 37 + 0x13 bytes<span =“Apple-tab-span” style=“white-space:pre”> C#
<span =“Apple-tab-span” style=“white-space:pre”> Northwoods.GoSilverlight!Northwoods.GoXam.Layout.MultiLayout.DoLayout(System.Collections.Generic.IEnumerable<Northwoods.GoXam.Node> nodes = {System.Linq.Enumerable.WhereEnumerableIterator<Northwoods.GoXam.Node>}, System.Collections.Generic.IEnumerable<Northwoods.GoXam.Link> links = {System.Linq.Enumerable.WhereEnumerableIterator<Northwoods.GoXam.Link>}) + 0x593 bytes<span =“Apple-tab-span” style=“white-space:pre”>
<span =“Apple-tab-span” style=“white-space:pre”> Northwoods.GoSilverlight!Northwoods.GoXam.LayoutManager.PerformLayout() + 0x496 bytes<span =“Apple-tab-span” style=“white-space:pre”>
><span =“Apple-tab-span” style=“white-space:pre”> Northwoods.GoSilverlight!Northwoods.GoXam.LayoutManager.#Xf() + 0x220 bytes<span =“Apple-tab-span” style=“white-space:pre”>
<span =“Apple-tab-span” style=“white-space:pre”> [Native to Managed Transition]<span =“Apple-tab-span” style=“white-space:pre”>
<span =“Apple-tab-span” style=“white-space:pre”> [Managed to Native Transition]<span =“Apple-tab-span” style=“white-space:pre”>
<span =“Apple-tab-span” style=“white-space:pre”> mscorlib.dll!System.Delegate.DynamicInvokeImpl(object[] args) + 0x6b bytes<span =“Apple-tab-span” style=“white-space:pre”>
<span =“Apple-tab-span” style=“white-space:pre”> System.Windows.dll!System.Windows.Threading.DispatcherOperation.Invoke() + 0x26 bytes<span =“Apple-tab-span” style=“white-space:pre”>
<span =“Apple-tab-span” style=“white-space:pre”> System.Windows.dll!System.Windows.Threading.Dispatcher.Dispatch(System.Windows.Threading.DispatcherPriority priority) + 0xd5 bytes<span =“Apple-tab-span” style=“white-space:pre”>
<span =“Apple-tab-span” style=“white-space:pre”> System.Windows.dll!System.Windows.Threading.Dispatcher.OnInvoke(object context) + 0xa bytes<span =“Apple-tab-span” style=“white-space:pre”>
<span =“Apple-tab-span” style=“white-space:pre”> System.Windows.dll!System.Windows.Hosting.CallbackCookie.Invoke(object[] args) + 0x16 bytes<span =“Apple-tab-span” style=“white-space:pre”>
<span =“Apple-tab-span” style=“white-space:pre”> System.Windows.RuntimeHost.dll!System.Windows.RuntimeHost.ManagedHost.InvokeDelegate(System.IntPtr pHandle, int nParamCount, System.Windows.Hosting.NativeMethods.ScriptParam[] pParams, ref System.Windows.Hosting.NativeMethods.ScriptParam pResult = {System.Windows.Hosting.NativeMethods.ScriptParam}) + 0xe9 bytes<span =“Apple-tab-span” style=“white-space:pre”>
<span =“Apple-tab-span” style=“white-space:pre”> [Appdomain Transition]<span =“Apple-tab-span” style=“white-space:pre”>

A few notes:

  1. If I have a small tree (3 or 4 nodes) then this problem doesn’t happen. It only happens when I have a large tree where some of the nodes are offscreen.

  2. If I save the node in the 1st call and return it in the 2nd call then later on I get errors when TreeLayout::LayoutTree() is called with a null TreeVertex.

So my questions are:

  1. What is causing this? I have a single root of my tree and it isn’t changing. Why does the Roots get cleared and need to be regenerated anyway?

  2. How can I tell what is triggering the layout?

  3. This might be a symptom of a larger problem. It’s very likely I have set up something else wrong. I can post any other code that you think might be useful.



I’d guess it has something to do with the creation of the TreeNetwork. It might be more complicated because apparently you are using a MultiLayout, so there are multiple layouts involved. Is your app a situation where you want the same Node/Vertex to act as the root for multiple layouts? This is like what happens in the DoubleTree sample, but the Virtualizing sample of course assumes there’s just one layout and thus one network.

Yes, I am using a Multi-layout. However, I am not using the node/vertex as the root for more than one layout. I am using a TreeLayout (which I am working on making virtual) to layout a tree and a DiagramLayout to layout labels that go around the tree.

I don’t know how much of VirtualizingTreeLayout you have changed, but you’ll note that the use of VirtualizingTreeLayout in the Virtualizing sample calls DoLayout(null, null). That’s because the VirtualizingTreeLayout cannot take any Nodes and Links if they do not yet exist. Hence why there’s an alternate way to pass the “graph” in – via VirtualizingTreeLayout.SetData – as raw data that the MakeNetwork override can use to create the TreeNetwork that is laid out by the TreeLayout.

Yet in the stack trace it appears that DoLayout is being called with some actual Nodes and Links. So I think the problem is that because of the MultiLayout, your VirtualizingTreeLayout.SetData method is not being called, and the tree layout is trying to operate with the given collections of Nodes and Links – not what you want.

I am calling SetData() with a list of data and links followed by calling DoLayout(null, null). Something else is triggering the second call to DoLayout and I’m not sure what. During the first call the node root is found and added to the roots collection. During the second call the roots collection is empty again.

TreeLayout automatically resets the Roots property to be an empty collection after each layout. This way there cannot accidentally be any invalid nodes as a root.

I’m not sure why the tree layout is being called more than once. It could be because of the DiagramLayout.Conditions you have set. How is the other layout in the MultiLayout declared? And for that matter, how is the VirtualizingTreeLayout declared?

The layout is defined in the XAML like this:

<span =“Apple-tab-span” style=“white-space: pre; “> go:Diagram.Layout
Sorting=“Ascending” Angle=“90”
Conditions=“Standard VisibleChanged”
Comparer=”{StaticResource FigureComparer}”
Alignment="{Binding Path=TreeDiagramAlignment}"
PortSpot="{Binding Path=InputFigureAlignment}"/>
<golayout:DiagramLayout Id=“Label”
Conditions=“NodeAdded NodeRemoved DiagramLayoutChanged VisibleChanged”/>

The VirtualizingTreeLayout class is exactly that from the sample. It creates a VirtualizingTreeNetwork and populates it with objects of type VirtualizingTreeVertex & VirtualizingTreeEdge.

At the moment I don’t have any labels. I only have figures in the tree.

If you take out the MultiLayout and the “Label” DiagramLayout, leaving just the VirtualizingTreeLayout, does it still get called twice?

Yes, it’s still called twice if I only have the VirtualizingTreeLayout.

The original Virtualizing sample constructs the VirtualizingTreeLayout programmatically and calls SetData and DoLayout explicitly.

But you have declared it in XAML as the value for Diagram.Layout.

Are you doing both? That would explain why it’s being called twice.

And if you are only defining Diagram.Layout, how are you making sure that SetData is called?

I am constructing the layout in the XAML and then referencing it programmatically like this from within the diagram class:

<span =“Apple-tab-span” style=“white-space:pre”> // Construct list of Figures & FigureLinks (snipped)

<span =“Apple-tab-span” style=“white-space:pre”> // Layout the Tree
<span =“Apple-tab-span” style=“white-space:pre”> var layoutTree = (VirtualizingTreeLayout)this.Layout;
<span =“Apple-tab-span” style=“white-space:pre”> layoutTree.SetData(Figures, FigureLinks, DiagramModel);
<span =“Apple-tab-span” style=“white-space:pre”> layoutTree.DoLayout(null, null);

If I only have a small number of figures then it’s only being called once. If I have many figures then it is called twice.

That would explain why it’s being called twice. Because of the virtualization, as Nodes and Links are being added due to scrolling or zooming, it causes the layout to be invalidated and then performed again. (The “Standard” invalidation conditions include adding or removing nodes or links.) Change the DiagramLayout.Conditions to be “None”, and explicitly call SetData and DoLayout, as you are already, whenever you want to perform a layout.

That fixed it. Thanks!

Now I’m working on inserting a new figure into the tree. Here are the steps I am following:

  1. Add the new figure to the Figures collection
  2. Add the new link to the FigureLinks collection
  3. Call SetData(Figures, FigureLinks, DiagramModel) & DoLayout(null, null) on the layout

The new figure appears in the diagram, but it is not in the correct location. What other steps do I need to follow to get the new figure to appear in the correct location when I add it?

If I close the app and restart it then everything is drawn just fine, so clearly I’m just missing a step.

I would first check whether VirtualizingTreeVertex.CommitPosition is setting the new node data’s Location property to the value that you want.

Actually, I can update the Virtualizing sample so that it can handle updates to the tree structure. Please give me some time to work on this.

Sure. Thanks!

An updated Virtualizing sample is now available, to address what I think your needs are.

I hope you can adapt it easily for your own application.

Thanks! I’ll take a look.