Directed Graph Traversal
workitharder at gmail.com
Thu Apr 3 18:38:31 CEST 2008
On Apr 2, 8:33 pm, Scott David Daniels <Scott.Dani... at Acm.Org> wrote:
> bukzor wrote:
> > Can someone point me in the direction of a good solution of this? I'm
> > using it to construct a SQL query compiler, ....
> > Given a directed graph and a list of points in the graph, what is the
> > minimal subgraph that contains them all? It is preferable that the
> > subgraph is a tree.
> I did something nice (but non-redistributable) on this once: here is the
> driving intuition:
> * Start with every point a distinct color.
> * Add all points adjacent in the digraph as the same color; merge
> colors as you join them.
> * When you are down to to a single color, you have the minimal solution
> in the set you've chosen.
> I actually did a cheapest-first search; adding an edge each time.
> There is a post-join pruning step that was (as I recall) fairly simple.
> -Scott David Daniels
> Scott.Dani... at Acm.Org
That sounds like a kind of iterative deepening search, which is what
I'm planning to do. Once I have it written up, I'll post for your
More information about the Python-list