Topological sorting of lists related to a graph in Scala

Question

I have a graph structure as follows:

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
}

Now I want to sort a list containing other class instances which contain nodes topologically related to the graph:

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

I'm using sortWith on a List with the ordered-method of the graph.

The output is:

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

this is wrong, because f is after e in the graph.

So why is this wrong? Is the ordered-method wrong? Or did I do other mistakes?

Thanks in advance.

Answer 1

I came up with implementing an Ordering based on an topological sort of the graph:

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

If you quickly "debug" your Graph.ordered method:

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
}

you'll notice that f and e are not compared directly:

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

Taking the comment of MvG into account, I assume that this is due to the assumption that the ordering is total - which yours isn't. However, I wasn't able to find a reference that makes this assumption explicit, neither for any SeqLike method, which is where sortWith comes from, nor for java.util.Arrays.sort, which sortWith seems to use internally.