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
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
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
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
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 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.Y(treeNode) where "
treeNode" is the
ITreeNode in question.
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.
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
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.
TreeNode containers implement the
ITreeNode interface and hence are themselves the
ITreeNodes necessary for
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
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.
- 9-20-2008 First version
- 2-21-2009 Added Silverlight control
I've been doing programming for close to 30 years now. I started with C at Bell Labs and later went to work for Microsoft for many years. I currently am a partner in Suckerpunch LLC where we produce PlayStation games (www.suckerpunch.com).
I am mainly interested in AI, graphics and more mathematical stuff. Dealing with client/server architectures and business software doesn't do that much for me. I love math, computers, hiking, travel, reading, playing piano, fruit jars (yes - I said fruit jars) and photography.