Tree Layout Help

I am having to write my own version of a tree layout, because I am having to lay things out right and left of a centered node in a “tree” fashion. I am stuck on how to do this, as there is a fan out factor as you move both up and down the tree (in other words the position of a node is not just a factor of the previous node, but is a factor of previous, next, adjacent, and adjacent next nodes).

Is there an example of how you do this? Or can anyone help with an algorithm?

Why don’t you use the Tree Layout in our Layout package?

  1. Because I don’t have what I thought was a diagram that would work. I have a central node and then “trees” going out both the right and left side.

  2. Because I have some node specific properties that need to be taken into account (such as the cardinal direction of the port on the node), when laying out the layout.

  3. Because I am doing this totally programmatically.

If you think that I still can, show me how. Your documents are sparse on using your layouts and look like they are more from the non-programmatic standpoint.

OK, try the new DoubleTree sample in version 3.0.

Given the following XML data:

<graph> <node text="root" color="Lavender"> <node dir="1" text="right1" color="Pink"> <node text="leaf1"></node> <node text="leaf2"></node> </node> <node dir="2" text="left1" color="LightBlue"> <node text="leaf3"></node> <node text="leaf4"></node> <node text="left2" color="LightBlue"> <node text="leaf5"></node> <node text="leaf6"></node> </node> </node> <node dir="1" text="right2" color="LightYellow"> <node text="right3" color="LightYellow"> <node text="leaf7"></node> <node text="leaf8"></node> </node> <node text="leaf9"></node> <node text="leaf10"></node> </node> </node> </graph>

It produces the result:

Am I missing something? The sample has no “layout” code in it, it just calls the GoTreeLayout… Also I am not using 3.0 yet. Is there a sample of the actual way you layout the tree?

GoLayoutTree is part of Northwoods.Go.Layout, and is in 2.6 as well.

Ok, where is a good resource for understanding how to use it? They Layout user guide is pretty thin.

All of the meaningful code in that new sample is in the Form1_Load event handler.

The first part of that method loads the document from the XML using a GoXmlBindingTransformer. That’s new for version 3.0. You could implement precisely the same functionality pretty easily by overriding a few GoXmlTransformer methods in version 2.x. There are some examples of this in the samples as well as in the documentation. For version 3.0 many (most?) of the samples have been converted to use the simpler and more declarative GoXmlBindingTransformer, although some remain because of the flexibility that the more general GoXmlTransformer mechanism affords.

The second part of that Form1_Load method actually does the layout. It does two separate tree layouts. This code should work in version 2.5+ as well as in version 3.0.

First it just operates on the root node and all of the nodes and links that are supposed to grow towards the left. Then it just operates on the root node and all of the nodes and links that are supposed to grow towards the right.

Laying out a subset of the nodes and links is done by initializing a GoLayoutTreeNetwork for the whole document and then removing the GoLayoutTreeNodes that are not going in the desired direction. That also automatically removes the GoLayoutTreeLinks that connect to those deleted nodes.

The winnowing is done by the DeleteNetworkChildren method on each of the nodes that is marked by a particular flag. These nodes are the immediate children of the root node. DeleteNetworkChildren recurses through the subtrees from that point, deleting all of those nodes from the GoLayoutTreeNetwork.

Here’s the whole Form1_Load method, for those who are curious but aren’t curious enough to download the ZIP file:

[code] private void Form1_Load(object sender, EventArgs e) {
goView1.UseWaitCursor = true;
GoDocument doc = goView1.Document;

  // load the tree, as nodes and links, from an XML file
  using (Stream stream = typeof(Form1).Assembly.GetManifestResourceStream("DoubleTree.data.xml")) {
    // construct a prototype node
    GoBasicNode protonode = new GoBasicNode();
    protonode.Shape = new GoRoundedRectangle();
    protonode.LabelSpot = GoObject.Middle;
    protonode.Text = "";
    protonode.Label.Multiline = true;

    GoXmlBindingTransformer tr = new GoXmlBindingTransformer("node", protonode);
    tr.AddBinding("text", "Text");
    tr.AddBinding("dir", "UserFlags");
    tr.AddBinding("color", "Shape.BrushColor");

    // construct a prototype link
    tr.TreeStructured = true;  // XML will consist of nested <node>s
    GoLink protolink = new GoLink();
    protolink.ToArrow = true;
    tr.TreeLinkPrototype = protolink;

    GoXmlReader xr = new GoXmlReader();
    xr.AddTransformer(tr);
    xr.RootObject = doc;   // add nodes and links to the view's document
    xr.Consume(stream);
  }
  
  // automatically layout the graph in two directions by doing two layouts,
  // each laying out only the nodes and links in each direction

  // grows towards the left
  GoLayoutTree lay = new GoLayoutTree();
  GoLayoutTreeNetwork net = new GoLayoutTreeNetwork(doc);
  // remove all nodes whose "dir" attribute, now stored in UserFlags, means "lay out rightward"
  // (this will leave the root node)
  foreach (GoObject obj in doc) {
    IGoNode node = obj as IGoNode;
    if (node != null && (node.UserFlags & 1) == 1) DeleteNetworkChildren(node, net);
  }
  lay.Document = doc;
  lay.Network = net;
  lay.Angle = 180;
  lay.SetsPortSpot = false;
  lay.PerformLayout();

  // grows towards the right, but doesn't move the root node positioned by the earlier tree layout
  lay = new GoLayoutTree();
  net = new GoLayoutTreeNetwork(doc);
  // remove all nodes whose "dir" attribute, now stored in UserFlags, means "lay out leftward"
  // (this will leave the root node)
  foreach (GoObject obj in doc) {
    IGoNode node = obj as IGoNode;
    if (node != null && (node.UserFlags & 2) == 2) DeleteNetworkChildren(node, net);
  }
  lay.Document = doc;
  lay.Network = net;
  lay.Angle = 0;
  lay.SetsPortSpot = false;
  lay.Arrangement = GoLayoutTreeArrangement.FixedRoots;
  lay.PerformLayout();

  // make the window fit the graph, which will resize goView1 to fill the client area of the Form
  this.ClientSize = new Size((int)goView1.DocumentSize.Width+10, (int)goView1.DocumentSize.Height+10);
  // make sure there aren't any unnecessary scrollbars,
  // if the GoDocument fits in the GoView at the current GoView.DocScale
  goView1.DocPosition = goView1.DocumentTopLeft;

  goView1.UseWaitCursor = false;
}

// remove PARENT and all of its children, connected by links from the PARENT node to a child node
private void DeleteNetworkChildren(IGoNode parent, GoLayoutTreeNetwork net) {
  if (parent == null) return;
  foreach (IGoNode child in parent.Destinations) {
    DeleteNetworkChildren(child, net);
  }
  net.DeleteNode(parent.GoObject);
}[/code]

Thanks… I had looked at that. I guess I am needing to see how the actual GoLayoutTreeNetwork, figures out the details of positioning nodes so that they are laid out affectively. I am assuming that is secret sauce, but does anyone have any links to non secret sauce algorithms I can use to help me?

You can use the SimpleTreeLayout code in Demo1.

Hi Walter,

Thanks for the excellent example for laying out in two different directions. I'm trying to incorporate into my own solution which requires going in more than two directions and I'm having a bit of trouble. When I took a step back and tried to add two more iterations to your code I found a similar issue:
If you layout either right/left or up/down all is well. However, when I tried to extend your sample by simply adding a third iteration so I could go right/left/up i found that the layout does does behave as expected.
Here's the XML I added:
<node dir="3" text="Three1" color="Pink">
<node text="Threeleaf1"></node>
<node text="Threeleaf2"></node> </node> <node dir="3" text="Three2" color="LightYellow"> <node text="Three3" color="LightYellow"> <node text="Threeleaf7"></node> <node text="Threeleaf8"></node> </node> <node text="Threeleaf9"></node> <node text="Threeleaf10"></node> </node>
And the extra iteration:
foreach (GoObject obj in doc) { IGoNode node = obj as IGoNode; if (node != null && (node.UserFlags & 3) == 3) DeleteNetworkChildren(node, net); } lay.Document = doc; lay.Network = net; lay.Angle = 0; lay.SetsPortSpot = false; lay.Arrangement = GoLayoutTreeArrangement.FixedRoots; lay.PerformLayout();
Which results in this:
Any suggestions?

Consider your code more carefully: in order to do a layout to the left,
for example, the original code deleted those network nodes that were
not supposed to go to the left. If there are multiple non-left
directions in your application, are you removing all of those network
nodes?

If you don’t, you’ll end up doing multiple layouts of the same nodes, in different directions, resulting in, well, a mess.

So you need to change each network pruning code to check like:
if (node != null && node.UserFlags != 2 && node.UserFlags != 0) DeleteNetworkChildren(node, net);

Then when you only have one subtree going upwards:

Even if you set up the GoLayoutTreeNetwork correctly each time, you
still run into the possibility of overlapping nodes, if you have a
bushy tree towards the left and a bushy tree towards the top.

This is with the data you supplied, having two subtrees going upward:

An alternative would be to use GoLayoutForceDirected, in v3.0.
However, that would not cause each subtree to be laid out neatly in one
orthogonal direction.

GoLayoutForceDirected lay = new GoLayoutForceDirected(); lay.Document = doc; lay.DefaultSpringLength = 10f; lay.DefaultElectricalCharge = 75f; lay.PerformLayout();
This gives the result:

Dude - you rock. Thanks for the speedy reply.