Tuesday, October 23, 2012

Adjacency (Sunburst) Diagram in C#

I am currently in the process of developing a special custom outliner program to help me design other big projects I'll get involved with in the future. (Check it out here!) I finished the basic outliner view and all under-the-hood functionality, but now to enhance it (add more tools and features) before I polish it off and share it with the world. The first idea that popped into my head was a data visualizer tool - specifically the node-link diagrams that used the Reingold-Tilford algorithm. I toured the sites and images online so that I wouldn't wast time 're-inventing the wheel' and along the way discovered many more diagrams that I have never seen or even heard of before - take A Tour Through the Visualization Zoo if you want to get clue of what you could do with specific types of data. ( "OO" XD ). Never the less, I actually wasted more time searching than I could have 're-inventing that wheel', but I did find a possible solution for one type of diagram here. (I'll maybe implement that later after parsing from WPF to WinForms)

Long Story Short
I was searching for an algorithm for hierarchy node-link diagram, learned about other was to display the same data, choose the 'Sunburst' diagram as my new primary choice, and never found a hint or clue of algorithmic code for it. This is what it looks like (without words):



To The CODE!

So, first I create an object that would store the drawing data:
public class TreeNodeEx : TreeNode
{
    public float Radius { get; set; }
    public float Scale { get; set;  }
    public float StartAngle { get; set; }
    public float SweepAngle { get; set; }

    public TreeNodeEx(String text)
        : base(text)
    {
        Radius = 0;
        Scale = StartAngle = SweepAngle = 0;
    }
}
Next, the actual sunburst generator!
// This is the entry point of the sunburst algorithm
private void GenerateStructures(TreeNodeEx rTNH)
{
    rTNH.Radius = 1;
    rTNH.SweepAngle = 360;
    tree_depth = Round1(rTNH);
    Round2(rTNH);
}
private int Round1(TreeNodeEx rootx)
{
    // traverse to the bottom while setting depth and breadth
    TreeNodeEx current;

    if(rootx == null) return 0; 

    current = (TreeNodeEx)rootx.Nodes[0];
    bool next_flag = false;
    int depth = 2, max = 0;
    while (current.Parent != null) // have we reached the root yet
    {
        if(current.Nodes.Count == 0 || next_flag)
        {
            if(!next_flag) current.Scale = 1; // count it's self
            ((TreeNodeEx)current.Parent).Scale += current.Scale;
            next_flag = false; // reset
            current.Radius = depth;

            int idx = current.Parent.Nodes.IndexOf(current);
            idx++; // get next sibling in line
            if (current.Parent.Nodes.Count == idx)
            {
                // move to next parant
                next_flag = true;
                current = (TreeNodeEx)current.Parent;
                current.Scale++; // count parent
                depth--;
            }
            else
            {
                current = (TreeNodeEx)current.Parent.Nodes[idx];
            }
        }
        else
        {
            // traverse to the bottom of the tree
            current = (TreeNodeEx)current.Nodes[0];
            depth++;
            max = Math.Max(max, depth);
        }
    }
    return max; // return max depth - used for precise rendering
}
private void Round2(TreeNodeEx rootx)
{
    // traverse to the bottom while setting depth and breadth
    TreeNodeEx current;

    if (rootx == null) return;
    current = (TreeNodeEx)rootx.Nodes[0];
    bool next_flag = false;
    while (current.Parent != null) // have we reached the root yet
    {
        if (current.Nodes.Count == 0 || next_flag)
        {
            if (current.PrevNode != null)
            {
                current.StartAngle = 
                    ((TreeNodeEx)current.PrevNode).StartAngle +
                    ((TreeNodeEx)current.PrevNode).SweepAngle;
                current.SweepAngle =
                    (current.Scale /
                    (((TreeNodeEx)current.Parent).Scale - 1F)) *
                    ((TreeNodeEx)current.Parent).SweepAngle;
            }
            else
            {
                current.StartAngle =
                    ((TreeNodeEx)current.Parent).StartAngle;
                current.SweepAngle =
                    (current.Scale /
                    (((TreeNodeEx)current.Parent).Scale - 1F)) *
                    ((TreeNodeEx)current.Parent).SweepAngle;
            }

            next_flag = false; // reset

            int idx = current.Parent.Nodes.IndexOf(current);
            idx++; // get next sibling in line
            if (current.Parent.Nodes.Count == idx)
            {
                // move to next parant
                next_flag = true;
                current = (TreeNodeEx)current.Parent;
            }
            else
            {
                current = (TreeNodeEx)current.Parent.Nodes[idx];
            }
        }
        else
        {
            if (current.PrevNode != null)
            {
                current.StartAngle =
                    ((TreeNodeEx)current.PrevNode).StartAngle +
                    ((TreeNodeEx)current.PrevNode).SweepAngle;
                current.SweepAngle =
                    (current.Scale /
                    (((TreeNodeEx)current.Parent).Scale - 1F)) *
                    ((TreeNodeEx)current.Parent).SweepAngle;
            }
            else
            {
                current.StartAngle =
                    ((TreeNodeEx)current.Parent).StartAngle;
                current.SweepAngle =
                    (current.Scale /
                    (((TreeNodeEx)current.Parent).Scale-1F)) *
                    ((TreeNodeEx)current.Parent).SweepAngle;
            }

            // traverse to the bottom of the tree
            current = (TreeNodeEx)current.Nodes[0];
        }
    }
}

I didn't include the drawing code portion because this is just an algorithmic post and not an application post.  After all, shapes can be presented, colored, or drawn in many ways with many graphics libraries... and also I feel mine may be a little bit messy or too complex for such a simple task here. However, if you'd like to see how I did it, please leave a comment and I'll try to get back to you!
EDIT: Rewrote the above code without recursion as sometimes trees can grow very deep and there is only a limited amount of stack space available on a machine. Also made a few bug fixes along the way such as the 'overlapping rendering' - a result of a logic error in the variable generation. The above code can still be further improved, but compared to the previous this is an improvement!

Here Are MY Results:
I did it all in WinForms using custom control designs.


HAVE FUN!

No comments:

Post a Comment