Scala grafiğinde deterministik topolojik düzen

Question

Yön grafik oluşturmak ve düğümlerini topolojik olarak almak için scala-graph kütüphanesini kullanıyorum. Bir grafiğin topolojik düzeni için birçok olasılık olabileceğinden, aynı şekilde eşit ve aynı şekilde oluşturulmuş grafikler için topolojik sıraya göre deterministik bir sonuca ihtiyacım var.

Bu küçük uygulama sorunu yanlış

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)) 
} 

Bu uygulama baskılar vurgular.

Scala-grafik kitaplığı api kullanarak bir grafiğin deterministik topolojik sıralamasını oluşturmanın bir yolu var mı? Bir algoritmanın yazımının sıfırdan yazılması benim son seçeneğim olurdu.

Answer 1

fonksiyonu on github uygulanmasına göre, düğümler sonra topologicalSort üzerinde adlandırılır

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

ile elde edilir ComponentTraverser kullanılarak toplanmıştır. Topolojik sıralama, düğümlerinizin değerini bir ComponentTraverser almak için sipariş vererek ve sonra sıralama işlevini kendiniz çağırıp deterministik olmaya zorlayabilir. Çözüm yine de test edilmedi.