Click here to Skip to main content
15,511,378 members
Articles / Desktop Programming / WPF
Article
Posted 20 Sep 2008

Tagged as

Stats

264K views
8.7K downloads
139 bookmarked

A Graph Tree Drawing Control for WPF

Rate me:
Please Sign up or sign in to vote.
4.84/5 (34 votes)
23 Feb 2009CPOL10 min read
This article describes and implements a graph drawing control for tree structures structured in a WPF panel.
Sample Image - maximum width is 600 pixels

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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Web Developer
United States United States
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.

Comments and Discussions

 
GeneralRe: silverlight Pin
darrellp21-Feb-09 20:17
darrellp21-Feb-09 20:17 
GeneralRe: silverlight Pin
jhuang7899-Sep-10 8:26
jhuang7899-Sep-10 8:26 
GeneralRe: silverlight Pin
darrellp9-Sep-10 13:38
darrellp9-Sep-10 13:38 
GeneralChanging layout of individual levels Pin
Richard Spiers5-Jan-09 0:20
Richard Spiers5-Jan-09 0:20 
QuestionHow to remove a node from tree? Pin
gecko00727-Nov-08 23:22
gecko00727-Nov-08 23:22 
AnswerRe: How to remove a node from tree? Pin
darrellp28-Nov-08 9:57
darrellp28-Nov-08 9:57 
QuestionHorizontal and vertical alignment stretch Pin
MBursill27-Oct-08 8:33
MBursill27-Oct-08 8:33 
AnswerRe: Horizontal and vertical alignment stretch Pin
darrellp27-Oct-08 12:07
darrellp27-Oct-08 12:07 
Please read the entire response, even if you find it tedious. I didn't think of what I believe to be the best answer until the very end of the response.

Thanks. It's really difficult to do something like this in the control itself because it has to ask the nodes what size they are in order to arrange them properly so in the end it has to size itself according to what the underlying nodes tell it about their individual sizes. Also, it can't really tell each individual node a pre-assigned size since the size dependency flows from node to control rather than the other way around.

However, hope is not lost! Fortunately, WPF really has an answer for just about everything and I think your answer is the ViewBox which takes any control of any size and scales it to fit wherever the ViewBox is. So put the tree control in the ViewBox and then let your ViewBox expand to fit wherever you like. Of course, the nodes will be distorted by the scaling, but that's the only option I've got right now. In that sense, the control is more like a TextBox in that it really can't do much if it's nodes want to be a particular size.

The only other possibility is placing more or less space between the nodes but this is kind of ugly. Plus, it would really cause problems if, for instance, you were to place it in a scroll viewer which gives it "infinite room" since the scroll viewer will accommodate any size control. Here's some thoughts on what such a feature would entail...

I'd do it in the GraphLayout code rather than the TreeContainer code since that's really where the arranging should go on, plus this would extend it to anything else that might make use of the GraphLayout code. This means you have to pass down a desired width and height in addition to the root node. It also means that this needs to be an optional thing since it will generally make a lot of sense to allow a specific spacing. This would also have to be done after the entire graph had been layed out in the conventional manner since the position/sizes of all nodes is required before you can know the width of the graph and after that you'll have to determine the buffer space you need to insert to achieve your optimal size. So this entires a third pass through all the vertices. Finally, I'm not sure how you'd determine what spacing to use. The first intuition is to figure the difference between the "natural" width and the one you want, divide that by...what? You can't really say "the number of nodes wide the graph is" because that's not even well definied - different parts of the graph have different widths of layers. What you want is some set of nodes who independently determine the width of the tree and that's not an obvious thing to determine. Obviously, in some sense, the algorithm currently "determines" this, but only in the most roundabout way with the information being passed up and down in call trees and not specifically recorded so to try to determine this information after the fact would be difficult and I'm not even sure right off the bat how to keep track of the information during the running of the algorithm (though I'm sure it would be possible if push came to shove since, like I say, it's implicitly determined in the course of running the algorithm). Actually, even determining this isn't enough. If, for instance, you have three nodes that, together determine the width of the graph, there may be some set of 5 narrower nodes who are currently narrower than those three but if you add the same constant internode width to all nodes, those five will get wider faster than the three and may end up being the deciding factor which will throw off your original calculations. Yikes! It's harder than I had originally imagined!

All in all, I think this would be a very tough feature to implement as spacing between nodes and would actually break many things like scrollviews so I'm not really that motivated to take it on myself. I'd say if the ViewBox works, that's great. If you've got text in the nodes that you don't want distorted, one possibility is to use tooltips to indicate what's in each node. Not a great option I don't think but I'm just trying to think of all possibilities.

Actually, here's a final possibility which I would suggest. You could fiddle with the internode width yourself. For instance, in TreeContainer you could binary search, calling into the GraphLayout code with different internode widths until you got within some delta of the width you were looking for. It's pretty quick in general so I think you could probably get away with this and I think it's probably the closest you're going to get to a reasonable solution. So in MeasureOverride you'd put the constructor/layout calls to LayeredTreeDraw in a loop which does binary search on horizontal and vertical buffer widths until you were close to what you wanted. I'd still be tempted to put the whole result in a ViewBox so it would scale to exactly the size you were looking for. The binary search within TreeContainer would just get you near enough the "proper" value that the distortion from scaling wouldn't look too bad.

That's probably more than you cared to hear about the subject so I'll shut up and let you mull over things. I hope you can get something that suits you.
GeneralRe: Horizontal and vertical alignment stretch Pin
darrellp27-Oct-08 12:23
darrellp27-Oct-08 12:23 
GeneralRe: Horizontal and vertical alignment stretch Pin
MBursill27-Oct-08 12:31
MBursill27-Oct-08 12:31 
GeneralRe: Horizontal and vertical alignment stretch Pin
darrellp27-Oct-08 12:40
darrellp27-Oct-08 12:40 
GeneralGreat! However connections are not printed. Pin
Patrick Lassalle23-Sep-08 7:22
Patrick Lassalle23-Sep-08 7:22 
GeneralRe: Great! However connections are not printed. Pin
darrellp23-Sep-08 10:45
darrellp23-Sep-08 10:45 
GeneralRe: Great! However connections are not printed. Pin
darrellp23-Sep-08 11:19
darrellp23-Sep-08 11:19 
GeneralRe: Great! However connections are not printed. Pin
darrellp23-Sep-08 11:25
darrellp23-Sep-08 11:25 
GeneralRe: Great! However connections are not printed. Pin
Patrick Lassalle23-Sep-08 12:40
Patrick Lassalle23-Sep-08 12:40 
GeneralRe: Great! However connections are not printed. Pin
darrellp23-Sep-08 15:34
darrellp23-Sep-08 15:34 
GeneralRe: Great! However connections are not printed. Pin
Patrick Lassalle24-Sep-08 1:20
Patrick Lassalle24-Sep-08 1:20 
GeneralRe: Great! However connections are not printed. Pin
darrellp24-Sep-08 6:33
darrellp24-Sep-08 6:33 
GeneralThis is funny Pin
Sacha Barber20-Sep-08 21:36
Sacha Barber20-Sep-08 21:36 
GeneralRe: This is funny Pin
darrellp20-Sep-08 22:03
darrellp20-Sep-08 22:03 
GeneralRe: This is funny Pin
Sacha Barber21-Sep-08 4:56
Sacha Barber21-Sep-08 4:56 
GeneralRe: This is funny Pin
darrellp20-Sep-08 22:17
darrellp20-Sep-08 22:17 
GeneralRe: This is funny Pin
dosdemon20-Sep-08 23:56
dosdemon20-Sep-08 23:56 
GeneralRe: This is funny Pin
Sacha Barber21-Sep-08 4:55
Sacha Barber21-Sep-08 4:55 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.