Blog BFS bottom up

bottom-up.scala

trait DirectedSerialAncestorManager extends SerialAncestorManager{
  var _graph: SerialDirectedGraph = _
  def getAncestor(id: Int): IndexedSeq[Int] = {
    _graph.getParents(id)
  }

  def getVertices: IndexedSeq[Int] = (0 to _graph.numberVertices - 1)
}

trait SBottomUpUpdater extends FrontierUpdater with SerialAncestorManager {

  def update(frontier: BitSet, parents: Array[Int]): Seq[Int] = {
    val next = mutable.BitSet()
    val vertices = getVertices
    val frontierSet = frontier.toSet

    (vertices.filter(parents(_) == -1)).foreach { node =>
      val neighbors = (getAncestor(node))

      neighbors.find(frontierSet) match {
        case Some(ancestor) => {
          parents(node) = ancestor
          next(node) = true
        }
        case None => None
      }
    }
    next.toBuffer
  }
}