|DAG walking problem email@example.com (1997-04-16)|
|Re: DAG walking problem firstname.lastname@example.org (Keith L. Breinholt) (1997-04-22)|
|From:||email@example.com (Stephen Clarke)|
|Date:||16 Apr 1997 00:29:43 -0400|
|Organization:||University of Bristol, England|
I have a graph-walking problem for which I'm sure there is a standard
solution, but I can't find one in the text books I have available.
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 ...
PACT (Partnership in Advanced Computer Technologies)
Mail : 10 Priory Road, Clifton, Bristol, BS8 1TU. UK.
Phone: +44 117 970 7188, Fax +44 117 970 7171.
Return to the
Search the comp.compilers archives again.