title: All unique paths in a directed acyclic graph, in randomized order, via Python generator?
body: <p>I have a <a href="https://en.wikipedia.org/wiki/Directed_acyclic_graph" rel="nofollow noreferrer">Directed Acyclic Graph</a> (DAG), which consists of layers, with two subsequent layers being completely bipartite (much like a neural net), like the following:</p>
  
  <p><a href="https://i.stack.imgur.com/8Nt1U.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/8Nt1U.png" alt="A DAG with 8 vertices"></a></p>
  
  <p>I want to <strong>stream</strong> all paths in the DAG, in an <strong>iterative manner</strong>, via some <strong>generator</strong>, in a randomized order. Because, <strong>output must not be in order</strong>, textbook DFS approaches are out of question. Memory is an issue, so I don't want to store any paths that I have yielded before, except the DAG alone, which could be modified however is needed.</p>
  
  <p>Example, the desired output for the above DAG is:</p>
  
  <pre><code>(1, 4, 6, 8)
  (3, 4, 5, 8)
  (2, 4, 7, 8)
  (3, 4, 6, 8)
  (1, 4, 5, 8)
  (3, 4, 7, 8)
  (1, 4, 7, 8)
  (2, 4, 6, 8)
  (2, 4, 5, 8)
  </code></pre>
  
  <p>instead of the following produced by DFS:</p>
  
  <pre><code>(1, 4, 5, 8)
  (1, 4, 6, 8)
  (1, 4, 7, 8)
  (2, 4, 5, 8)
  (2, 4, 6, 8)
  (2, 4, 7, 8)
  (3, 4, 5, 8)
  (3, 4, 6, 8)
  (3, 4, 7, 8)
  </code></pre>
  
  <p>Thanks for your help.</p>
  
  <p>Update:</p>
  
  <p>I have the following code</p>
  
  <pre><code>graph = {
      1: set([4]),
      2: set([4]),
      3: set([4]),
      4: set([5, 6, 7]),
      5: set([8]),
      6: set([8]),
      7: set([8])
  }
  
  def dfs_paths(graph, start, goal):
      stack = [(start, [start])]
      while stack:
          (vertex, path) = stack.pop()
          for next in graph[vertex] - set(path):
              if next == goal:
                  yield path + [next]
              else:
                  stack.append((next, path + [next]))
  
  def run_paths():
      for start in [1, 2, 3]:
          for path in dfs_paths(graph, start, 8):
              print path
  </code></pre>
  
  <p>Finding all paths and then randomly streaming them will not work for me, as I do not want to store any paths I will be generating.</p>