Deterministic topological order in scala graph

Question

I'm using scala-graph library to build directional graph and to retrieve its nodes in topological order. Since there can be many possibilities for a topological order of a graph, I need to have deterministic result for topological order for graphs that are equal and built in the same way.

This small app highlights the problem

import scalax.collection.Graph
import scalax.collection.GraphEdge.DiEdge
import scalax.collection.GraphPredef._

object MainApp extends App {

  // Creates new graph for every call
  // val is not an option
  def graph: Graph[String, DiEdge] = Graph(
    "A" ~> "B",
    "A" ~> "C",
    "A" ~> "D",
    "B" ~> "E",
    "B" ~> "F",
    "C" ~> "G",
    "C" ~> "H",
    "D" ~> "F",
    "D" ~> "G"
  )

  val results = 1 to 20 map { _ =>
    graph.topologicalSort.mkString("")
  }

  println(results.tail.forall(_ == results.head))
}

This app prints false.

Is there a way to build deterministic topological sort of a graph using api of scala-graph library? Writing an algorithm from scratch of doing so would be my last option.

Answer 1

According to the implementation of the function on github, the nodes are gathered using a ComponentTraverser which is obtained with

def componentTraverser(parameters: Parameters = Parameters(), subgraphNodes: (NodeT) ⇒ Boolean = anyNode, subgraphEdges: (EdgeT) ⇒ Boolean = anyEdge, ordering: ElemOrdering = noOrdering): ComponentTraverser

Then the topologicalSort is called on it. You could force the topological sort to be deterministic by giving an ordering on the value of your nodes to get a ComponentTraverser and then call the sort function yourself. Solution not tested though.