On Apr 2, 8:33 pm, Scott David Daniels <[EMAIL PROTECTED]> 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 > [EMAIL PROTECTED]
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 pythonic enjoyment. --Buck -- http://mail.python.org/mailman/listinfo/python-list
