Directed Graph Traversal

bukzor workitharder at gmail.com
Wed Apr 2 00:49:13 CEST 2008


On Apr 1, 3:46 pm, bukzor <workithar... at gmail.com> 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

edited to correct diagram for monospace font...



More information about the Python-list mailing list