Need help with this data structure

[Knews]

hi,
Can someone help me with this problem.
I have a java data structure of the form

A11
- -
- -
- -
A21 A22
- - - - - -
- - - - - -
A31 A32 A33 A34 A35 A36
- - - - - -
- - - - - -
- - -
-
-
A41
Ai correspond to actions, my application should traverse the structure
and perform each action upon traversal. Actually using the composite
design pattern I can perform A11, A21, (A31,A32, A33) , A41 then the
other part A22, (A31, A32, A33).
The problem is that I need to have actions in the same level to
completly perform before the lowest level. I mean, that A41 is
performed only when the two parts in the same level (A21, A22, A31,
A32, A33) and (A34, A35, A36) are performed not necessarily at the
same time but before A41. How to do that?
Thank you

 

[E.C. Bäck]

hi,
Can someone help me with this problem.
I have a java data structure of the form

A11
- -
- -
- -
A21 A22
- - - - - -
- - - - - -
A31 A32 A33 A34 A35 A36
- - - - - -
- - - - - -
- - -
-
-
A41
Ai correspond to actions, my application should traverse the structure
and perform each action upon traversal. Actually using the composite
design pattern I can perform A11, A21, (A31,A32, A33) , A41 then the
other part A22, (A31, A32, A33).
The problem is that I need to have actions in the same level to
completly perform before the lowest level. I mean, that A41 is
performed only when the two parts in the same level (A21, A22, A31,
A32, A33) and (A34, A35, A36) are performed not necessarily at the
same time but before A41. How to do that?
Thank you

There are two basic forms of tree navigation: depth-first-search (DFS) and
breadth-first-search (BFS). The former (DFS) traverses to the leaves of a
tree first, and then "backs up" to explore the other branches. This is what
you don't want. However, the latter (BFS) explores all the children of a
node, before looking at those nodes's children. Use a queue.

http://www.ics.uci.edu/~eppstein/161/960215.html
http://www.comp.lancs.ac.uk/computi...eople/paulb/old243prolog/subsection3_6_2.html

--
Thanks,
Elliott C. Bäck

Sophomore, Computer Science
Cornell University

"Knews" <[email protected]> wrote in message

 

[Roedy Green]

However, the latter (BFS) explores all the children of a
node, before looking at those nodes's children. Use a queue.

the queue holds all the children of a generation?

 

[rkm]

hi,
Can someone help me with this problem.
I have a java data structure of the form

A11
- -
- -
- -
A21 A22
- - - - - -
- - - - - -
A31 A32 A33 A34 A35 A36
- - - - - -
- - - - - -
- - -
-
-
A41
Ai correspond to actions, my application should traverse the structure
and perform each action upon traversal. Actually using the composite
design pattern I can perform A11, A21, (A31,A32, A33) , A41 then the
other part A22, (A31, A32, A33).
The problem is that I need to have actions in the same level to
completly perform before the lowest level. I mean, that A41 is
performed only when the two parts in the same level (A21, A22, A31,
A32, A33) and (A34, A35, A36) are performed not necessarily at the
same time but before A41. How to do that?
Thank you

Visit the nodes in post-fix order. For each level you
encounter, build a stack for that level and push the node
encountered onto the stack. Traverse the entire tree until
you have all your stacks populated. In your example, there
would be 4 stacks. Then run an execution phase where you
take the stack for level 1 and pop and execute its first
(and only?) action. When that stack is exhausted, move onto
stack 2, popping and executing, etc.

I can't tell from your diagram if A41 is reachable from more
than one node at level 3, so you might have to modify the
algorithm to account for that.

Rick

 

[Harald Kirsch]

Can someone help me with this problem.
I have a java data structure of the form

A11
- -
- -
- -
A21 A22
- - - - - -
- - - - - -
A31 A32 A33 A34 A35 A36
- - - - - -
- - - - - -
- - -
-
-
A41 [...]
The problem is that I need to have actions in the same level to
completly perform before the lowest level.

Since this is a DAG (directed acyclic graph) rather than a tree, normal
tree-walking algorithm will step on A41 more than once.

I would dig down into the DAG recursively, keeping track of nodes visited
in a IdentityHashset. At each node, first visit the as yet unvisited
children. Then append it to a list or Vector. When you
pop out again at the top of the DAG, run the actions in the Vector from
back to front.

Some pseudo code:

// call this with your root node.
public callDAGActions(Action node) {
Vector v = new Vector(); // will collect actions in correct order
IdentityHashset known = new IdentityHashset(); // visited nodes

// visit is recursive, see below
visit(node, v, known);

// run actions back to front
for(int i=v.size(); i>0; i--) ((Action)(v.get(i-1)).do();
}

private visit(Action node, Vector v, IdentityHashset known) {
known.put(node);

Action child;

// iterate over all children of this node, call recursive
// only if the child was not yet handled.
foreach child:node.children() {
if( known.contains(child) ) continue;
visit(child, v, known);
}
v.add(node);
}

REMARK: If you can afford a boolean visited in every node, you can
do without the possibly expensive IdentityHashset known. You only
have to make sure that you reset the visited flag when working your
way backwards over Vector v. And then don't operate on the data structure
within two threads without locking. Otherwise they mutually mess up
the visited flag.


This was not compiled or tested. It may not work at all. I don't
give any guarantees.

Harald.

 

[E.C. Bäck]

the queue holds all the children of a generation?

I think the algorithm basically (1) puts the root into a queue (2) explores
the root (3) puts its children in the queue (4) takes itself out (5) looks
at the next child-->root-->(1).
--
Thanks,
Elliott C. Bäck

Sophomore, Computer Science
Cornell University