On tree diagrams and XML

By NetronProject   |   Published: 03 July 2005   |   Reader Level:  Advanced

A control to edit tree structures is described with an emphasis on its XML capabilities and the underlying layout algorithms.

Download source files - 242 Kb
Download demo project - 194 Kb

---

Introduction

In a previous article, a blueprint was described to implement a diagramming control. The control described therein was able to display simple flowcharts, to interactively edit the shapes and connections, and was meant as an easy introduction to diagramming using C#. It was also pointed out how the control could be improved or used and how it eventually could evolve to a more feature-complete one like the full Netron graph library. In this article, we will use the foundations laid in that article and describe a diagramming control with a more specific goal: displaying and editing tree (data) structures.

A tree structure is a type of data structure in which each element is attached to one or more elements directly beneath it. The connections between elements are called branches. Trees are often called inverted trees because they are normally drawn with the root at the top. The elements at the very bottom of an inverted tree (that is, those that have no elements below them) are called leaves. Inverted trees are the data structures used to represent (for example) hierarchical file structures. In this case, the leaves are files and the other elements above the leaves are directories. Loosely speaking, one could say that a tree structure is anything you can cast or display in a tree control, whereby 'tree control' is referred to the common tree control found in Visual Studio. In the literature, you will often see the term 'binary tree' (or B-tree) which is a special type of inverted tree in which each element has only two branches below it.

Any XML data has a tree structure since an XML-node can be underneath one and only one other XML-node, unless it's the root of the XML data. Conversely, you can take any tree structured data and save (serialize or convert) it to XML. Recall for example that most website directories or menus are basically XML files.

The use (and success) of diagramming techniques to display XML is well-known. Commercial products like XMLSpy [7] tremendously simplify the editing of XML (and other XML-related formats like XSD), and Visual Studio's XSD designer makes it a breeze to edit schemas. The advantage of a diagram control over a tree control lies probably in the fact that a diagram or graph gives a better insight in to the inter-relation of nodes and more clearly displays the depth of branches, where the leaves, are and so on.

This article describes in some details how to develop a tree-diagram control (codenamed 'Lithium' in the source code) which allows you to edit any tree data. The following list gives an overview of its features:

• Automatic layout of the tree both horizontally and vertically.
• The standard add/delete/edit mouse actions.
• Various types of connections; the traditional rectangular connections, the default straight line, Bezier connections (popular in mind-mapping applications).
• Flexible import/export of XML data using .NET's XmlSerializer class.
• Depth First Traversal (DFT) and Breadth First Traversal (BFT) of the tree.
• The visitor pattern allows you to traverse the graph and perform actions (see the colouring example or the XML export example).
• Expand/collapse branches (sub-branches persisting in their state).
• Various hotkeys to easily edit the diagram.
• Easy to understand and, hence, easy to extend or modify architecture.
• 'seek new parent' on moving shapes or branches. I.e., on moving a sub-branch, you get visual feedback about a possible new parent. If no parent is found, the sub-branch will be connected back to its previous parent.
• Editing of properties via the property grid.
• Various examples are given on how to use the visitor interface.
• Random graph generation, random node addition.
• Lots of comments in the code which, in addition to this article, should make it easy to adapt the control in your own applications.

As mentioned before, the control is built upon the previous work [9] and you're encouraged to read it before reading this one. We will review in the next section the essential ingredients but you are referred to the Netron Light article, or the articles, FAQ and white papers [3] on the Netron site [1], for more details.

Finally, before jumping into the internals, let's recall that terms like graph and diagram, edge and connection, node and shape,...are often used synonymously and emphasize a different aspect of the same entity.

Class structure and review of internals

This section reviews the class structure of the control and how everything fits together. When comparing with the Netron Light control, it should be noted that the structure was simplified because of the following:

• Since connections cannot live independently of shapes, connectors have no function and were dropped.
• Every node has one connection, one parent and a collection of children. Hence, the ShapeBase has got connection, parentNode and childNodes members.
• The diagram has an implicit direction (it's a digraph). By convention, the 'From' part of a connection is always the child while the 'To' part is always the parent. This remark is important when serialization is considered.
• Connections cannot be added which simplifies the OnMouseDown handler.

The Entity class

The Entity class is an abstract base class for all the diagram elements. It might be helpful at this point to take a look (again) at the screenshot of the Netron Light control [9] to recall the inter-dependence of the classes. All the common members are defined in the Entity, which contains the following four fundamental abstract methods:

• Paint(Graphics): how the diagram element is painted on the canvas.
• Move(Point): how the diagram element can be moved on the canvas.
• Invalidate(): what additional actions have to be performed prior to the painting.
• Hit(Point): given a mouse location (the Point parameter), is this diagram element being hit on that location?

The GraphAbstract class

The GraphAbstract is not an abstract class as the name suggests but it refers to the fact that this class contains the essential data of the diagram, i.e., the abstract representation of the diagram. A diagram is in essence just a collection of shapes and connections and, indeed, this class consists (besides a few additional properties) of:

• The Shapes collection; a strongly typed collection of ShapeBase objects.
• The Connections collection; a strongly typed collection of Connection objects.
• The Root; a pointer to the unique root of the tree.
• A temporary (volatile) connection used by the 'seek new parent' method, see below.

The class is central both to the serialization and the GDI process;

• When the graph is persisted to file, the GraphAbstract class is serialized (via the mechanism described below) and inversely, when the data is deserialized, a GraphAbstract instance is recreated and filled up with the filed data.
• The overridden OnPaint method of the control loops over the two collections (Connections and Shapes) and simply calls the individual Paint methods to draw the diagram on the canvas. Connections are looped first since they have to be drawn underneath the shapes.

The central function of this class implies that any (inherited) instance of the ShapeBase will not be visible on the canvas unless it's been added to the GraphAbstract.

The fact that the traversal algorithms have been added to the GraphAbstract class is irrelevant since they could have been added to the control as well. It's a matter of convenience since you'll notice that both the Shapes and the Connections collections are also accessible via the control class and are pointing to the GraphAbstract.

The ShapeBase class

The ShapeBase class is an (abstract) template class for all shapes in the diagram. Besides the inherited Entity members, it adds the following:

• the Connection property contains the unique connection to a parent shape. This member is null if and only if the shape is the root of the diagram.
• the ChildNodes collection contains the collection of children.
• the ParentNode contains a pointer to the unique parent shape. Like the Connection, this member is null if and only if the shape is the root of the diagram.

Implementing your own shapes is really a matter of inheriting from this class and implementing the four basic members from the inherited ShapeBase class (Paint, Move, Invalidate and Hit) as described above. We refer to the Netron Light article again for more details [9].

The Connection class

A connection connects two shapes. As evident as it might sound, this is however different from both the Netron Light and the full Netron graph library because of the simplification we mentioned above; connectors are not necessary in this control because connections cannot be created individually. The Move() method is not implemented for the same reason.

The Hit() and Paint() methods contain the same code you'll find in the Netron library and might seem complicated at first but really rely only on simple geometry and approximations.

The XML import/export

The control allows you to save/open a diagram to/from disk, whether you consider it an 'export' or a 'save' is a matter of discussion. In the section below on the visitor pattern, another method is described to export diagram data to XML. The diagram serialization to disk as implemented in the control is based on .NET's XmlSerializer class [5] and is very flexible. It allows you to import/export to whatever XML compliant schema by placing some C# attributes.

This XmlSerializer approach allows you to add/remove serialized properties by means of simple addition/removal of an attribute: the GraphData attribute. Anything marked by this attribute will be serialized and, conversely, anything serialized to XML will be matched to corresponding properties if tagged by this attribute. The name and the appearance of the XML element in the XML is set by means of .NET attributes. Together, this means that you can import/export the diagram from/to any XML structure by customizing a few attributes and where they appear.

To make the IO process modular, the serialization classes were put separately and the GraphData attributes were not placed directly on the GraphAbstract but on an additional abstraction layer. It means that you can add or implement multiple XML serializations without interference. You can copy the IO directory in the source code and modify the GraphSerialize and the GraphType classes according to your own XSD schema with a minimum of effort.

Serialization

The serialization process consists in essence of the following recipe:

• take the GraphAbstract and hand it over to the GraphType class; this class describes the root-level of the exported XML.
• the GraphType loops over the shapes and connections and collects all properties (by means of .NET reflection) tagged by the GraphData attributes; this creates a hashtable of key-value pairs.
• the obtained hashtable is converted into appropriate edge, shape and data classes marked with XmlSerializer attributes; a shape becomes a NodeType, an edge becomes an EdgeType and so on.
• the Serialize() method is called of the XmlSerializer class which will start with the GraphType class (and loop down through the sub-collections) and automatically write the corresponding XML.

The flexibility of this method is hence a combination of the reflection mechanism and the built-in XML serialization in the .NET framework.

The GraphType class is marked with the following attributes:

[XmlType(IncludeInSchema=true, TypeName="graph.type")]
[XmlRoot(ElementName="NetronLightGraph", IsNullable=false, DataType="")]
public class GraphType
{...}

and tells the XmlSerializer that the root of the XML should be called 'NetronLightGraph' but it can be whatever you wish. The XmlType is related to schema information. Inside the GraphType, the Nodes and Edges collections can be found:

[XmlElement(ElementName="Node", Type=typeof(NodeType))]
public virtual GraphDataCollection Nodes
{...}

These collections get filled by the Serialize() method in the GraphSerializer class:

public void Serialize(XmlWriter writer)
{
    GraphType graph = new GraphType();
    GraphAbstract g = site.graphAbstract;
    foreach ( ShapeBase s in g.Shapes )
    {
        graph.Nodes.Add(SerializeNode(s));
    }
    foreach(Connection c in g.Connections)
    {
        graph.Edges.Add(SerializeEdge(c));
    }
    // serialize
    XmlSerializer ser = new XmlSerializer(typeof(GraphType));
    ser.Serialize(writer,graph);
}

where the SerializeNode() and SerializeEdge() are the methods which do the real work. For example, the SerializeNode returns a NodeType object which, as described in our recipe above, internally loops over all properties:

private NodeType SerializeNode(ShapeBase s)
{
        Hashtable attributes = GraphDataAttribute.GetValuesOfTaggedFields(s);
        NodeType node = new NodeType();
        foreach(DataType data in DataTypesFromAttributes(attributes))
            node.Items.Add(data);
        return node;
}

The GetValuesOfTaggedFields is a standard loop over class properties by means of reflection:

foreach (PropertyInfo pi in value.GetType().GetProperties())
{
    if (Attribute.IsDefined(pi, typeof(GraphDataAttribute)))
    {
        vs.Add(pi.Name,pi.GetValue(value,null));
    }
}

The properties are collected in a generic data-collection, which can contain more-or-less any kind of data. The constraint is the fact that XML is really a string format and that whatever is being serialized needs to be converted in some way to the string data type. For example, the shape's serialized color property is not an RGB value but an Int32 value, which can be converted back to a color by means of the Color.FromRGB method. You will also notice that the serialization uses the GUID-valued UID property of the Entity class to uniquely identify the elements of the diagram and to re-connect connection on deserialization, see the next section on this.

Deserialization

The deserialization works in the same way, though a little more care is required since the XmlSerializer class does not automatically map XML to the correct .NET data types. Deserialization means, in this context, re-building the GraphAbstract from XML data.

The recipe is in this case:

• loop over the ShapeType collection and instantiate accordingly (using reflection again).
• assign the properties of the shape by looping over the key-value pairs and use reflection again to match.
• loop over the EdgeType collection and instantiate connections.
• attach the connection back to the previously instantiated shape by means of the serialized UID; i.e., the end-points of the connection match one-to-one to shapes.

As mentioned above, the tricky point is the data mapping in the reflection:

foreach (PropertyInfo pi in shape.GetType().GetProperties())
{
    if (Attribute.IsDefined(pi, typeof(GraphDataAttribute)))
    {
        if(pi.Name==dt.Key)
        {
            if(pi.GetIndexParameters().Length==0)
            {
                if(pi.PropertyType.Equals(typeof(int)))
                    pi.SetValue(shape,Convert.ToInt32(dt.Text[0]),null);
                else if(pi.PropertyType.Equals(typeof(Color)))
                //Color is stored as an integer
                    pi.SetValue(shape, 
                      Color.FromArgb(int.Parse(dt.Text[0].ToString())), null);
                else if(pi.PropertyType.Equals(typeof(string)))
                    pi.SetValue(shape,(string)(dt.Text[0]),null);
                else if(pi.PropertyType.Equals(typeof(bool)))
                    pi.SetValue(shape,Convert.ToBoolean(dt.Text[0]),null);
                else if(pi.PropertyType.Equals(typeof(Guid)))
                    pi.SetValue(shape,new Guid((string) dt.Text[0]),null);
            }
            else
                pi.SetValue(shape,dt.Text,null);

        }
    }
}

where, depending on the amount of properties serialized and their data type, you can get a long list of test-and-matches.

Traversals

A traversal is a technique or algorithm for processing the nodes of a tree in some order. The most popular tree traversals are:

• Depth First Traversal, sometimes called depth first search or DFT traversal: an algorithm that considers outgoing edges of a node before any neighbours of the node, that is, outgoing edges of the node's predecessor in the search. Extremes are searched first. Typically, this algorithm is the solution if you want to delete a directory but sub-directories need to be deleted first.
• Breadth First Traversal or level order traversal or BFT traversal: an algorithm that considers neighbours of a node, that is, outgoing edges of the node's predecessor in the search, before any outgoing edges of the node. Extremes are searched last. Typically, this algorithm is used when a tree search is performed and the depth or node-level in the tree being searched has some meaning.

In the visitor examples, we have used both algorithms to clarify the difference; see the next section on this.

Depth first algorithm

The DFT algorithm is well known and can be found in many sources. In pseudo-code, it amounts to:

DFT(action, shape)
{
    shape.action
    foreach(child in shape.childNode)
    {
        DFT(action, child)
    }
}

That is; visit and iterate through a shape's child nodes before continuing to or staying on the same level. The 'action' parameter is usually associated to the visitor pattern and we explain in the next section more in detail the IVisitor interface. The algorithm can be started from any shape but is usually launched with the root node as input, and this is the reason that you'll find two overloads of the method with the following signatures:

private void DFT(IVisitor visitor, ShapeBase shape)
private void DFT(IVisitor visitor)

Breadth first algorithm

The BFT algorithm is slightly more complicated and requires a queue but is not iterative. In pseudo-code, it amounts to:

BFT(action shape)
{
    make new queue
    enqueue(shape)
    while(not queue is Empty)
    {
        shape = queue.dequeue()
        shape.action()
        foreach(shape2 in shape.childNodes)
            enqueue(shape2)
    }

}

Variations of the algorithm use linked-list or other structures and you can find a vast amount of information on the BFT algorithm on the net. To understand the method, it's helpful to simulate it with a little example on paper but you can also find a nice visualization of it in the coloring example included in the demo application. Like the DFT, the 'action' parameter is an IVisitor implementation, the 'shape' can be any node, and the method is overloaded.

The visitor pattern

The visitor design pattern is a way of separating an algorithm from an object structure [6]. The idea is to use an object structure of element classes, each of which has an accept method that takes a visitor object as an argument. The visitor is an interface that has a different visit method for each element class. The accept method of an element class calls back the visit method for its class. Separate concrete visitor classes can then be written that perform some particular operations.

The visitor pattern also specifies how iteration occurs over the object structure. In the simplest version, where each algorithm needs to iterate in the same way, the accept method of a container element, in addition to calling back the visit method of the visitor, also passes the visitor object to the accept method of all its constituent child elements.

The IVisitor interface is defined as follows:

public interface IVisitor
{
   void Visit(ShapeBase shape);
    bool IsDone { get; }
}

where the Visit() method specifies some action on visiting the shape while the IsDone property allows to stop the visiting process at any time, which is a useful thing when you use a certain search and you need to break the process on finding a match. There is also an extension of this interface in the form of:

public interface IPrePostVisitor : IVisitor
{
    void PreVisit(ShapeBase shape);
    void PostVisit(ShapeBase shape);
}

which allows you to perform a certain action before, on and after visiting a shape. In the demo application, a few examples were included to demonstrate how the interface can be used in concrete situations;

• Info visitor: this visitor example simply prints out the name of the visited shape but can also print out a complete summary of shape information.
• Coloring visitor: coloring the shapes depending on their level. The color gradient used in this example is stored in a pre-defined array and the level (defined in the ShapeBase class) is used to pick out a color.
• XML visitor: this visitor example implements the IPrePostVisitor interface and uses the PreVisit to open the XML tag while the PostVisit method closes it again. Note that this example requires the DFT algorithm to construct the XML.

The XML visitor can be extended to include properties and other information from the shapes which means that you can use it to export the tree structure just like the XML serializer. Note, however, that this method does not offer (in contrast to the XmlSerializer) the flexibility to easily import the XML data again.

The layout, deleting and collapsing branches

There are two layout algorithms in the control (horizontal and vertical layouts) but since they can be changed into one another by simply interchanging Width with Height, we'll review only the vertical layout algorithm (i.e. the VerticalDrawTree method in the LithiumControl class).

The algorithm is, in essence, a recursive measuring of shape widths, and consists of finding the location of a shape in function of its underlying children. In the source code, additional attention is given to whether a shape is expanded but we'll put this aside for a moment. The general recipe is:

• the X-position of a shape is centered above the children nodes.
• the Y-position is just one branch-height above the children.

Again, there are some exceptions to the rule but we'll come back to this later. To know the center of the shapes, you need to know the width of the children, which depends on its turn on their children. This is translated to:

VerticalDrawTree(ShapeBase containerNode, int shiftLeft, int shiftTop)
{
        for(int i =0; i<containerNode.childNodes.Count; i++)
        {
            if(containerNode.childNodes[i].visible)
            {
                returned = VerticalDrawTree(containerNode.childNodes[i], 
                   shiftLeft + childrenWidth, shiftTop + branchHeight );
                childrenWidth += returned;
            }
        }
        if(childrenWidth>0)
                childrenWidth=containerNode.Width;
}

The function is called recursively and returns the total width of the children. Note that the recursion is broken if a child is a leaf in which case the function essentially returns the width of the node. Since we now know the location and width of the children, we can place the parent. There are two possibilities: the node is a parent in which case it is placed halfway the children, or it's a leaf node and it's placed just a little further from the previous node, i.e., the shiftLeft location passed as a parameter:

if(containerNode.childNodes.Count>0)
{
        float firstChild = containerNode.childNodes[0].Left+ 
        containerNode.childNodes[0].Width/2;

        float lastChild = 
         containerNode.childNodes[containerNode.childNodes.Count-1].Left + 
         containerNode.childNodes[containerNode.childNodes.Count-1].Width/2;

        containerNode.rectangle.X = Convert.ToInt32(Math.Max(firstChild + 
         (lastChild -firstChild - containerNode.Width)/2, firstChild));

}
else
{
        containerNode.rectangle.X = shiftLeft;
}

To start the recursion, we feed the method with the root node and a certain left shift and right shift:

VerticalDrawTree(graphAbstract.Root,false,marginLeft,this.graphAbstract.Root.Y);

The last two parameters can be anything to position the whole diagram but it's convenient to have the root node somewhere near the top of the control and the whole diagram a little right from the edge.

This concludes the description of the bare bones but, as you can notice in the source code, some more attention is given to certain layout pathologies:

• a shape's width can exceed the width of its children.
• a shape's height can be bigger than the (constant) branch height described above.

Also, how to collapse/expand branches and use the same algorithm? At this point, one has to take care to split two different aspects of the control: the layout process and the drawing process. As far as the layout algorithm is concerned, the pathologies stated above really only mean additional if-then-else statements. As far as the drawing process is concerned, only the collapse/expand feature makes a difference: whatever the layout algorithm, the paint process always simply executes the Paint method. Hence we need two additional fields for a collapse:

• expanded: if set to true, all children need to be visible and the layout algorithm needs to take them into account but not recursively.
• visible: if set to true, the parent is set to expanded and the shape should be drawn on the canvas.

Referring to the code outlined above to calculate the children's width, it now becomes:

if(containerNode.childNodes[i].visible)
{
    if((branchHeight - containerNode.Height) < 30)
    //if too close to the child, shift it with 40 units
      verticalDelta = containerNode.Height + 40;

    returned = VerticalDrawTree(containerNode.childNodes[i], isFirst, 
               shiftLeft + childrenWidth, shiftTop + verticalDelta ); 

    childrenWidth += returned;
}

where an additional test was added to see if the parent node is too close to its children, shifting it a 40 units in that case. Similar modifications are performed to include the cases above in the rest of the code, the positioning in particular. The precise values and exceptions are found by trial-and-error, whether a layout is satisfactory is to some extend a matter of taste. You should try and modify things in function of your own application or tree data. This (as an apology) also means that a layout is 'good' until the next irregularity is found.

Finally, a note on the mouse interaction with the control and the graph layout: since expanding/collapsing a branch is a recursive process, the DFT algorithm is necessary and therein lies the justification to include it in this control, besides the ease with which you can walk through the tree via IVisitor classes defined outside the control. The BFT together with an ExpanderVisitor is used to collapse/expand branches:

public void Visit(ShapeBase sh)
{
    sh.Expand();
}

The Expand() method sets the expanded and visible fields to true and the rest is taken care of by the drawing and the layout process. The deletion of shapes and branches is handled in a similar fashion and you can find the DeleteVisitor in the code, which on each shape visit, simply deletes the shape via the DFT algorithm.

Moving nodes and the 'seek parent' feature

Branches and individual nodes can be dragged around on the canvas and attached to a new parent, which is an easy and visual way to change the underlying XML structure of the data. On dragging around, visual feedback is given in the form of a volatile red-colored connection to the nearest (node) neighbour of the node being dragged, similar to the behaviour of this feature found in many commercial applications [7]. The term 'volatile' refers here to the fact that this connection is not really part of the diagram until the mouse button is released where after the connection is made 'solid' and the former parent/child connection is disposed. In fact, if the node being dragged is not released anywhere near another node (i.e. the volatile connection is not visible), the node will be placed back under the original parent. This feature can be found in the code under the SeekNewParent() method and works together with the boolean Pickup member of the ShapeBase and the mouse events.

private void SeekNewParent(ShapeBase shape)
{
    double best = 10000d;
    int chosen = -1;
    double dist;
    ShapeBase other;
    for(int k=0;k<Shapes.Count; k++)
    {
        other = Shapes[k];
        if(other!=shape && other.visible && 
           other.parentNode!=shape && !other.pickup)
        {
            dist = 
                Math.Sqrt((other.X-shape.X)*(other.X-shape.X)+ 
                          (other.Y-shape.Y)*(other.Y-shape.Y));
            if(dist<best && dist< 120)
            chosen = k;
        }
    }
    if(chosen>-1)
    {
        neoCon = new Connection(shape, Shapes[chosen], Color.Red,2f);
        neoCon.visible = true;
        neoCon.site = this;
        return;
    }
    neoCon = null;
}

When the mouse button is pressed above a shape, the shape's Hit method will help to set the selectedEntity member of the control (see again the Netron Light article on this [9]) and the whole branch underneath will be picked up (pickup = true). Before the rest of the action is handled in the OnMouseMove handler, a temporary reference is set to the current parent and the current connection until it is released. In the mouse move handler, the move is handled and the SeekNewParent() method is called. This method loops over all shapes and tries to find the closest neighbor with a cut-off of 120 pixels. If a shape is found satisfying this criteria, it is returned and a temporary (volatile) connection is created between the dragged node and the possibly new parent. This volatile connection is drawn in the OnPaint method of the control and is not part of the Connections collection since it has no meaning outside the dragging operation. Finally, when the mouse button is released, the volatile connection (if any) is made permanent or the reference to the previous parent is picked up again to reset the structure to its former state.

Note that the type of connection (default, traditional or Bezier) is set on the control level and not on an individual basis, which implies that the volatile connection gives a real feedback of how the state will be when the mouse is released. The layout algorithm could be used in addition to giving precise feedback on how the diagram would look like structurally, but this would produce a lot of 'shaking' in the diagram and is therefore omitted.

In contrast to the other Netron graph libraries, this control does not allow you to move shapes freely over the canvas though the demo application allows you to temporarily disable the auto-layout. It requires, however, very little code to add this feature, and you are referred to the Netron Light article for an in-depth overview. Note that this control, just like the one described there, uses relative (i.e. vector) parameters to move shapes and entities instead of absolute coordinates. This means that Point-valued methods get a relative parameter instead of an absolute control position value.

Diverse functions and remarks

• The control was tested with thousands of nodes (using [4] as XML source) and gave satisfactory results in terms of performance though nothing in the code has been optimized. The display is, however, huge and requires a zoom-feature. This feature is implemented in the full graph library but for the sake of simplicity was left out in this control.
• The Bezier connection together with the horizontal layout could easily be extended to create a mind-mapping application. This would require some additional code to include branches emanating both from the left and the right of the root node.
• The layout code does not assume anything about the diagram and could be used on graphs in general (i.e., non-tree graphs). Some preliminary analysis could be performed on the imported data before drawing it; spanning tree, cyclic property, and so on. You can find in the full Netron library (more specifically, the data structures library) a collection of graph analysis algorithms to test and explore graphs.
• The upcoming release of Visual Studio 2005 features a new UML modeling or class design tool which, as far as the visual appearance is concerned, closely matches this control. The additional code to implement reverse engineering, refactoring and forward engineering is considerable though a simple assembly reflector (displaying the class structure of the assembly) on top of this control would be easy to code.
• The compiled class reference was put in the debug directory of the assembly and can be accessed from within the demo application. Of course, if you re-compile, you need to move/copy the reference by hand. The help was compiled with the wonderful NDoc compiler.
• Some hotkeys have been defined in the control to ease the manipulation of the diagram;
  • Shift-click: moves the whole diagram over the canvas (globalMove = true in the code).
  • Control-click: allows you to pick up a shape or branch and move it underneath another shape (via the discussed 'seek new parent').
  • Alt-click: add a new child node underneath the clicked node.
  • Double-click: collapse/expand the branch underneath the double-clicked node.
• It should be emphasized that the global move (via the Shift-click) is implemented just like the ordinary shape-move action in the Netron Light library and does not use an absolute position but a shift vector;
  

  if(globalMove)
  {
      foreach(ShapeBase shape in Shapes)
      {
          shape.Move(new Point(p.X-refp.X,p.Y-refp.Y));
          Invalidate();
      }
  }

• Finally, for those who wish to have the tree drawn in the complementary directions (bottom-up or right-left), you can achieve this by means of a single plus-to-minus change in the algorithm:

  private int HorizontalDrawTree(ShapeBase containerNode, 
                      bool first, int shiftLeft, int shiftTop)
  {
      ...
      returned = HorizontalDrawTree(containerNode.childNodes[i], isFirst, 
        shiftLeft +/- horizontalDelta , shiftTop + childrenHeight );
      ...
  }

  and similarly for the vertical algorithm:

  private int VerticalDrawTree(ShapeBase containerNode, 
                      bool first, int shiftLeft, int shiftTop)
  {
      ...
      returned = VerticalDrawTree(containerNode.childNodes[i], isFirst, 
        shiftLeft + childrenWidth, shiftTop +/- verticalDelta );
      ...
  }

Conclusion and final remarks

This article gives you a jump-start if you wish to incorporate tree diagrams in your applications, and can easily be adapted or extended to be used in various scenarios. In designing the control, we have tried to keep the code simple yet versatile and solid. Furthermore, the layout algorithm can certainly be used outside the current structure in other/your code with a minimum of efforts. The tree layout will be integrated into the next release of the Netron graph library (version 2.2), which already contains the (fancy but more complicated) spring-embedded algorithm. If this article has sharpened your appetite for more diagram-food, or you wish to extend the range of features, you are encouraged to visit the Netron website for more information and to read the paper on the graph library's architecture [3].

Acknowledgement

I wish to thank Geri for her patience and encouragement, Howard van Rooijen for correcting my horrible English as well as his sparkling ideas and suggestions, Tannya Peeters for her constructive comments, and the people around the world who pop-up in my mailbox or on the Netron forum for their feedback and appreciation. Thank you all.

References

• [1] The Netron Graph Library: where you can find tutorials, download the full Netron library, additional documents and applications.
• [2] The Netron Project forum: public forum related to the graph library.
• [3]The Netron Graph Library White Paper and Architecture Pape both in PDF format, in-depth information about 'what is it?' and 'how is it made?'.
• [4] The Tree of Life web project: The Tree of Life Web Project (ToL) is a collaborative effort of biologists from around the world. On more than 3000 World Wide Web pages, the project provides information about the diversity of organisms on Earth, their evolutionary history (phylogeny), and characteristics.
• [5] You can read about the XmlSereliazer class on MSDN.
• [6] See for example the www.dotfactory.com for a nice overview of the visitor design pattern.
• [7] Altova XMLSpy: a very complete suite of tools to edit XML and related formats.
• [8] The graph-drawing organization and the GraphML format.
• [9] Diagramming for dummies; how to build a diagramming library from scratch. This is the 'Netron Light' control, a simplified version of the full graph library found on the Netron site. The article explains in details the class structure found in this tree control.

---

Author: NetronProject  

Francois *Swa* Vanderseypen is the person behind The Netron Project and can be contacted at Illumineo@users.sourceforge.net. Job: .Net architect in Belgium. Heterogeneous integrations, now more than ten years in the field. Time flies...During working hours I play with IBM Tivoli, SQL Server, mainframes, WebSphere MQ and everything in between. If you have a challenging job for me, drop me a note. Interests: as good as everything, but with a PhD in theoretical physics you can assume I spend a lot of time with mathematical ideas and complexity. Quantum gravity (Loops and knots) in my nostalgic moments. I tend to improvize a lot on my piano and thanks to the blogging phenomenon I write quite a lot of pseudo-philosophical essays.

---