|
|
Comments and Discussions
|
|
 |
|
Hello, I really admire your work here, was very interesting.
My question here is ,
Can a child node be reached from more than one parent node.
If you take the TreeContainerTest sample, i want the Node G to be reached from both F & N.
You answer & suggestion will be really helpful.
Also if you can suggest some link for starting on understanding the algorithm behind this, i.e Walkers / Reigngold-Tilford algorithm.
Thanks in advance !.
|
|
|
|
|
|
I was looking for good ways to change the TreeContainer orientation so it could be displayed Vertically instead of horizontally. At first I tried inverting some coordinates in the positioning algorithm but I got really weird behaviors, then I read about WPF rotate, transform capabilities and was able to flip it this way:
Assuming you have defined a TreeContainer like this:
<tc:TreeContainer
HorizontalAlignment="Center"
VerticalAlignment="Center"
x:Name="Tree"
HorizontalBuffer="38"
VerticalBuffer="48"
HorizontalBufferSubtree="40"
VerticalJustification="center"
RenderTransformOrigin="0.5,0.5"/>
You can create a Test method in your main window code-behind:
private void BuildTree()
{
Button btn_Root = new Button();
btn_Root.Content = "ROOT";
TreeNode root = Tree.AddRoot(btn_Root);
for (int i = 0; i < 4; i++)
{
Button btn = new Button();
btn.Content = "Button_l1_" + i;
TreeNode ch1 = Tree.AddNode(btn, btn.Content.ToString(), root);
for (int j = 0; j < 2; j++)
{
Button btn2 = new Button();
btn2.Content = "Button_l2_" + i + "_" + j;
Tree.AddNode(btn2, btn2.Content.ToString(), ch1);
}
}
Tree.RenderTransform = new RotateTransform(-90);
foreach (TreeNode n in Tree.Children)
{
Button btn = n.Content as Button;
btn.LayoutTransform = new RotateTransform(90);
}
}
You will end up with a vertical tree now 
Give it a try.
Ideally the TreeContainer should have a DependencyProperty to define the orientation
and shouldn't be to hard to implement, but for now I think this gets us closer to a good solution.
If someone knows how to achieve the same by modifying the positioning algorithm itself i'd be very interested to know...
modified 15 Oct '12 - 13:35.
|
|
|
|
|
I wanted the TreeContainer control to show horizontal and vertical TreeConnections as in most standard Org Chart diagrams. In order to do that I modified:
Class: LayeredTreeDraw.cs Method: DetermineFinalPositions
The idea: My idea was to add the extra points to the TreeConnection so it was rendered as horizontal and vertical lines in case a given parent node had more than one child node. Fortunately TreeContainer.OnRender method worked fine without changes. It deals with multiple TreeConnection points by default.
Drawback: The only drawback I've found with this approach is that some lines
are drawn on top of each other causing some connections to appear bolder in the overlapped line segments.. Other than that it does what I wanted. If anyone has a solution to this line overlap I'd be very grateful if you could share it.
private void DetermineFinalPositions(ITreeNode tn, int iLayer, double pxFromTop, double pxParentFromLeft)
{
double pxRowHeight = _lstLayerHeight[iLayer];
LayeredTreeInfo lti = Info(tn);
double pxBottom;
DPoint dptOrigin;
lti.pxFromTop = pxFromTop + CalcJustify(tn.TreeHeight, pxRowHeight);
pxBottom = lti.pxFromTop + tn.TreeHeight;
if (pxBottom > PxOverallHeight)
{
PxOverallHeight = pxBottom;
}
lti.pxFromLeft = lti.pxLeftPosRelativeToParent + pxParentFromLeft;
dptOrigin = new DPoint(lti.pxFromLeft + tn.TreeWidth / 2, lti.pxFromTop + tn.TreeHeight);
iLayer++;
TreeNodeGroup tng = GetChildren(tn);
foreach (ITreeNode tnCur in tng)
{
List<DPoint> lstcpt = new List<DPoint>();
LayeredTreeInfo ltiCur = Info(tnCur);
lstcpt.Add(dptOrigin);
DetermineFinalPositions(tnCur, iLayer, pxFromTop + pxRowHeight + _pxBufferVertical, lti.pxFromLeft);
if (tng.Count == 1)
{
lstcpt.Add(new DPoint(ltiCur.pxFromLeft + tnCur.TreeWidth/2, ltiCur.pxFromTop));
_lsttcn.Add(new TreeConnection(tn, tnCur, lstcpt));
}
else
{
double halfHeight = (ltiCur.pxFromTop - dptOrigin.Y)/2;
DPoint p2 = new DPoint(dptOrigin.X, dptOrigin.Y + halfHeight);
lstcpt.Add(p2);
DPoint p3 = new DPoint(ltiCur.pxFromLeft + tnCur.TreeWidth / 2, dptOrigin.Y + halfHeight);
lstcpt.Add(p3);
DPoint p4 = new DPoint(ltiCur.pxFromLeft + tnCur.TreeWidth / 2, ltiCur.pxFromTop +5);
lstcpt.Add(p4);
_lsttcn.Add(new TreeConnection(tn, tnCur, lstcpt));
}
}
}
Update: The issue with the rendering of connection lines has been solved thanks to user @Member 8767345 who shared the one-liner fix. Here his explanation:
"The problem with the drawing of the lines is caused because they are drawn in logical pixels. The antialiasing system spreads the line over multiple pixels if it doesn't align with physical device pixels, making them blurry and sometimes bolder."
This can be fixed by setting the EdgeMode to aliasedt in the TreeContainer.OnRender method:
base.OnRender(dc);
if (Connections != null)
{
RenderOptions.SetEdgeMode(this, EdgeMode.Aliased);
...
When setting that EdgeMode the TreeConnections rendering is now very clean and smooth
Thanks,
Adolfo
modified 27 Sep '12 - 9:00.
|
|
|
|
|
Thanks for sharing this modification - exactly what I needed.
The problem with the drawing of the lines is caused because they are drawn in logical pixels. The antialiasing system spreads the line over multiple pixels if it doesn't align with physical device pixels, making them blurry and sometimes bolder.
This can be fixed by setting the EdgeMode to aliasedt in the TreeContainer.OnRender method:
base.OnRender(dc);
if (Connections != null)
{
RenderOptions.SetEdgeMode(this, EdgeMode.Aliased);
...
|
|
|
|
|
Wow that single line made the difference!!  Node connections look much more cleaner and smoother now.
Thanks so much! I thought the fix was going to be much more elaborated.
Glad you liked my idea.
Cheers,
Adolfo
|
|
|
|
|
Is it possible to use the HierarchyDataTemplate to bind the tree to a business object?
Thanks!
|
|
|
|
|
Hi darrellp, first of all let me say that I really love this code. Before I stumbled on this I was having huge headaches figuring out how to determine the X and Y positions of nodes on a tree.
I am only using your tree layout code and using my own code to draw the nodes with GDI.
When I have just a few items in a few levels on my tree like in your examples, the positions are perfect. However as my tree becomes very large and very wide, your algorithm seems to add occasional extra horizontal space between nodes - sometimes quite a lot of space - for unknown reason. Have you (or anyone else?) seen this behaviour?
If I can't figure this out then I might have to re-write your layout algorithm :(
|
|
|
|
|
I'm embarrassed to admit that I saw the same thing. I figured it out but I honestly wasn't motivated enough to fix it at the time. Unless the tree gets really wide it won't appear, but you're right - if it gets wide enough it can pop up. I'd like to tell you that I'll go back and figure out the details but I'm off on some other stuff so if it happens at all, it's probably going to be a while. If you want to mail me with any questions, I'll try and remember what I can about the code. I don't think it's too awfully bad at least as far as understanding goes. Then again, I'm a biased observer.
|
|
|
|
|
Ahh, ok. I'll take a deeper look at your code and see what I can find.
Incidentally, I downloaded the paper "A Node-positioning Algorithm for General Trees" by John Q. Walker II (1990). It describes a technique for drawing these sorts of trees, and mentions that there are some deficiencies in the Tilford algorithm, though from the description in the paper I don't think it's related to this horizontal spacing bug.
|
|
|
|
|
Oh - and P.S. - I'm glad you're using the library - seems like everybody was using the WPF code, but the library should make it much more applicable to other situations as you're demonstrating (modulo the embarrassing problem you unfortunately brought up!  ).
|
|
|
|
|
Great bit of code and I can appreciate the effort as I tried doing a "simple" tree structure myself.
My question, which I think is different from the previous one on horizontal alignment, is that I would like the nodes to stay in the same position when collapsing and un-collapsing. Put simply, if the root node is centered when everything is not collapsed, it should stay put when they are collapsed. My SilverTreeContainer is being bound to a ContentControl and I have everything set to centre.
Do you have any advice?
|
|
|
|
|
I guess I don't quite understand the question. When you collapse a branch, the definition of "centering" (or at least what I think of as "centering") changes. You could certainly change it to just calculate values as though the entier graph was being drawn and then not draw the collapsed parts. The resulting graph would look out of kilter, but if that's what you're looking for I don't think it's hard. I haven't got the code in front of me but I'm pretty sure that there's an attachable property for whether a node is collapsed or not. Just look up where that property is used and keep the part that avoids drawing the children and eliminate the part which recalculates based on missing children.
Since I'm not 100% sure what you're asking for, I'm not sure whether this answers your question or not.
|
|
|
|
|
Thanks for this Darrell, I will look into it, but if you are not sure you understand it's probably becase I didn't explain it very well.
Imagine a node with two children which is centered in the screen. When I collapse this node, it "jumps" to the left because there is no longer any need to be as wide as it was. I should explain that my SilverTreeContainer is bound to a ContentControl which is itself in a ScrollViewer with everything set to Stretch. I think the easy way to explain this is that I want the top node to be centered at all times.
|
|
|
|
|
Great library, thanks Darrell!
I have the same question and been trying to figure out how and where to change the code for two hours now, but I can't find where "the part that avoids drawing the children" and "the part which recalculates based on missing children" are exactly.
It seems that the Collapsed property of TreeNode leads to the children of the collapsed nodes being ignored everywhere, because LayeredTreeDraw.GetChildren() only returns non-collapsed nodes.
The TreeNode.VisibleDescendants list is used to set the visibility of the collapsed TreeNodes.
If I construct the tree with all nodes, by having LayeredTreeDraw.GetChildren() return all nodes and have LayeredTreeDraw.GetChildren() return all nodes, and only set the collapsed nodes to invisible inside TreeNode.CollapsePropertyChange, the Panel's Measure function will ignore them by setting their DesiredSize to (0,0).
If someone has figured out how to proceed from there, I'd love to hear it.
-- modified 15 Mar '12 - 11:57.
|
|
|
|
|
I'm not sure what changed in 4.0 to cause OnRender to not be called when the control's measure and arrange are being changed, but it breaks my tree control. In 3.5, collapsing a TreeNode caused the parent TreeContainer's measure and arrange to be affected. These, in turn, caused a render of the parent and the connecting lines were drawn in the OnRender() that was called as a result. In 4.0, apparently changing the measure and arrange does not automatically invoke a rerender so my connection lines weren't being redrawn properly. Here's a fix:
In TreeContainer.MeasureOverride() put a call to InvalidateVisual() as the first thing. This is better than my previous fix since it's more general.
This forces the OnRender() function of the parent to be called which draws the connection lines properly. I guess I'll eventually get around to putting this up on CodeProject afresh, but for the moment, this note will have to do.
modified on Friday, April 22, 2011 11:10 AM
|
|
|
|
|
That did the trick! thanks for the fix and thanks for sharing this cool project
|
|
|
|
|
Hi, im getting this InvalidOperationException when i want to use the control; im working in C# with winforms, i use a elementHost to host the tree container, but when i want to add a root i get this:
InvalidOperationException
The NameScope to register the Name '_TreeNode0' was not found
The problem is in your metod SetName:
private void SetName(TreeNode tn, string strName)
{
tn.Name = strName;
RegisterName(strName, tn);
}
In the line RegisterName(strName, tn);
I don´t really know anything about wpf so im not sure what is the problem, i have done this code in base to VisLogTree example you give, this is my code:
TreeContainer.TreeContainer tree = new TreeContainer.TreeContainer();
System.Windows.Controls.Button button = new System.Windows.Controls.Button();
button.Content = "root";
button.Name = "root";
tree.AddRoot(button);
Any kind of help would be great, thanks.
|
|
|
|
|
I believe that the difference is that my TreeContainer is already placed in a window while yours isn't. That window provides a namescope for the names added. If you look at the docs for RegisterName you'll see that "the implementation will check successive parent elements until it finds the applicable NameScope implementation, which is found by finding an element that implements INameScope." Since your TreeContainer has no parent elements, this search is going to fail and you're going to get the error message you wrote about. It makes sense if you stop and think about it. These names aren't just "names" that anybody, anywhere can reference. It's not a "name" in the sense of a variable name in C#. It's a name that, for instance, animations can use to locate items and it has to be done within this context of a namescope which is attached to a container.
It raises an interesting question which I don't think I've ever thought about - perhaps TreeContainer can/should implement INameScope. I'm not 100% sure of the ramifications so I'm hesitant to just jump in and do it, but it bears some thought. It might hinder doing animations, for instance, on the tree nodes.
You can read more here:
http://msdn.microsoft.com/en-us/library/ms746659.aspx[^]
|
|
|
|
|
Is it possible to add text on connectors?
|
|
|
|
|
Not as things stand, but it's only code. Look for the part where the connectors are drawn and add some code to draw text. The main question will be about positioning the text so it's obvious which text belongs to which connector but once you make a decision on that the rest should be pretty easy.
|
|
|
|
|
Hi,
Firstly, it goes without saying, this is a brilliant article and I'm sure you're code is going to help me with my 3rd year University project
But... I've just downloaded the .zip and run the solution in Visual Studio 2010 but there seems to be some problem with the horizontal alignment of nodes - if I debug the solution and click to collapse the root node (labelled StackPanel) the nodes disappear but the vertices persist pointing from/to where the nodes were and the root node aligns itself to the left of the panel.
Just wondering if this is a problem on my machine/VS 2010?
Thanks for reading,
Harri
Note: Just noticed that "TreeContainerTest"'s App.xaml throws a problem message at me when I try to open it saying that there is an undefined CLR namespace in the XAML line xmlns:local="clr-namespace:TreeContainer"
Not sure whether that might have anything to do with it?
modified on Thursday, February 10, 2011 7:20 PM
|
|
|
|
|
Hmm...
I really don't know what the problem is. If I was there, I could probably figure it out but long distance debugging through email is pretty tough. It kinda sounds like your screen isn't refreshing properly.
The error message you're getting says it can't find the TreeContainer library when it's trying to parse your XAML. That could mean that it wasn't built properly or that it can't find it in the place it expects.
I just can't say too much at this distance. If you've got somebody else who knows something about CLR there, maybe they can take a look.
Darrell
|
|
|
|
|
Hi,
I'm having the same problem it works fine until i resize the control/window then for whatever reason when the Collapsed property is changed it doesn't re-render the control.. just does measure and arrange.
The quick and dirty way around this is to invalidate the treecontainer which will force a re-render but its not nice..
I'm gonna dig around a bit and let you know if I can find out whats happening.
Excellent article btw well written and very useful
|
|
|
|
|
That would be great! I'd love to help, but everything is working fine up here so it's pretty tough to solve a problem you can't see. I'm guessing some sort of odd difference in the specific hardware you're using though WPF should work the same on all hardware. I assume the silverlight version on my website works okay for you? I think I mention the website in the article, but here's a link:
http://www.darrellplank.com/Experiments/Silverlight/SilverTreeTest/SilverTreeTest.html
|
|
|
|
|
yeah that works haven't had time to investgate the problem in WPF yet but I've noticed that it only happens when I resize the panel above a certain threshold. Typically if there are only a few nodes and and a large panel so lots of empty space, after the panel is resized for whatever reason it will no longer re-render when the Collapsed property is changed.
|
|
|
|
|
About all I can tell you is that the "WPF" portion of it is really a pretty thin shell over all the arranging machinery underneath and you could probably throw it away and write it again from scratch without that much trouble. After all, all you need in WPF is somebody to tell you where to put things. After that, there's not that much to do - just put them there which is what the small shell I wrote does. You could scrap the XAML part and the custom control part and just call the arranging assembly directly from inside your code - if nothing else just for testing purposes. It should be really simple to do.
|
|
|
|
|
yeah sure was just checking you hadn't identified this problem.. looks like a WPF 'feature' to me probably to do with how dependencyproperty metadata is managed internally, seeing as though this defines the behaviour when the value is changed.. or it could just be that I've not read enough.. if I do get time to look into it I will, for now its not a biggy.
|
|
|
|
|
|
See my "IMPORTANT" comment for a fix.
|
|
|
|
|
Okay, I'm seeing the problem. For some reason, OnRender (where the connection lines are drawn) is not being called when a collapse occurred. This used to happen in 3.0 so something has changed under the hood. I have the collapse property's metadata say that it affects the parent's measure and arrange and you'd think that if their measure and arrange changed they'd have to rerender and apparently they did under 3.5 but not under 4.0. I'm not sure why this is. There's no "AffectsParentRender" metadata type so I'll have to look into this. Aargh!
|
|
|
|
|
Okay, I'm not sure why things changed, but here's a fix. In TreeNode.CollapsePropertyChanged() put the following lines at the end of the if block:
TreeContainer tc = tn.Parent as TreeContainer;
if (tc != null)
{
tc.InvalidateVisual();
}
This forces the OnRender() function of the parent to be called which draws the connection lines properly. I guess I'll eventually get around to putting this up on CodeProject afresh.
|
|
|
|
|
This article is a great starting place for showing how to employ a layout algorithm with WPF.
Thanks.
|
|
|
|
|
|
Hello,
I was wonderring if there is any documentation or unit tests.
Regards.
|
|
|
|
|
The CodeProject page and the sources are the documentation. I don't remember whether I put in unit tests or not. Look at the source code and find out.
|
|
|
|
|
I am using Windows Forms. Do you have any insight as to how I might implement a Graph Tree using Windows Forms and C#?
Sincerely Yours,
Brian Hart
|
|
|
|
|
I'd just use the underlying library and tell it how big each node is and how they're connected. It will tell you where to place each node. I think it tells you where to draw the connecting lines also but it's been a long time since I wrote this. Draw your nodes on a sizing panel, make it the right size and you should be good to go. Of course it's your responsibility to determine the size of your nodes and draw them since I don't know anything about them, but that's the easy part. The hard part is arranging the which the library function here provides.
|
|
|
|
|
I'm trying to see how this could be adapted to use WPF binding to bind to a hierarchical view model in the same way that the tree view does instead of having to manually create the structure in code. How easy/hard would this be?
|
|
|
|
|
Well, you can build it in Xaml - doesn't have to be in code. I know that doesn't help much in MVVM - at least not if it's dynamic. I don't really know about databinding on a custom control. I've never done it and can't really say I know much about it off the top of my head. If you do know something about it then you're a much better person to answer your own question than I am I'm afraid. Might be a fun project to dig into sometime, though. Sorry I'm of no help here. The control itself is pretty simple so if you know something about it, I doubt it would be too awfully difficult. Really, the article is more about the algorithm than about the particular implementation in WPF which is a fairly thin layer.
|
|
|
|
|
Hi Darrel,
Can I have cycles in your graph control?
Thank you
who dares wins!
|
|
|
|
|
Sorry - strictly works with trees.
|
|
|
|
|
hello darrell,
your graph tree is vertical(top to bottom), but my need is to draw horizontal tree(left to right)
i tried some ways but didn't get the proper solution can u help me???????
one more thing that i want is, to add my icons in the node???
i m drawing rectangle instead of UI Element and need to draw icon in it..
how to do that????
Raj
|
|
|
|
|
Dear darrellp
Kindly please
Do you have any Graph Tree connect to Database like family tree in Silverlight?
Please share it with us
many thanks
|
|
|
|
|
Hi Darrell,
Not to be too picky, but this looks like Walker's algorithm (A node-positioning algorithm for general trees, p 685-705, John Q. Walker II, Software: Practice and Experience, July 1990), not the Reingold/Tilford algorithm (Tidier Drawings of Trees
Reingold, E.M.; Tilford, J.S.; IEEE Transactions on Software Engineering, Volume SE-7, Issue 2, March 1981 Page(s):223 - 228). In your description, the link you gave points to an article in DDJ written by Walker himself.
Also, you might want to check out the newer algorithm by Buchheim et al. (Drawing rooted trees in linear time, p 651-665, Christoph Buchheim, Michael Jünger, Sebastian Leipert, Software: Practice and Experience, May 2006). It's better organized (especially in how it computes the left and right contours used in determining shift distances), and you can adapt it more easily to other tree layouts, including something that works like an RT layout for general trees.
Ken Domino
|
|
|
|
|
Hey - thanks for the info! You're absolutely right - I did implement Walker's algorithm - guess I just wasn't clear in my own head on where the distinction lay. The article you mention does a MUCH better job of describing stuff than the one by Walker in my opinion, even when summarizing the various historical algorithms. I never saw mention of the "threads" in any of the original articles but realized that they were necessary so just implemented it that way on my own. It seemed to me that many of the details such as this were "swept under the rug" in those original articles. Buchheim's article calls them out directly.
Anyway, I'm looking at his article and will consider altering the algorithm. I'm in the process of fixing some stuff up and consolidating my Silverlight version with the normal WPF version so will be making a revision soon anyway. At the very least, I'll change the name in the text to Walker. I'll have to see how many complications Buchheim introduces (haven't gotten through the entire article yet). Regardless, I much prefer the newer article to the old ones I had been looking at.
Thanks again!
Darrell
|
|
|
|
|
I've been reading Buchheim's paper sporadically and I think I essentially have an equivalent solution. His optimization is to avoid having to calculate which two immediate child nodes we have to spread out nodes evenly between when we come to a conflict at a lower level. He seems to be doing it by keeping pointers in the child nodes. I keep an array of which child node is the ancestor node for every node in the right contour generated thus far. Since the right contour is just one node per maximum level in any of our child subtree forest, this is just an array of one index for a responsible child node for ever level of the child forest. When I have a conflict on level N, I just look up level N in the array and I know immediately which child node we have to space between. I don't think I ever fully grokked Walker's given algorithms (perhaps because I never read Tilford's original paper which I take it now, introduced a lot of the terminology Walker tacitly assumes such as modifiers) so I mainly went by his careful walkthrough and I think in that walkthrough, he glosses over all this by saying something like "space children c through e equally". I had to figure out on my own how he might come up with "c through e" and I think this is how I did it and just assumed that he had done something similar. Keeping track of this array is linear since each node at most changes one element of this array one time. This solves the problem of finding the ancestor nodes which is by far the bulk of the non-linearity I think since it must be done whenever there is a conflict and is really time consuming to calculate. The other thing the Buchheim does is to avoid shifting trees more than once but this seems like a real corner case where successive children have to have larger subtrees at increasing levels - you have to kind of stand on your head to get this to happen at all. I may do it, but I think it would require a bit more of a change than I'm ready to put in for such a rare case. Thanks for the article, regardless. It really helped me understand some things I didn't really know before.
Darrell
|
|
|
|
|
Hello,
Got a link or a way to read Buchheim's article?
|
|
|
|
|
The article is:
Buchheim, C., Junger, M. and Leipert, S. Drawing rooted trees in linear time.
SOFTWARE PRACTICE AND EXPERIENCE, 36, 6 2006), 651.
http://www3.interscience.wiley.com/journal/112418290/abstract[^]
There is a minor typo in the algorithm, but it works. I have an implementation in C# if you are interested. The algorithm may be difficult to understand without the paper, and it assume that you understand Walker's algorithm, including the meaning of Prelim, Modifier, and Thread attributes, contours and nearest common ancestors. The layout is exactly the same between Buchheim and Walker.
|
|
|
|
|
Hi Darrell,
This looks great. I did something similar by subclassing a standard WPF treeview control and applying a new control template here: http://wpfblog.info/2008/05/27/wpf-treeview-org-chart-a-bit-of-refactoring/[^]
If feels like you're doing the same thing albeit with a bit more complexity. Is that the case or am I missing some great benefit of your technique that could enhance my own?
Great article either way and a very clever implementation!
Regards,
Roland
|
|
|
|
|
|
|
 General  News  Suggestion  Question  Bug  Answer  Joke  Rant  Admin
|
This article describes and implements a graph drawing control for tree structures structured in a WPF panel.
| Type | Article |
| Licence | CPOL |
| First Posted | 20 Sep 2008 |
| Views | 108,070 |
| Downloads | 3,493 |
| Bookmarked | 119 times |
|
|
Submit an article or tip
Post your Blog
