By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
440,097 Members | 1,580 Online
Bytes IT Community
+ Ask a Question
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
Share this Question
Share on Google+
4 Replies


P: n/a
On Apr 1, 3:46 pm, bukzor <workithar...@gmail.comwrote:
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
edited to correct diagram for monospace font...
Apr 1 '08 #2

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 <Scott.Dani...@Acm.Orgwrote:
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...@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
pythonic enjoyment.

--Buck
Apr 3 '08 #5

This discussion thread is closed

Replies have been disabled for this discussion.