Hi. I have an issue with tree layouts when there are lots of nodes (in the 80s for example). Often the result is that nodes are spaced quite far apart from each other, leaving lots of blank space in the diagram.

The code for setting up the layout is like this:

Dim tl As New TreeLayout()
tl.Direction = TreeLayoutDirections.TopToBottom
tl.LinkStyle = TreeLayoutLinkType.Cascading3
tl.Type = TreeLayoutType.Centered
tl.Root = rootDiagramNode
tl.IgnoreLinkDirection = True
tl.LevelDistance = 10
tl.NodeDistance = 5


I guess I could do the layout and then re-position items in my code, but this seems pretty cumbersome.


Here is the image:

[img]http://legacyforward.com/treelayout.jpg[/img]

Thanks for your help!

It is true that there are cycles in the graph, so it is not a true tree. I do specify a root node for the layout, as you can see in the code. Are you saying that the TreeLayout can't be made to work for cyclic graphs? Actually I do get something tree-like (i.e. hierarchical) appearing, and it generally works ok for me, but as I said the spacing is often unwieldy. Any ideas of how to alleviate the spacing in situations where nodes can have more than one incoming link?

Ah. I understand. Thanks for the explanation. Nevertheless, the tree does seem to work pretty well as a layout, even when there are a few cycles in the graph. And it has the advantage of showing the designated root node at the top of the hierarchy, and giving a hierarchical arrangement of nodes. It's just that it results in a lot of wasted space on the display. Would you have any suggestions on how to resolve this? Does it require, as I had speculated earlier, that I programmatically shift positions of individual nodes after the layout has been applied? Or are there any TreeLayout properties I could set or methods I could call to address the spacing issues within the layout algorithm itself?

Try the following solution.

1. Define a function, which creates a spanning tree from a source diagram by setting IgnoreLayout of some of the links to true. The function accept as arguments the source diagram and the node that should be used as root, and returns a list with all ignored links.

Private Shared Function MakeTree(ByVal diagram As Diagram, ByVal root As DiagramNode) As List(Of DiagramLink)

      Dim ignoredLinks As New List(Of DiagramLink)()

      Dim visited As New Dictionary(Of DiagramNode, DiagramNode)()
      Dim visitedLinks As New Dictionary(Of DiagramLink, DiagramLink)()
      Dim remaining As New Queue(Of DiagramNode)()
      visited.Add(root, root)
      remaining.Enqueue(root)

      root.Tag = 0

      While (remaining.Count > 0)

            Dim [next] = remaining.Dequeue()
            Dim allLinks As New List(Of DiagramLink)()
            For Each link As DiagramLink In [next].OutgoingLinks
                  allLinks.Add(link)
            Next link
            For Each link As DiagramLink In [next].IncomingLinks
                  allLinks.Add(link)
            Next link

            For Each link As DiagramLink In allLinks


                  If (visitedLinks.ContainsKey(link)) Then
                        Continue For
                  End If

                  Dim destination = IIf(link.Destination Is [next], link.Origin, link.Destination)
                  If (visited.ContainsKey(destination)) Then

                        link.IgnoreLayout = True
                        ignoredLinks.Add(link)
                        Continue For

                  End If

                  visited.Add(destination, destination)
                  visitedLinks.Add(link, link)
                  remaining.Enqueue(destination)

                  Dim origin = [next]
                  destination.Tag = CInt(origin.Tag) + 1

            Next link

      End While

      Return ignoredLinks

End Function 

2. Perform the layout on the diagram. The links with IgnoreLayout = true will automatically be ignored. After the layout has run, manually set the points of the ignored links.

Public Sub LayoutTree(ByVal diagram As Diagram, ByVal root As DiagramNode)

      If (diagram.Nodes.Count = 0) Then
            Return
      End If

      Dim ignoredLinks = MakeTree(diagram, root)

      Dim l As New TreeLayout()
      l.Direction = TreeLayoutDirections.TopToBottom
      l.LinkStyle = TreeLayoutLinkType.Cascading3
      l.Type = TreeLayoutType.Centered
      l.Root = root
      l.IgnoreLinkDirection = True
      l.LevelDistance = 10
      l.NodeDistance = 5

      l.Arrange(diagram)

      ' Manually arrange the ignored links
      For Each link As DiagramLink In ignoredLinks

            Dim origin As DiagramNode = Nothing
            Dim destination As DiagramNode = Nothing
            If (CInt(link.Origin.Tag) < CInt(link.Destination.Tag)) Then

                  origin = link.Origin
                  destination = link.Destination

            Else

                  destination = link.Origin
                  origin = link.Destination

            End If

            Dim originBounds = origin.Bounds
            Dim destinationBounds = destination.Bounds
            Dim distance = destinationBounds.Top - originBounds.Bottom

            link.SegmentCount = 3
            link.ControlPoints(0) = New PointF(originBounds.Left + originBounds.Width / 2, originBounds.Bottom)
            link.ControlPoints(1) = New PointF(originBounds.Left + originBounds.Width / 2, originBounds.Bottom + distance / 2)
            link.ControlPoints(2) = New PointF(destinationBounds.Left + destinationBounds.Width / 2, destinationBounds.Top - distance / 2)
            link.ControlPoints(3) = New PointF(destinationBounds.Left + destinationBounds.Width / 2, destinationBounds.Top)
            link.UpdateFromPoints()

      Next link

End Sub 

Regards,
Meppy

Thanks Meppy, that worked well. I set the links of the cycle (detected in your MakeTree function) to ignoreLayout and also Visible=false, and it makes a big improvement in the displayed tree. Thanks!