scala - 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

根据函数on github的实现，使用 ComponentTraverser 收集节点这是获得的

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

然后是 topologicalSort被称为它。您可以通过对节点的值进行排序来获得 ComponentTraverser，从而强制拓扑排序具有确定性。然后自己调用排序函数。虽然没有测试解决方案。