Recent

Author Topic: TTree depth-first traversal  (Read 2105 times)

Anonimista

  • New Member
  • *
  • Posts: 19
TTree depth-first traversal
« on: September 21, 2019, 08:00:40 pm »
I am trying to do a depth-first traversal of a TTree (gtree). The tree I am building looks like

Code: Pascal  [Select]
  1. {*
  2. *
  3. *         1
  4. *       /   \
  5. *      2     3
  6. *     / \   / \
  7. *    4   5 6   7
  8. *
  9. * }

When using tree.DepthFirstTraverse() I get:

Code: Pascal  [Select]
  1. 1 3 7 6 2 5 4

which is right to left, but I need it to be from left to right, ie

Code: Pascal  [Select]
  1. 1 2 4 5 3 6 7

edit: pre-order per this article

https://en.wikipedia.org/wiki/Tree_traversal#Depth-first_search

I kind of see why this happens from the TTrree source:

Code: Pascal  [Select]
  1. procedure TTree.DepthFirstTraverse(Callback: TDepthFirstCallbackType);
  2. var
  3.   Stack: TStackType;
  4.   Node,Child: TTreeNodeType;
  5. begin
  6.   if Assigned(FRoot) then begin
  7.     Stack := TStackType.Create;
  8.     Stack.Push(FRoot);
  9.     while Stack.Size > 0 do begin
  10.       Node := Stack.Top;
  11.       Stack.Pop;
  12.       Callback(Node.Data);
  13.       for Child in Node.Children do Stack.Push(Child);
  14.     end;
  15.     Stack.Free;
  16.   end;
  17. end;

It pushes nodes to a stack and then pops them back so the rightmost nodes get processed first. Here is my test code:

Code: Pascal  [Select]
  1. program project1;
  2.  
  3. {$mode objfpc}{$H+}
  4.  
  5. uses
  6.     gtree, gvector, sysutils;
  7.  
  8.  
  9. type
  10.  
  11.     TExpression = class(TObject)
  12.     public
  13.         value: integer;
  14.         constructor Create(v: integer);
  15.     end;
  16.  
  17.     TExpressionNode = class(specialize TTreeNode<TExpression>)
  18.         destructor Destroy; override;
  19.     end;
  20.    
  21.     TExpressionTree = specialize TTree<TExpression>;
  22.    
  23.     TIntVector = specialize TVector<integer>;
  24.  
  25.  
  26.  
  27. var
  28.     tree: TExpressionTree;
  29.     n1, n2, n3, n4, n5, n6, n7: TExpressionNode;
  30.     e1, e2, e3, e4, e5, e6, e7: TExpression;
  31.    
  32.     v: TIntVector;
  33.     i: integer;
  34.    
  35.  
  36. constructor TExpression.Create(v: integer);
  37. begin
  38.     self.value := v;
  39. end;
  40.  
  41.  
  42. destructor TExpressionNode.Destroy;
  43. begin
  44.     self.Data.Free;
  45.     inherited;
  46. end;
  47.  
  48.  
  49. procedure WriteCallback(const e: TExpression);
  50. begin
  51.     write(e.value, ' ');
  52. end;
  53.  
  54.    
  55. begin
  56.  
  57. {*
  58. *
  59. *         1
  60. *       /   \
  61. *      2     3
  62. *     / \   / \
  63. *    4   5 6   7
  64. *
  65. * }
  66.  
  67.  
  68.     e1 := TExpression.Create(1);
  69.     e2 := TExpression.Create(2);
  70.     e3 := TExpression.Create(3);
  71.     e4 := TExpression.Create(4);
  72.     e5 := TExpression.Create(5);
  73.     e6 := TExpression.Create(6);
  74.     e7 := TExpression.Create(7);
  75.    
  76.     n1 := TExpressionNode.Create;
  77.     n2 := TExpressionNode.Create;
  78.     n3 := TExpressionNode.Create;
  79.     n4 := TExpressionNode.Create;
  80.     n5 := TExpressionNode.Create;
  81.     n6 := TExpressionNode.Create;
  82.     n7 := TExpressionNode.Create;
  83.    
  84.     tree := TExpressionTree.Create;
  85.    
  86.     n1.Data := e1;
  87.     n2.Data := e2;
  88.     n3.Data := e3;
  89.     n4.Data := e4;
  90.     n5.Data := e5;
  91.     n6.Data := e6;
  92.     n7.Data := e7;
  93.    
  94.     n1.Children.PushBack(n2);
  95.     n1.Children.PushBack(n3);
  96.    
  97.     n2.Children.PushBack(n4);
  98.     n2.Children.PushBack(n5);
  99.    
  100.     n3.Children.PushBack(n6);
  101.     n3.Children.PushBack(n7);    
  102.    
  103.     tree.Root := n1;
  104.    
  105.     tree.DepthFirstTraverse(@WriteCallback);
  106.     writeln;
  107.    
  108.     tree.BreadthFirstTraverse(@WriteCallback);
  109.     writeln;
  110.    
  111.     tree.Free;
  112.    
  113.     v := TIntVector.Create;
  114.    
  115.     for i := 1 to 10 do
  116.     begin
  117.         v.PushBack(i);
  118.     end;
  119.    
  120.     for i in v do
  121.     begin
  122.         write(i, ' ');
  123.     end;
  124.    
  125.     v.Free;
  126.    
  127.     writeln;
  128.    
  129. end.
  130.  
  131.  

The background is I am trying to build an AST from a Pyacc generated parser.
« Last Edit: September 21, 2019, 08:03:51 pm by Anonimista »

simone

  • Full Member
  • ***
  • Posts: 249
Re: TTree depth-first traversal
« Reply #1 on: September 22, 2019, 12:07:05 am »
A 'quick and dirty' solution is modify your code as follows (see comments added in code):

Code: Pascal  [Select]
  1. program project1;
  2.  
  3. {$mode objfpc}{$H+}
  4.  
  5. uses
  6.     gtree, gvector, sysutils;
  7.  
  8.  
  9. type
  10.  
  11.     TExpression = class(TObject)
  12.     public
  13.         value: integer;
  14.         constructor Create(v: integer);
  15.     end;
  16.  
  17.     TExpressionNode = class(specialize TTreeNode<TExpression>)
  18.         destructor Destroy; override;
  19.     end;
  20.  
  21.     { TExpressionTree }
  22.  
  23.     TExpressionTree = class(specialize TTree<TExpression>) //inherits from TTree<TExpression>
  24.       procedure DepthFirstTraverse(Callback: TDepthFirstCallbackType); //hide original procedure
  25.     end;
  26.  
  27.     TIntVector = specialize TVector<integer>;
  28.  
  29.  
  30.  
  31. var
  32.     tree: TExpressionTree;
  33.     n1, n2, n3, n4, n5, n6, n7: TExpressionNode;
  34.     e1, e2, e3, e4, e5, e6, e7: TExpression;
  35.  
  36.     v: TIntVector;
  37.     i: integer;
  38.  
  39. { TExpressionTree }
  40.  
  41. procedure TExpressionTree.DepthFirstTraverse(Callback: TDepthFirstCallbackType); //new depth first traverse
  42. var
  43.   Stack: TStackType;
  44.   Node{,Child}: TTreeNodeType; //Child variable no longer needed
  45.   ind : integer;
  46. begin
  47.   if Assigned(FRoot) then begin
  48.     Stack := TStackType.Create;
  49.     Stack.Push(FRoot);
  50.     while Stack.Size > 0 do begin
  51.       Node := Stack.Top;
  52.       Stack.Pop;
  53.       Callback(Node.Data);
  54.       //for Child in Node.Children do Stack.Push(Child); //(right to left order) replaced by following line
  55.       for ind:=Node.Children.Size-1 downto 0 do Stack.Push(Node.Children[ind]); //inverts order of iteration over children
  56.     end;
  57.     Stack.Free;
  58.   end;
  59. end;
  60.  
  61.  
  62. constructor TExpression.Create(v: integer);
  63. begin
  64.     self.value := v;
  65. end;
  66.  
  67.  
  68. destructor TExpressionNode.Destroy;
  69. begin
  70.     self.Data.Free;
  71.     inherited;
  72. end;
  73.  
  74.  
  75. procedure WriteCallback(const e: TExpression);
  76. begin
  77.     write(e.value, ' ');
  78. end;
  79.  
  80.  
  81. begin
  82.  
  83. {*
  84. *
  85. *         1
  86. *       /   \
  87. *      2     3
  88. *     / \   / \
  89. *    4   5 6   7
  90. *
  91. * }
  92.  
  93.  
  94.     e1 := TExpression.Create(1);
  95.     e2 := TExpression.Create(2);
  96.     e3 := TExpression.Create(3);
  97.     e4 := TExpression.Create(4);
  98.     e5 := TExpression.Create(5);
  99.     e6 := TExpression.Create(6);
  100.     e7 := TExpression.Create(7);
  101.  
  102.     n1 := TExpressionNode.Create;
  103.     n2 := TExpressionNode.Create;
  104.     n3 := TExpressionNode.Create;
  105.     n4 := TExpressionNode.Create;
  106.     n5 := TExpressionNode.Create;
  107.     n6 := TExpressionNode.Create;
  108.     n7 := TExpressionNode.Create;
  109.  
  110.     tree := TExpressionTree.Create;
  111.  
  112.     n1.Data := e1;
  113.     n2.Data := e2;
  114.     n3.Data := e3;
  115.     n4.Data := e4;
  116.     n5.Data := e5;
  117.     n6.Data := e6;
  118.     n7.Data := e7;
  119.  
  120.     n1.Children.PushBack(n2);
  121.     n1.Children.PushBack(n3);
  122.  
  123.     n2.Children.PushBack(n4);
  124.     n2.Children.PushBack(n5);
  125.  
  126.     n3.Children.PushBack(n6);
  127.     n3.Children.PushBack(n7);
  128.  
  129.     tree.Root := n1;
  130.  
  131.     tree.DepthFirstTraverse(@WriteCallback);
  132.     writeln;
  133.  
  134.     tree.BreadthFirstTraverse(@WriteCallback);
  135.     writeln;
  136.  
  137.     tree.Free;
  138.  
  139.     v := TIntVector.Create;
  140.  
  141.     for i := 1 to 10 do
  142.     begin
  143.         v.PushBack(i);
  144.     end;
  145.  
  146.     for i in v do
  147.     begin
  148.         write(i, ' ');
  149.     end;
  150.  
  151.     v.Free;
  152.  
  153.     writeln;
  154.  
  155.     readln;
  156.  
  157. end.
« Last Edit: September 22, 2019, 12:26:45 am by simone »

jamie

  • Hero Member
  • *****
  • Posts: 1993
Re: TTree depth-first traversal
« Reply #2 on: September 22, 2019, 02:24:10 am »
Nice guy you are..

 I wish I had  you around when I was doing my home work! :)

avk

  • Full Member
  • ***
  • Posts: 131
    • my self-education project
Re: TTree depth-first traversal
« Reply #3 on: September 22, 2019, 04:23:35 am »
@Anonimista, another option is to write your own recursive DFS that will do what you need, it is very simple.

Anonimista

  • New Member
  • *
  • Posts: 19
Re: TTree depth-first traversal
« Reply #4 on: September 22, 2019, 07:14:38 am »
Thank you guys. @avk yes I tend to lose time trying to find a ready-made solution even when it's probably easier to make one myself. oh well

simone

  • Full Member
  • ***
  • Posts: 249
Re: TTree depth-first traversal
« Reply #5 on: September 22, 2019, 12:40:55 pm »
@Anonimista, another option is to write your own recursive DFS that will do what you need, it is very simple.

I agree. A recursive DFS would be more compact and elegant (I say this because I spent some time with Lisp and Prolog during my youth). I note only that it would have the two typical small disadvantages of recursive algorithms. First, it would be slightly slower. Second, since recursive calls allocate resources in the system stack, in the case of traversals of very large trees, a stack overflow could happen during execution.
« Last Edit: September 22, 2019, 01:23:29 pm by simone »

avk

  • Full Member
  • ***
  • Posts: 131
    • my self-education project
Re: TTree depth-first traversal
« Reply #6 on: September 22, 2019, 02:23:58 pm »
I note only that it would have the two typical small disadvantages of recursive algorithms. First, it would be slightly slower. Second, since recursive calls allocate resources in the system stack, in the case of traversals of very large trees, a stack overflow could happen during execution.
Do you have any benchmark confirming the first thesis? I am interested because my own measurements usually show the opposite.
As for the second, it doesn't seem to matter much, since the TTreeNode destructor is already recursive.

simone

  • Full Member
  • ***
  • Posts: 249
Re: TTree depth-first traversal
« Reply #7 on: September 22, 2019, 04:17:18 pm »
I note only that it would have the two typical small disadvantages of recursive algorithms. First, it would be slightly slower. Second, since recursive calls allocate resources in the system stack, in the case of traversals of very large trees, a stack overflow could happen during execution.
Do you have any benchmark confirming the first thesis? I am interested because my own measurements usually show the opposite.
As for the second, it doesn't seem to matter much, since the TTreeNode destructor is already recursive.

This fact is well known in literature. See, for example:

https://en.wikipedia.org/wiki/Recursion_(computer_science)#Performance_issues
"Performance issues
In languages (such as C and Java) that favor iterative looping constructs, there is usually significant time and space cost associated with recursive programs, due to the overhead required to manage the stack and the relative slowness of function calls; in functional languages, a function call (particularly a tail call) is typically a very fast operation, and the difference is usually less noticeable.
As a concrete example, the difference in performance between recursive and iterative implementations of the "factorial" example above depends highly on the compiler used. In languages where looping constructs are preferred, the iterative version may be as much as several orders of magnitude faster than the recursive one. In functional languages, the overall time difference of the two implementations may be negligible; in fact, the cost of multiplying the larger numbers first rather than the smaller numbers (which the iterative version given here happens to do) may overwhelm any time saved by choosing iteration."

Sedgewick, Wayne, "Alghorithms", 4th ed. p. 415:
"Generally, recursive implementations are a bit easier to verify for correctness; nonrecursive
implementations are a bit more efficient."

avk

  • Full Member
  • ***
  • Posts: 131
    • my self-education project
Re: TTree depth-first traversal
« Reply #8 on: September 22, 2019, 04:51:32 pm »
We are not talking about the "grand and terrible" Factorial, but specifically about DFS, right?
Well, personally, I have never been able to write iterative DFS, which would be faster than recursive one.

howardpc

  • Hero Member
  • *****
  • Posts: 3152
Re: TTree depth-first traversal
« Reply #9 on: September 22, 2019, 04:59:00 pm »
"Iterative algorithms are typically faster than recursive ones."
Like many generalisations the correctness of the assertion is often belied by actual measurements.
Algorithms can vary so widely and be used on such varied data that generalisations about comparing them are no better than a rough guide.

Like avk the few times I have done actual measurements on equivalent algorithms chewing their way through identical data I have not found particularly significant speed differences between iterative and recursive methods (provided both routines are well optimsed, of course). Which is not to deny that there are cases where one type of algorithm performs consistently better than the other approach.



440bx

  • Hero Member
  • *****
  • Posts: 1129
Re: TTree depth-first traversal
« Reply #10 on: September 22, 2019, 04:59:21 pm »
Sedgewick, Wayne, "Alghorithms", 4th ed. p. 415:
"Generally, recursive implementations are a bit easier to verify for correctness; nonrecursive implementations are a bit more efficient."
That's one of the books I keep at hand and, unsurprisingly, he is right.  One thing that should be noted is that, recursion can often be the simplest and most intuitive way of implementing an algorithm but, that doesn't mean it is the best (read, reasonably efficient) way.

Sedgewick's book has a chapter on recursion (chapter 5 in my edition) which provides some examples of the above.  Some algorithms are really simple to implement using recursion but have undesirable Big Os when implemented that way.  That is a problem of the algorithm, not of recursion (like a bubble sort is simply a poor algorithm regardless of how it is implemented.)

Just like everything else, some algorithms can be implemented simply, efficiently and elegantly using recursion, others, not so much. ;)


using FPC v3.0.4 and Lazarus 1.8.2 on Windows 7 64bit.

simone

  • Full Member
  • ***
  • Posts: 249
Re: TTree depth-first traversal
« Reply #11 on: September 22, 2019, 05:45:45 pm »
I have not revealed an absolute truth, but a typical situation: in general recursive alghorithms are slightly slower than iterative ones, because they require as many 'calls with return' as the number of recursive cycles.  These types of operations are very expensive for the CPU.  I mentioned authoritative sources in support of my thesis. If someone cites to me equally authoritative sources or shows me experimental evidence of the opposite sign, I am happy to change my mind, because I often use recursive algorithms. :D
« Last Edit: September 22, 2019, 05:48:47 pm by simone »

simone

  • Full Member
  • ***
  • Posts: 249
Re: TTree depth-first traversal
« Reply #12 on: September 22, 2019, 06:26:15 pm »
Moreover, every recursive call requires a stack frame allocation. This is a further cause of slowing down performances and could generate stack overflow. Finally, note that the DFS algorithm implemented by Leledumbo in gtree unit is iterative. 

avk

  • Full Member
  • ***
  • Posts: 131
    • my self-education project
Re: TTree depth-first traversal
« Reply #13 on: September 22, 2019, 08:06:11 pm »
The algorithm implemented by Leledumbo is not equivalent to DFS, otherwise this thread would not have arisen.

simone

  • Full Member
  • ***
  • Posts: 249
Re: TTree depth-first traversal
« Reply #14 on: September 22, 2019, 08:30:10 pm »
Yes, I agree. In the gtree unit are implemented a Depth First Traversal and a Breadth First Traversal algorithm. However graph search and graph traversal are very similar algorithms. My posts were not a crusade against recursion! I just wanted to highlight some possible side effects.  O:-)
« Last Edit: September 22, 2019, 08:41:12 pm by simone »