Introduction
This article includes two very different basic assemblies and a couple of test assemblies for WPF. The first basic assembly is GraphLayout which implements the Reingold-Tilford algorithm, described here, to determine the placement of nodes in a tree structure. This tree is structured as a top down tree with the root at the top and the leaves at the bottom. This algorithm is entirely independent of any actual drawing of those nodes and so can be used for any purpose where such positioning is required. It includes options for vertical justification for nodes, collapsing of nodes, distance between sibling nodes and distance between non-sibling nodes. This assembly is not WPF specific and could easily be used to produce a GDI+ tree drawer (though I haven't included any here). It also includes a list of endpoints for lines which can be drawn as connectors between nodes. Currently, these lines are simply straight lines from the bottom center of the parent node to the top center of the child node, though it would be easy enough to modify them to draw different kinds of connectors.
The second assembly is a WPF control subclassed from Panel which uses GraphLayout to determine where to place its child controls in a tree. Each non-root node has a dependency property for its parent node's name which is how the graph is strung together. Since this is a subclassed panel, the individual nodes can be any type of WPF control desired. This allows the tree to be specified in XAML as demonstrated in the TreeContainerTest test app or in code as demonstrated in the VisLogTree.
It also contains a Silverlight control which does the same thing. The primary difference with the Silverlight control is that the connections have to be added as a Path child to the tree container rather than painting the connections directly onto the control. Silverlight doesn't support the OnRender function for controls where they can be drawn to. I prefer the drawing method used in the WPF control so that there's not this "dangling" path control, but it really doesn't seem to be an option in Silverlight. I just got started with Silverlight a couple of days ago so if anybody knows better, I'd love to hear about it. The GraphLayout DLL had to be recompiled so it would be linked with the Silverlight libraries but otherwise was used unchanged. After figuring out all the little Silverlight quirks, the new Silverlight control worked the first time I tried it testifying to some extent to the universality of GraphLayout.
Background
There are several WPF controls which I could locate which make some effort to produce trees in WPF but so far as I can find, there are no free assemblies/source code which give a proper implementation of the Reingold-Tilford algorithm in a standard WPF fashion (i.e., a subclassed panel which can be implemented in XAML) and it seems like an obvious and valuable thing to do, so I've done it. There are LOTS of extensions which I can think of making here, but this seems pretty valuable as it is so I'm putting it out there and moving on to other things for the moment.
The Reingold-Tilford algorithm can easiest be described as "recursively drawing all child graphs then jamming them all to the left as far as you can, leaving a fixed distance between nodes and finally cleaning up interior nodes which are jammed to the left but can be moved to the right for centering purposes". I know that's not incredibly intuitive - especially the last part - but reading the article cited above gives all the details (albeit not in a terribly clear manner in my estimation, nor in a way that corresponds very directly to my code which I implemented before reading this article and with not much more than the sketchy description given here - carefully slogging through the walkthrough is the only way I really understood it, even when I knew the basics of the algorithm).
I tried to test all the cases, but I might have missed a few - there are lots of trees out there, so please mail me if you find any bugs. For the most part, if I found inconsistencies with the Parenting within the WPF control, I just didn't position the corresponding controls at all so they end up in the upper left of the TreeContainer control. This is so XAML isn't constantly blowing up and showing you nothing because of a thrown exception. If you see nodes in the upper left of your TreeContainer control, go in and check for consistency in your Parent properties.
Using GraphLayout
GraphLayout (which probably should more properly be called TreeLayout although in the future I may add other Graph type layouts to it) provides an ITreeNode interface which represents (you guessed it) the nodes in the tree. GraphLayout.LayeredTreeDraw is the class which calculates all node positions. Its constructor takes an ITreeNode which represents the root of the tree and some global parameters which affect the positioning (minimum distance between nodes, vertical justification, etc.) and sets properties on all the nodes giving their proper positions in the final graphical tree.The ITreeNode interface is fairly simple. It includes TreeWidth and TreeHeight properties which return the width and height of the node. It also includes the boolean Collapsed property which is a readonly property telling whether the node should be collapsed. How this information is kept and set on the node is up to the implementation. The most important property is TreeChildren which returns the children of this node in a TreeNodeGroup collection. TreeNodeGroup is a simple enough class with an Add function to add ITreeNode objects to its collection. Finally, LayeredTreeDraw needs a place to poke its own private information into each node. You must implement PrivateNodeInfo which takes an object, stores it into the node and retrieves it back later.
There are three buffer distances associated with trees. The vertical buffer distance is the minimum distance between the layered rows of the tree. The horizontal buffer distance is the minimal distance between sibling nodes in the graph. The horizontal subtree distance is the minimal distance between nodes which are not direct siblings. This makes some graphs look better by further separating subtrees further than individual siblings.
After constructing the LayeredTreeDraw object, you simply call LayoutTree() on it and then retrieve the information back from it. The X and Y coordinates for a given node are retrieved from a LayeredTreeDraw object called ltd with ltd.X(treeNode) and ltd.Y(treeNode) where "treeNode" is the ITreeNode in question. ltd.PxOverallWidth() and ltd.PxOverallHeight() return the width and height of the resultant tree. ltd.Connections() returns a list of TreeConnection objects. Each object has a parent ITreeNode and a child ITreeNode along with a list of DPoints which give a path of lines from the parent to the child. Since WPF and GDI+ use different definitions for "Point" I decided to implement a very lightweight DPoint structure which always uses doubles for the coordinates and can be used from either WPF or GDI+ (or anywhere else for that matter). Currently, these connectors give a single line between the parent and the child but this wouldn't be hard to change. Really, I was going to provide a set of different types of connectors, but maybe that will be something for the future. As it is, it is possible with different sized vertical nodes that a connector from a short node could overlap with a taller sibling node. One of the things I thought about doing was giving broken lines which would avoid this possibility.
That is pretty much it for GraphLayout. It's simple enough to use but definitely the most complicated part under the covers.
Using TreeContainer
TreeContainer is a WPF control subclassed from Panel which uses GraphLayout to layout its children. To be used properly, we have to know the tree structure of the children. This is handled by having a dependency property called "Root" which is set on the TreeContainer and has the string value of the name of the node which is the root of the tree. The children of the TreeContainer must all be TreeNodes which are content controls which may hold whatever controls you like. The TreeNodes have a TreeParent property which tells which node is their parent in the tree - again, a string value with the name of the parent node. Every TreeNode in the TreeContainer must have a parent property except the root node. There is also a Collapsible and Collapsed property on each TreeNode. If the Collapsible property is set to false for a node, it cannot be collapsed. It it is true, then the value of Collapsed determines whether a node is collapsed or not. In the VisLogTree sample, the nodes are buttons which toggle the collapse of the tree below them when pressed. These properties are all XAML settable.
TreeContainer also contains some utility routines for creating the TreeNodes programmatically. This includes Clear() which clears all nodes from the TreeContainer and routines to add roots or interior nodes. At their simplest, these never have to deal directly with names in which case the code produces internal names. So, for instance, AddNode(Object, TreeNode) wraps the object in a new TreeNode, gives it a name and sets its parent to the TreeNode passed in. The TreeNode produced to wrap the object is returned. See the VisLogTree for an example of how to use these to easily produce the trees in a TreeContainer at runtime.
The TreeNode containers implement the ITreeNode interface and hence are themselves the ITreeNodes necessary for GraphLayout's calculations.
Points of Interest
There are many additions which could easily be added to this control. I've mentioned several in the text already - arbitrary pen for drawing connections, different types of connections, different orientations for the graph (i.e., left to right or bottom to top), a routed event for when nodes get collapsed or uncollapsed, etc. It seems like a valuable control at this point, however, and to be honest, I'm anxious for new territory to cover so I'm putting it out there as is.
The algorithm proved to be much trickier than I had initially supposed. There are a fair number of exceptions and gotchas to the algorithm as I originally read it. It might have been easier to just blindly follow the algorithm as described in Dr. Dobb's article in the hyperlink above, but I didn't have that article ahead of time and there are a few things I'm not fond of in the algorithm as written there.
There are two samples. One is an XAML version of the graph used in the paper mentioned above just to verify that it turned out correctly as described in the paper. The other gives the visual and logical tree for a dialog loosely based on one in "WPF Unleashed" by Adam Nathan, an excellent book. It's the dialog that Nathan uses to illustrate logical and visual trees so you can check that it gives the right information. The nodes in the second one are buttons which toggle whether their subgraphs are collapsed or not. There is also a button to remove or add back in the label at the top of the dialog which I used for debugging and left in there.
A point I wasn't aware of until working on this control is the RegisterName/UnregisterName methods on FrameworkElements. When I first tried to create the tree control programmatically, I naively set the name on my TreeNodes and then used FindName() to locate them later. Wrong! If you do the same, you will be told that no such control name exists. You must use the RegisterName() method to register the name with the parent in order to make this work. Similarly, if you remove a control you really should do an UnregisterName(). I've read a lot on WPF and this is the first time I've ever seen this. It seems like this should be a little more visible in the documentation out there. The utilities on the TreeContainer which allow easy production of the TreeNodes takes care of all this automatically.
History
- 9-20-2008 First version
- 2-21-2009 Added Silverlight control
