0

我有一个图结构如下：

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

我在一个 List 上使用 sortWith 和图形的有序方法。

输出是：

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

这是错误的，因为f在图中的e之后。

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

提前致谢。

4

2 回答 2

4

如果您快速“调试”您的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哪里的任何方法，也不是对于似乎在内部使用的 for 。sortWithjava.util.Arrays.sortsortWith

于 2012-07-02T11:24:30.150 回答
0

我想出了基于图的拓扑排序实现排序：

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
}
于 2012-07-02T18:17:37.087 回答