Adventures in Grouping and Binning

Oct 5, 2011 at 12:45 PM

I have an ASP.NET MVC application that needs to display a graph (with grouping). For some reason, grouping and binning in NodeXL is only available when doing asynchronous layouts (a fact well hidden in an implementation note inside the AsyncLayoutBase  source code).

No problem, I thought, I'll just call it like this:

				// Asynchronous layout, supports grouping and binning
				layout.LayoutStyle = LayoutStyle.UseGroups;
				using (var completedEvent = new ManualResetEventSlim())
				{
					
					layout.LayOutGraphCompleted +=
						(object sender, AsyncCompletedEventArgs e) =>
						{
							completedEvent.Set();
						};
					layout.LayOutGraphAsync(graph, layoutContext);
					completedEvent.Wait();
				}

While this works perfectly in Windows Forms and in WPF, it doesn't work in IIS or Cassini (Visual Studio 2010's ASP.NET developement server). The reason is AsyncLayoutBase's use of BackgroundWorker which doesn't trigger the completion event on the right thread (that aspect of the code in AsyncLayoutBase's is wrong).

Rather than changing the existing code to use the more correct ThreadPool.QueueUserWorkItem with a proper syncronization context and PostOrCallback instance for the callback, I tried to find out if grouping and binning could be done synchronously.  It turns out it's not that difficult: the only limitation is that you need to decide which layout to use first (you need to do this because most of the interesting things you need are protected, not public) and derive from it. In my case, I chose FruchtermanReingoldLayout. My derived type is defined as such:

			/// <summary>
			/// Implement a custom layout that can use grouping or binning synchronously.
			/// For accessibility reasons, the custom layout should derive from the actual layout you want to use.
			/// </summary>
			class CustomLayout : FruchtermanReingoldLayout
			{
				new public void LayOutGraph(IGraph graph, LayoutContext layoutContext)
				{
					if (m_eLayoutStyle == LayoutStyle.Normal)
					{
						base.LayOutGraph(graph, layoutContext);
						return;
					}

					AssertValid();

					GroupMetadataManager.OnLayoutBegin(graph);

					LayoutContext adjustedLayoutContext;
					if (!GetAdjustedLayoutContext(graph, layoutContext, out adjustedLayoutContext))
						return;

					// Honor the optional LayOutTheseVerticesOnly key on the graph.
					var verticesToLayOut = GetVerticesToLayOut(graph);
					var iVerticesToLayOut = verticesToLayOut.Count;
					if (iVerticesToLayOut == 0)
						return;

					// Groups and binning can be used only if the entire graph is being laid out.
					if (iVerticesToLayOut == graph.Vertices.Count)
					{
						if (m_eLayoutStyle == LayoutStyle.UseGroups && graph.ContainsKey(ReservedMetadataKeys.GroupInfo))
						{
							if (!LayOutGraphOnBackgroundWorkerUsingGroups(graph, adjustedLayoutContext))
								return; // cancelled
							verticesToLayOut = new IVertex[0];
						}
						else if ((m_eLayoutStyle == LayoutStyle.UseBinning) && SupportsBinning)
						{
							// Lay out the graph's smaller components in bins.
							var graphBinner = new GraphBinner();
							graphBinner.MaximumVerticesPerBin = m_iMaximumVerticesPerBin;
							graphBinner.BinLength = m_iBinLength;

							ICollection<IVertex> remainingVertices;
							Rectangle remainingRectangle;

							if (graphBinner.LayOutSmallerComponentsInBins(graph, verticesToLayOut, adjustedLayoutContext, out remainingVertices, out remainingRectangle))
							{
								// The remaining vertices need to be laid out in the remaining rectangle.
								verticesToLayOut = remainingVertices;
								adjustedLayoutContext = new LayoutContext(remainingRectangle);
							}
							else
								// There are no remaining vertices, or there is no space left.
								verticesToLayOut = new IVertex[0];
						}
					}

					if (verticesToLayOut.Count > 0)
					{
						// Let the derived class do the work.
						if (!LayOutGraphCore(graph, verticesToLayOut, adjustedLayoutContext, null))
							return;	// cancelled
					}

					LayoutMetadataUtil.MarkGraphAsLaidOut(graph);
				}


				/// <summary>
				/// This is just a grid layout whose LayoutGraphCore method has been made publically accessible
				/// </summary>
				private class MyGridLayout : GridLayout
				{
					new public bool LayOutGraphCore(IGraph graph, ICollection<IVertex> verticesToLayOut, LayoutContext layoutContext, BackgroundWorker backgroundWorker)
					{
						return base.LayOutGraphCore(graph, verticesToLayOut, layoutContext, backgroundWorker);
					}
				}


				protected Boolean LayOutGraphOnBackgroundWorkerUsingGroups(IGraph graph, LayoutContext adjustedLayoutContext)
				{
					Debug.Assert(graph != null);
					Debug.Assert(adjustedLayoutContext != null);

					Object groupInfoAsObject;

					if (!graph.TryGetValue(ReservedMetadataKeys.GroupInfo, typeof(GroupInfo[]), out groupInfoAsObject))
						return true;

					// There is one object in this List for each group of vertices that will be laid out in a rectangle.
					var groupsToLayOut = GetGroupsToLayOut(graph, (GroupInfo[])groupInfoAsObject);

					// Calculate a rectangle for each group.
					GroupRectangleCalculator.CalculateGroupRectangles(adjustedLayoutContext.GraphRectangle, groupsToLayOut);

					foreach (var groupInfo in groupsToLayOut)
					{
						var groupRectangle = groupInfo.Rectangle;
						groupRectangle.Inflate(-m_iMargin, -m_iMargin);

						// Do not use Rectangle.IsEmpty() here.  It returns true only if
						// the rectangle is at the origin and has zero width and height.

						if (groupRectangle.Width > 0 && groupRectangle.Height > 0)
						{
							var verticesInGroup = groupInfo.Vertices;
							Debug.Assert(verticesInGroup != null);
							Debug.Assert(verticesInGroup.Count > 0);
							bool result;
							if (m_bImproveLayoutOfGroups && SubgraphCalculator.GetSubgraphAsNewGraph(verticesInGroup).Edges.Count <= MaximumGroupEdgeCountToGrid)
							{
								// Create a new graph from the vertices in the group and the edges that connect them.
								// The graph is sparse.  Use a grid layout, and sort the vertices by layout order.
								MyGridLayout oGridLayout = new MyGridLayout();
								oGridLayout.UseMetadataVertexSorter(graph);
								result = oGridLayout.LayOutGraphCore(graph, verticesInGroup, new LayoutContext(groupRectangle), null);
							}
							else
								// Use the layout implemented by the derived class.
								result = LayOutGraphCore(graph, verticesInGroup, new LayoutContext(groupRectangle), null);
							if (!result)
								return false; // cancelled
						}
						else
						{
							groupRectangle = groupInfo.Rectangle;
							PointF vertexLocation;

							if (groupRectangle.Width > 0 && groupRectangle.Height > 0)
								// Put the group's vertices at the rectangle's center.
								vertexLocation = new PointF(groupRectangle.Left + groupRectangle.Width / 2, groupRectangle.Top + groupRectangle.Height / 2);
							else
								// Put the group's vertices at the rectangle's upper-left corner.
								vertexLocation = new PointF(groupRectangle.X, groupRectangle.Y);

							foreach (var vertex in groupInfo.Vertices)
								vertex.Location = vertexLocation;
						}
					}

					// Perform metadata-related tasks.
					GroupMetadataManager.OnLayoutUsingGroupsEnd(graph, groupsToLayOut, GroupRectanglePenWidth, IntergroupEdgeStyle);
					return true;
				}
			}

Calling LayOutGraph on CustomLayout will do the right thing when the layout style specifies grouping or binning. As you can see, I didn't re-invent the wheel: the code is almost identical to the one used in asynchronous layout.

The ideal solution would be to provide grouping and binning synchronously within NodeXL. Also, the asynchronous implementation should avoid BackgroundWorker.

Finally (this has nothing to do with the above adventure), while experimenting with different layouts, I found that the Sugiyama rendering (which is delegated to MSAGL) doesn't take the Bezier paths for the edges into account. That's too bad, it looked so cool.

So now you know.