Топологическая сортировка списков, связанная с графом в Scala

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) 

это неправильно, потому что е после е в графе.

Так почему же это неправильно? Является ли метод заказа неправильным? Или я делал другие ошибки?

Заранее спасибо.

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, по-видимому, используется внутренне.