Re: DAG walking problem

Stephen Clarke wrote:
> I have a DAG, and I want to visit the vertices in topological order
> (i.e. I can only visit a vertex after I have visited all its
> predecessors). I have to store information with each vertex after I
> visit it, and I can only discard the information after I have visited
> all of its immediate successors. Assuming the space required for this
> information is the same for every vertex, I would like to visit the
> vertices in an order that minimizes the maximum amount of space
> required for the complete walk.
>
> Obviously, depth first order is not the best order on very deep
> graphs, and breadth first ordering is not the best order on very broad
> graphs. I can envisage some kind of priority ordering where I
> prioritize the avialable vertices according to how much info they
> allow me to discard, but it seems there ought to be some more elegant
> solution than this ...


In order to prioritize your graph you would need to scan the graph
first and then pick and store your priorities in some fashion. The
above would require both time and resources. If you want to conserve
on resources you just killed the reason for prioritizing your walk.


Sometimes the simplest approach is the best approach.
--
kbreinho@bsquare.com
--

Return to the comp.compilers page.
Search the comp.compilers archives again.