scala图中的确定性拓扑顺序

Question

我正在使用scala-graph库来构建方向图并以拓扑顺序检索其节点.由于图的拓扑顺序可能存在许多可能性,因此我需要对于相同且以相同方式构建的图的拓扑顺序具有确定性结果.

这个小应用程序突出了这个问题

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

这个应用程序打印错误

有没有办法使用scala-graph库的api构建确定性的拓扑排序图？从头开始编写算法将是我的最后选择.

Answer 1

根据github上的功能实现该函数的实现，节点是使用a来聚集的，aComponentTraverser是通过以下方式获得的

\n\n

def componentTraverser(parameters: Parameters = Parameters(), subgraphNodes: (NodeT) \xe2\x87\x92 Boolean = anyNode, subgraphEdges: (EdgeT) \xe2\x87\x92 Boolean = anyEdge, ordering: ElemOrdering = noOrdering): ComponentTraverser\n

\n\n

然后topologicalSort调用它。您可以通过对节点的值进行排序来强制拓扑排序具有确定性，以获得 a ComponentTraverser，然后自己调用排序函数。解决方案尚未经过测试。

\n