1
This article
includes two very different basic
assemblies and a couple of test
assemblies for WPF. The first basic
assembly is
Graph Layout
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
.
2
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.
3
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
Graph Layout
.
It's simple enough to use but definitely
the most complicated part under the
covers.
4
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.
5
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.