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

グラフのordered-methodを使用してリストで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。これは、どこsortWithから来たのか、内部で使用されているjava.util.Arrays.sortとsortWith思われる のメソッドでもありません。

于 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 に答える