DAG walking problem

stevec@pact.srf.ac.uk (Stephen Clarke)
16 Apr 1997 00:29:43 -0400

          From comp.compilers
Related articles
DAG walking problem stevec@pact.srf.ac.uk (1997-04-16)
Re: DAG walking problem kbreinho@bsquare.com (Keith L. Breinholt) (1997-04-22)
| List of all articles for this month |
From: stevec@pact.srf.ac.uk (Stephen Clarke)
Newsgroups: comp.compilers
Date: 16 Apr 1997 00:29:43 -0400
Organization: University of Bristol, England
Keywords: question, theory

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 ...


Any offers?


Steve
--------------
PACT (Partnership in Advanced Computer Technologies)
Email: stevec@pact.srf.ac.uk
Mail : 10 Priory Road, Clifton, Bristol, BS8 1TU. UK.
Phone: +44 117 970 7188, Fax +44 117 970 7171.
--

Post a followup to this message

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