Directed Graph Traversal

bukzor workitharder at
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

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


More information about the Python-list mailing list