Determined topological order in scala

Question

I use the scala-graph library to build the radiation pattern and to extract its nodes in a topological order. Since there can be many possibilities for the topological order of the graph, I need a deterministic result for the topological order for graphs that are equal and constructed in the same way.

This small application 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 application displays false.

Is there a way to build a deterministic topological view of the graph using the scala -graph library api? Writing an algorithm from scratch is my last option.

Answer 1

According to the implementation of the function in github, nodes are assembled using the ComponentTraverser , which is obtained using

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

Then topologicalSort is called on it. You can force topological sorting to be deterministic by pointing to the value of your nodes to get a ComponentTraverser , and then call the sorting function yourself. The solution has not been verified.