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]
--
http://mail.python.org/mailman/listinfo/python-list
