Deterministyczny porządek topologiczny w scala graph

Question

Używam biblioteki scala-graph do budowania wykresu kierunkowego i do pobierania jego węzłów w porządku topologicznym. Ponieważ może istnieć wiele możliwości dla kolejności topologicznej wykresu, muszę mieć deterministyczny wynik dla porządku topologicznego dla wykresów, które są równe i zbudowane w ten sam sposób.

Ta niewielka aplikacja podkreśla 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)) 
} 

Ta aplikacja drukuje fałszywe.

Czy istnieje sposób na zbudowanie deterministycznego topologicznego rodzaju wykresu przy użyciu api biblioteki scala-graph? Pisanie algorytmu od zera byłoby ostatnią opcją.

Answer 1

Według realizacji funkcji on github, węzły są zbierane za pomocą ComponentTraverser który jest otrzymywany z

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

Następnie topologicalSort nazywa się na nim. Możesz zmusić sortowanie topologiczne do determinizmu, podając kolejność na wartości swoich węzłów, aby uzyskać ComponentTraverser, a następnie wywołaj funkcję sortowania samodzielnie. Rozwiązanie nie testowane jednak.