www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - foreach DFS/BFS for tree data-structure?

reply =?iso-8859-1?Q?Robert_M._M=FCnch?= <robert.muench saphirion.com> writes:
I have a simple tree C data-structure that looks like this:

node {
	node parent:
	vector[node] children;
}

I would like to create two foreach algorthims, one follwing the breadth 
first search pattern and one the depth first search pattern.

Is this possible? I read about Inputranges, took a look at the RBTree 
code etc. but don't relly know/understand where to start.

-- 
Robert M. MŁnch
http://www.saphirion.com
smarter | better | faster
Jun 14 2018
next sibling parent rikki cattermole <rikki cattermole.co.nz> writes:
On 14/06/2018 11:31 PM, Robert M. M√ľnch wrote:
 I have a simple tree C data-structure that looks like this:
 
 node {
struct Node {
      node parent:
Node* parent;
      vector[node] children;
Node[] children;
 }
 
 I would like to create two foreach algorthims, one follwing the breadth 
 first search pattern and one the depth first search pattern.
Here is (very roughly breadth): auto search(Method method) { struct Voldermort { Node parent; size_t offset; property { Node front() { return parent.children[offset]; } bool empty() { return offset == parent.children.length; } } void popFront() { offset++; } } return Voldermort(this); } Depth will be a bit of a pain since you'll need to know where you have been at each set of children.
Jun 14 2018
prev sibling next sibling parent reply Dennis <dkorpel gmail.com> writes:
On Thursday, 14 June 2018 at 11:31:50 UTC, Robert M. M√ľnch wrote:
 Is this possible? I read about Inputranges, took a look at the 
 RBTree code etc. but don't relly know/understand where to start.
You can also use opApply to iterate over a tree using foreach, see: https://tour.dlang.org/tour/en/gems/opdispatch-opapply
Jun 14 2018
parent reply =?iso-8859-1?Q?Robert_M._M=FCnch?= <robert.muench saphirion.com> writes:
On 2018-06-14 11:46:04 +0000, Dennis said:

 On Thursday, 14 June 2018 at 11:31:50 UTC, Robert M. MŁnch wrote:
 Is this possible? I read about Inputranges, took a look at the RBTree 
 code etc. but don't relly know/understand where to start.
You can also use opApply to iterate over a tree using foreach, see: https://tour.dlang.org/tour/en/gems/opdispatch-opapply
Ah... that looks very good. Need to dig a bit deeper on how to use it. Thanks. -- Robert M. MŁnch http://www.saphirion.com smarter | better | faster
Jun 14 2018
parent Steven Schveighoffer <schveiguy yahoo.com> writes:
On 6/14/18 8:35 AM, Robert M. M√ľnch wrote:
 On 2018-06-14 11:46:04 +0000, Dennis said:
 
 On Thursday, 14 June 2018 at 11:31:50 UTC, Robert M. M√ľnch wrote:
 Is this possible? I read about Inputranges, took a look at the RBTree 
 code etc. but don't relly know/understand where to start.
You can also use opApply to iterate over a tree using foreach, see: https://tour.dlang.org/tour/en/gems/opdispatch-opapply
Ah... that looks very good. Need to dig a bit deeper on how to use it. Thanks.
Just to clarify, RBTree can easily do DFS without a real stack because there are a finite number of children (2) for each node, and it's an O(1) operation to figure out which child the current node is in relation to the parent (am I a left child or right child?). Now, with your C version, if your children are stored in the array itself, figuring out the "next" child is a matter of doing &this + 1. But if you are storing pointers instead, then figuring out the next child would be an O(n) operation. Using the stack to track where you are (via opApply) is a valid way as well. You could also unroll that into a malloc'd stack, but the code is not as pretty of course. -Steve
Jun 14 2018
prev sibling next sibling parent Meta <jared771 gmail.com> writes:
On Thursday, 14 June 2018 at 11:31:50 UTC, Robert M. M√ľnch wrote:
 I have a simple tree C data-structure that looks like this:

 node {
 	node parent:
 	vector[node] children;
 }

 I would like to create two foreach algorthims, one follwing the 
 breadth first search pattern and one the depth first search 
 pattern.

 Is this possible? I read about Inputranges, took a look at the 
 RBTree code etc. but don't relly know/understand where to start.
While it's possible to do with input ranges, it's not pretty and I'm not sure that it's as performant as the traditional method. I would recommend going with one of the other suggestions in this thread.
Jun 14 2018
prev sibling parent Timoses <timosesu gmail.com> writes:
On Thursday, 14 June 2018 at 11:31:50 UTC, Robert M. M√ľnch wrote:
 I have a simple tree C data-structure that looks like this:

 node {
 	node parent:
 	vector[node] children;
 }

 I would like to create two foreach algorthims, one follwing the 
 breadth first search pattern and one the depth first search 
 pattern.

 Is this possible? I read about Inputranges, took a look at the 
 RBTree code etc. but don't relly know/understand where to start.
What I found really interesting when reading Ali Çehreli's book 'Programming in D' was using fibers for tree iteration. Check out http://ddili.org/ders/d.en/fibers.html and skip to the section "Fibers in range implementations"
Jun 16 2018