Directed Graph Traversal

bukzor workitharder at gmail.com
Wed Apr 2 00:46:20 CEST 2008


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



More information about the Python-list mailing list