440,097 Members | 1,580 Online
Need help? Post your question and get tips & solutions from a community of 440,097 IT Pros & Developers. It's quick & easy.

# Directed Graph Traversal

 P: n/a 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 Apr 1 '08 #1
4 Replies

 P: n/a On Apr 1, 3:46 pm, bukzor

 P: n/a 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 tu****@tundraware.com PGP Key: http://www.tundraware.com/PGP/ Apr 1 '08 #3

 P: n/a 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 Sc***********@Acm.Org Apr 3 '08 #4

 P: n/a On Apr 2, 8:33 pm, Scott David Daniels

### This discussion thread is closed

Replies have been disabled for this discussion.