Directed Graph Traversal

Collapse
This topic is closed.
X
X
Collapse
 
  • Page of 1
  • Time
  • Show
Clear All
new posts
Previous template Next
  • bukzor
    #1

    Directed Graph Traversal

    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
    Tags: None
    • bukzor
      #2
      Re: Directed Graph Traversal

      On Apr 1, 3:46 pm, bukzor <workithar...@g mail.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...

        Comment

        • Tim Daneliuk
          #3
          Re: Directed Graph Traversal

          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.or g/wiki/Kruskal's_algor ithm

          The implementation details are left to the reader ;)



          --
          ----------------------------------------------------------------------------
          Tim Daneliuk tundra@tundrawa re.com
          PGP Key: http://www.tundraware.com/PGP/

            Comment

            • Scott David Daniels
              #4
              Re: Directed Graph Traversal

              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.Daniels@A cm.Org

                Comment

                • bukzor
                  #5
                  Re: Directed Graph Traversal

                  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...@A cm.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

                    Comment

                    Previous template Next
                    Working...