title: Tail recursive algorithm for generating all topological orderings in a graph
body: <p>Given a graph i need to generate <em>all</em> topological orderings.
  For instance, given the following graph:</p>
  
  <p><a href="https://i.stack.imgur.com/2Wz5t.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/2Wz5t.png" alt="enter image description here"></a></p>
  
  <p>i want to generate all topological orderings, which are:</p>
  
  <ul>
  <li>2 4 7 5</li>
  <li>2 7 4 5</li>
  <li>2 4 5 7</li>
  </ul>
  
  <p>Because many topological orderings may exist, I need to generate them lazily. Currently, I have a working implementation that is recursive and works on top of the <code>scala-graph</code> library:</p>
  
  <pre><code>import scalax.collection.Graph
  import scalax.collection.GraphPredef._
  import scalax.collection.GraphEdge._
  
  import scala.collection.mutable.ArrayStack
  import scala.collection.Set
  
  def allTopologicalSorts[T](graph: Graph[T, DiEdge]): Stream[List[graph.NodeT]] = {
    val indegree: Map[graph.NodeT, Int] = graph.nodes.map(node =&gt; (node, node.inDegree)).toMap
  
    def isSource(node: graph.NodeT): Boolean = indegree.get(node).get == 0
    def getSources(): Set[graph.NodeT] = graph.nodes.filter(node =&gt; isSource(node))
  
    def processSources(sources: Set[graph.NodeT], indegrees: Map[graph.NodeT, Int], topOrder: List[graph.NodeT], cnt: Int): Stream[List[graph.NodeT]] = {
      if (sources.nonEmpty) {
        // `sources` contain all the nodes we can pick
        // --&gt; generate all possibilities
        sources.toStream.flatMap(src =&gt; {
          val newTopOrder = src :: topOrder
          var newSources = sources - src
  
          // Decrease the in-degree of all adjacent nodes
          var newIndegrees = indegrees
          for (adjacent &lt;- src.diSuccessors) {
            val newIndeg = newIndegrees.get(adjacent).get - 1
            newIndegrees = newIndegrees.updated(adjacent, newIndeg)
            // If in-degree becomes zero, add to sources
            if (newIndeg == 0) {
              newSources = newSources + adjacent
            }
          }
  
          processSources(newSources, newIndegrees, newTopOrder, cnt + 1)
        })
      }
      else if (cnt != graph.nodes.size) {
        throw new Error("There is a cycle in the graph.")
      }
      else {
        topOrder.reverse #:: Stream.empty[List[graph.NodeT]]
      }
    }
  
    processSources(getSources(), indegree, List[graph.NodeT](), 0)
  }
  </code></pre>
  
  <p>Now, i can generate all (or only a few) topological orderings as follows:</p>
  
  <pre><code>val graph: Graph[Int, DiEdge] = Graph(2 ~&gt; 4, 2 ~&gt; 7, 4 ~&gt; 5)
  allTopologicalSorts(graph) foreach println
  </code></pre>
  
  <p><em>How can i make the algorithm tail recursive but still lazy?</em></p>