Puu visualiseerimine

Kuna olen juba infograafika lainel, siis siin on täiesti erakordne õpetus, kuidas puud joonistada Walkeri algoritmiga. Koos koodinäidetega!

Üks asi, mis siin silma torkab on liigne OO kasutamine, mis tundub täiesti pöörane. Aga samas on kood väga modulaarne ja arusaadav.

Walkeri algoritm on hea näiteks decision treede visualiseerimiseks, millest veits juttu siin Klassifikatsioon.

Olemasolevad teegid ei ole nii paindlikud, et neid oma suva järgi muuta,  kuigi GraphViz jt. on päris ilusad.

Selle koodiga saad ainult x ja y väärtused igale puu osale, ise võid jooned tõmmata selliselt nagu tahad, ise võid kirjutada juurde, mida tahad… palju kasutatavam.

Kasutusjuhend on selline:


WalkersTree tree = new WalkersTree("1");
WalkersTree tree2 = new WalkersTree("2");
WalkersTree tree3 = new WalkersTree("3");
WalkersTree tree4 = new WalkersTree("4");
WalkersTree tree5 = new WalkersTree("5");
WalkersTree tree6 = new WalkersTree("6");
WalkersTree tree7 = new WalkersTree("7");
WalkersTree tree8 = new WalkersTree("8");
WalkersTree tree9 = new WalkersTree("9");
WalkersTree tree10 = new WalkersTree("10");
root = new WalkersTree("0");
root.AttachSubtree(tree);
root.AttachSubtree(tree2);
root.AttachSubtree(tree3);
tree.AttachSubtree(tree4);
tree.AttachSubtree(tree5);
tree3.AttachSubtree(tree6);
tree3.AttachSubtree(tree7);
tree6.AttachSubtree(tree8);
tree6.AttachSubtree(tree9);
tree6.AttachSubtree(tree10);

Walker walker = new Walker();
walker.TreeLayout(root);

//drawing pseudocode in .net gdi
Stack<WalkersTree> stack = new Stack<WalkersTree>();
stack.Push(root);
while (stack.Count > 0)
{
WalkersTree t1 = stack.Pop();
g.DrawString(t1.Key.ToString(), new Font(FontFamily.GenericSerif, 10f), Brushes.Red, new PointF((float)t1.X, (float)t1.Y));
if (t1.Degree != 0)
{
for (int i = 0; i < t1.Degree; i++)
{
stack.Push((WalkersTree)t1.GetSubtree(i));
g.DrawLine(Pens.Red, new PointF((float)t1.X, (float)t1.Y), new PointF((float)((WalkersTree)t1.GetSubtree(i)).X, (float)((WalkersTree)t1.GetSubtree(i)).Y));
}
}
}


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using FreeLib;

namespace Visualization
{
    public class Walker
    {
        private WalkersTree default_ancestor;
        //this is the distance
        double distance = 100;
        // temp------------- this is because the coordinates are -inf to +inf, so if you add this variable in function SecondWalk, you get positive coordinates.
        //otherwise set it to 0 or calculate width of the tree by traversing X values
        double start = 400; 
        public void TreeLayout(WalkersTree tree)
        {
            FirstWalk(tree);
            SecondWalk(tree, -(tree.Prelim));
        }
        private void FirstWalk(WalkersTree tree)
        {
            if (tree.IsLeaf)
            {
                tree.Prelim = 0;
                if (tree.LeftSibling != null)
                {
                    tree.Prelim = tree.LeftSibling.Prelim + distance;
                }
            }
            else
            {
                default_ancestor = (WalkersTree)tree.LeftmostChild;
                for (int i = 0; i < tree.Degree; ++i)
                {
                    FirstWalk((WalkersTree)tree.GetSubtree(i));
                    Apportion((WalkersTree)tree.GetSubtree(i), default_ancestor);
                }
                ExecuteShifts(tree);
                double r_prelim = tree.RightmostChild.Prelim;
                double l_prelim = tree.LeftmostChild.Prelim;
                double midpoint = 0.5 * (l_prelim + r_prelim);
                if (tree.LeftSibling != null)
                {
                    tree.Prelim = tree.LeftSibling.Prelim + distance;
                    tree.Mod = tree.Prelim - midpoint;
                }
                else
                    tree.Prelim = midpoint;
            }
        }
        
        private void SecondWalk(WalkersTree tree, double prelim)
        {
            tree.X = tree.Prelim + prelim + start;
            tree.Y = tree.Height * distance;
            for (int i = 0; i < tree.Degree; ++i )             {                 SecondWalk((WalkersTree)tree.GetSubtree(i), prelim + tree.Mod);             }         }         private void Apportion(WalkersTree tree, WalkersTree defaultAncestor)         {             double sileft = 0;             double siright = 0;             double soleft = 0;             double soright = 0;             if (tree.LeftSibling != null)             {                 tree.InsideRight = tree;                 tree.OutsideRight = tree;                 tree.InsideLeft = tree.LeftSibling;                 tree.OutsideLeft = tree.InsideRight.LeftmostSibling();                 siright = tree.InsideRight.Mod;                 soright = tree.OutsideRight.Mod;                 sileft = tree.InsideLeft.Mod;                 soleft = tree.OutsideLeft.Mod;                 while (null != NextRight(tree.InsideLeft) && null != NextLeft(tree.InsideRight))                 {                     WalkersTree il = tree.InsideLeft;                     WalkersTree ir = tree.InsideRight;                     tree.InsideLeft = NextRight(tree.InsideLeft);                     tree.InsideRight = NextLeft(tree.InsideRight);                                          tree.OutsideLeft = NextLeft(tree.OutsideLeft);                     tree.OutsideRight = NextRight(tree.OutsideRight);                     tree.OutsideRight.Ancestor = tree;                     double shift = (tree.InsideLeft.Prelim + sileft) - (tree.InsideRight.Prelim + siright) + distance;                     if (shift > 0)
                    {
                        MoveSubtree(Ancestor(tree.InsideLeft, tree, default_ancestor), tree, shift);
                        siright += shift;
                        soright += shift;
                    }
                    sileft += tree.InsideLeft.Mod;
                    siright += tree.InsideRight.Mod;
                    soleft += tree.OutsideLeft.Mod;
                    soright += tree.OutsideRight.Mod;
                }
            }
            if (null != NextRight(tree.InsideLeft) && null == NextRight(tree.OutsideRight))
            {
                tree.OutsideRight.Thread = NextRight(tree.InsideLeft);
                tree.OutsideRight.Mod += sileft - soright;
            }
            if (null != NextLeft(tree.InsideRight) && null == NextLeft(tree.OutsideLeft))
            {
                tree.OutsideLeft.Thread = NextLeft(tree.InsideRight);
                tree.OutsideLeft.Mod += siright - soleft;
                default_ancestor = tree;
            }
        }
        private WalkersTree NextLeft(WalkersTree tree)
        {
            if (tree == null)
                return null;
            if (tree.LeftmostChild != null)
                return tree.LeftmostChild;
            else
                return tree.Thread;
        }
        private WalkersTree NextRight(WalkersTree tree)
        {
            if (tree == null)
                return null;
            if (tree.RightmostChild != null)
                return tree.RightmostChild;
            else
                return tree.Thread;
        }
        private void ExecuteShifts(WalkersTree tree)
        {
            double shift = 0.0;
            double change = 0.0;
            for (int i = tree.Degree - 1; i >= 0; i--)
            {
                WalkersTree w = (WalkersTree)tree.GetSubtree(i);
                if (shift > 0.0 || shift < 0.0)                 {                           //somehow w.Prelim += 0.0; equals NaN                     w.Prelim += shift;                     w.Mod += shift;                 }                 change += w.Change;                 shift += w.Shift + change;             }         }         private void MoveSubtree(WalkersTree minus, WalkersTree plus, double shift)         {             int subtrees = plus.Number - minus.Number;      //"number" is not degree             //System.Diagnostics.Debug.Assert(subtrees >= 0, "subtrees is zero or less:" + subtrees.ToString());
            if (subtrees != 0)
            {
                plus.Change = plus.Change - shift / subtrees;
                minus.Change = minus.Change + shift / subtrees;
            }
            plus.Shift = plus.Shift + shift;
            
            plus.Prelim = plus.Prelim + shift;
            plus.Mod = plus.Mod + shift;
        }
        WalkersTree Ancestor(WalkersTree treeInnerLeft, WalkersTree tree, WalkersTree defaultAncestor)
        {
            if (tree.IsSibling(treeInnerLeft.Ancestor))
                return treeInnerLeft.Ancestor;
            else
                return defaultAncestor;
        }

    }
}

Lisaks veel selline klass puu jaoks.


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using FreeLib;

namespace Visualization
{
    public class WalkersTree: GeneralTree
    {
        public WalkersTree(object key)
            : base(key)
        {
            mod = 0;
            shift = 0;
            change = 0;
            thread = null;
            this.ancestor = this;
            x = 0;
            y = 0;
            parent = null;
        }
        private double mod;
        private WalkersTree thread;
        private WalkersTree ancestor;
        private double prelim;
        double shift;
        double change;
        double y;
        double x;
        WalkersTree parent;
        WalkersTree leftSibling = null;
        WalkersTree ileft = null;
        WalkersTree iright = null;
        WalkersTree oleft = null;
        WalkersTree oright = null;

        public double X
        {
            get { return x; }
            set { x = value; }
        }
        public double Y
        {
            get { return y; }
            set { y = value; }
        }
        public double Shift
        {
            get { return shift; }
            set { shift = value; }
        }
        public double Change
        {
            get { return change; }
            set { change = value; }
        }
        public double Prelim
        {
            get { return prelim; }
            set
            {
                if (Double.IsNaN(value))
                    throw new ArgumentOutOfRangeException("Prelim is NaN");
                prelim = value;
            }
        }
        public double Mod
        {
            get { return mod; }
            set { mod = value; }
        }
        public WalkersTree Thread
        {
            get { return thread; }
            set { thread = value; }
        }
        public WalkersTree Ancestor
        {
            get { return ancestor; }
            set { ancestor = value; }
        }
        public WalkersTree InsideLeft
        {
            get { return ileft; }
            set { ileft = value; }
        }
        public WalkersTree InsideRight
        {
            get { return iright; }
            set { iright = value; }
        }
        public WalkersTree OutsideLeft
        {
            get { return oleft; }
            set { oleft = value; }
        }
        public WalkersTree OutsideRight
        {
            get { return oright; }
            set { oright = value; }
        }
        public void AttachSubtree(WalkersTree tree)
        {
            tree.parent = this;
            if (this.Degree > 0)
                tree.leftSibling = (WalkersTree)this.list.Last.Value;
            base.AttachSubtree(tree);
        }
        public void DetachSubtree(WalkersTree tree)
        {
            base.DetachSubtree(tree);
            tree.parent = null;
            //code for siblings
        }
        public WalkersTree LeftSibling
        {
            get { return leftSibling; }
        }
        public WalkersTree LeftmostSibling()
        {
            if (parent == null)
                return null;
            if (parent.Degree == 0)
                return null;
            return parent.LeftmostChild;
        }
        public WalkersTree LeftmostChild
        {
            get
            {
                if (Degree == 0)
                    return null;
                else
                    return (WalkersTree)list.First.Value;
            }
        }
        public WalkersTree RightmostChild
        {
            get
            {
                if (Degree < 1)     //<2 makes sense
                    return null;
                else
                    return (WalkersTree)list.Last.Value;
            }
        }
        public bool IsSibling(WalkersTree tree)
        {
            if (tree == this)
                return false;
            if (this.parent == null)
                return false;
            if (parent.list.Count == 0)
                return false;
            for (int i = 0; i < parent.list.Count; ++i)
            {
                if (((WalkersTree)parent.GetSubtree(i)) == tree)
                    return true;
            }
            return false;
        }
        double GetHeight()
        {
            WalkersTree parent2 = this.parent;
            double height = 0;
            while (parent2 != null)
            {
                ++height;
                parent2 = parent2.parent;
            }
            return height;
        }
        public new double Height
        {
            get
            {
                return GetHeight();
            }
        }
        public int Number
        {
            get
            {
                return GetNumber();         // should store a number for runtime speedup
            }
        }
        int GetNumber()
        {
            if (this.parent == null)
                return -1;
            for (int i = 0; i < this.parent.Degree; ++i)
            {
                WalkersTree t = (WalkersTree)this.parent.GetSubtree(i);
                if (t == this)
                    return i;
            }
            return -1;
        }
    }
}

Ja arusaadavalt veel 10 klassi OO-d, mida kõike ei postita.

using System;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Linq;
using System.Text;

namespace FreeLib
{
    public class GeneralTree : AbstractTree
    {
        protected object key;
        protected int degree;
        protected LinkedList<object> list;
        public override bool IsEmpty
        {
            get
            {
                return key == null;
            }
        }
        public GeneralTree(object key)
        {
            this.key = key;
            degree = 0;
            list = new LinkedList<object>();
        }

        public override void Purge()
        {
            list.Clear();
            degree = 0;
        }

        public override object Key
        { 
            get { return key; }
            set { key = value; }
        }

        public override Tree GetSubtree(int i)
        {
            if (i < 0 || i >= degree)
                throw new IndexOutOfRangeException();
            LinkedListNode<object> ptr = list.First;
            for (int j = 0; j < i; ++j)
                ptr = ptr.Next;
            return (GeneralTree)ptr.Value;
        }

        public void AttachSubtree(GeneralTree t)
        {
            list.AddLast(t);
            ++degree;
        }

        public void DetachSubtree(GeneralTree t)
        {
            list.Remove(t);
            --degree;
        }

        // ...

        public override bool IsLeaf
        {
            get { return this.degree == 0 ? true: false; }
        }

        public override int Degree
        {
            get { return degree; }
        }

        public override int Height
        {
            get { throw new NotImplementedException(); }
        }

        public override int CompareTo(object obj)
        {
            return this.Equals(obj) == true ? 0 : -1;
        }
        
    }
}

Advertisements