列出的拓扑排序相关的图表斯卡拉

Question

我有一个图结构如下：

class Graph { 
    private var nodes: Set[Node] = Set.empty[Node] 
    def addEdges(edges: (Node, Node)*) { 
    for ((a, b) <- edges) { 
     nodes ++= List(a, b) 
     a addDst b 
    } 
    } 

    override def toString = { 
    val sb = new StringBuilder 
    for (node <- nodes if node.dst.toList.sortWith(ordered).nonEmpty) 
     sb ++= "%s -> %s\n" format (node.toString, node.dst.mkString(", ")) 
    sb.toString 
    } 

    def ordered(a: Node, b: Node): Boolean = { 
    var dst = a.dst 
    while (dst.nonEmpty) { 
     if (dst contains b) 
     return true 
     dst = dst.flatMap(_.dst) 
    } 
    return false 
    } 
} 

trait Node { 
    def dst = _dst 
    private var _dst: Set[Node] = Set.empty[Node] 
    def addDst(that: Node) { 
    this._dst += that 
    } 
} 

class CharNode(val n: Char) extends Node { 
    override def toString = n.toString 
} 

现在我想排序含含拓扑关系图中的节点其它类实例的列表：

object Main extends App { 
    val graph = new Graph 
    val d = new CharNode('d') 
    val e = new CharNode('e') 
    val f = new CharNode('f') 
    val g = new CharNode('g') 
    val i = new CharNode('i') 
    val l = new CharNode('l') 

    graph.addEdges(
    d -> l, 
    e -> i, 
    i -> f, 
    f -> g 
) 

    case class Other(s: String, node: Node) 

    val other = List(Other("wb2", f), Other("wa1", d), Other("wb1", e)) 
    println(other.sortWith { case (o1, o2) => graph.ordered(o1.node, o2.node) }.mkString("\n")) 
} 

我在图表的有序方法上使用sortWith。

的输出是：

Other(wb2,f) 
Other(wa1,d) 
Other(wb1,e) 

这是错误的，因为˚F是后在图中ë。

那么为什么这是错的？有序方法是否错误？还是我犯了其他错误？

在此先感谢。

Answer 1

我想出了实施基于一个拓扑排序图表的排序：

object Main extends App { 
    val graph = new Graph 
    val d = new CharNode('d') 
    val e = new CharNode('e') 
    val f = new CharNode('f') 
    val g = new CharNode('g') 
    val i = new CharNode('i') 
    val l = new CharNode('l') 

    graph.addEdges(
    d -> l, 
    e -> i, 
    i -> f, 
    f -> g 
) 

    case class Other(s: String, node: Node) 

    val other = List(Other("wb2", f), Other("wa1", d), Other("wb1", e)) 
    println(other.sorted(graph.ordering[Other](_.node)).mkString("\n")) 

} 

class Graph { 
    private var nodes: Set[Node] = Set.empty[Node] 
    def addEdges(edges: (Node, Node)*) { 
    for ((a, b) <- edges) { 
     nodes ++= List(a, b) 
     a addDst b 
    } 
    } 

    def ordering[T](f: T => Node = (x: Node) => x) = { 
    import collection.mutable 
    val inDegrees = mutable.HashMap.empty ++ nodes.map(n => n -> n.src.size) 
    val sorted = new mutable.ListBuffer[Node]() 
    val zeroInDegree = mutable.Stack[Node]() 
    zeroInDegree pushAll inDegrees.filter(_._2 == 0).keys 
    while (zeroInDegree.nonEmpty) { 
     val next = zeroInDegree.pop 
     sorted += next 

     for (after <- next.dst) { 
     val count = inDegrees(after) - 1 
     if (count == 0) zeroInDegree push after 
     inDegrees(after) = count 
     } 
    } 

    assert(sorted.toSet == nodes) 

    new Ordering[T] { 
     val lookup = (sorted zipWithIndex).toMap 
     def compare(a: T, b: T) = lookup(f(a)) compare lookup(f(b)) 
    } 
    } 
} 

trait Node { 
    var dst: Set[Node] = Set.empty[Node] 
    var src: Set[Node] = Set.empty[Node] 
    def addDst(that: Node) { 
    this.dst += that 
    that.src += this 
    } 
} 

class CharNode(val n: Char) extends Node { 
    override def toString = n.toString 
} 

Answer 2

如果迅速 “调试” 你Graph.ordered方法：

def ordered(a: Node, b: Node): Boolean = { 
    println("[ordered] a = %s, b = %s".format(a, b)) 
    var dst = a.dst 
    while (dst.nonEmpty) { 
    if (dst contains b) 
     return true 
    dst = dst.flatMap(_.dst) 
    } 
    return false 
} 

你会发现f和e不直接进行比较：

[ordered] a = d, b = f 
[ordered] a = f, b = d 
[ordered] a = e, b = d 
[ordered] a = d, b = e 

以MVG的意见考虑在内，我假设这是由于排序是全部的假设 - 你的不是。但是，我无法找到一个明确的假设，对于任何SeqLike方法（其中sortWith来自哪个方法）以及java.util.Arrays.sort（其中sortWith似乎在内部使用）都没有提及。