Directed Graph Traversal

[Tim Daneliuk]

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, where each node is a table
> and each edge is a join. I'm planning on using the NetworkX library if
> possible.
> https://networkx.lanl.gov/reference/networkx/
> 
> 
> 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.
> 
> 
> A -- B -- C -- D
>        |      |
>       E --  F
> 
> 
> A, B, F  =>  ABEF (or ABCF)
> A, F, C => ABCF
> A, E, D => ABCD
>                    E
> 
> Thanks!
> --Buck

This leaps to mind:

  http://en.wikipedia.org/wiki/Kruskal's_algorithm

The implementation details are left to the reader ;)



-- 
----------------------------------------------------------------------------
Tim Daneliuk     tundra at tundraware.com
PGP Key:         http://www.tundraware.com/PGP/