treadstone90

trait PTopDownUpdater extends FrontierUpdater {
 
  def update(frontier: Seq[Int], parents: Array[Int]): Seq[Int] = {
    val next = ArrayBuffer[Int]()
 
    frontier.par.foreach { node =>
      graph.getNeighbors(node).filter(parents(_) == -1).foreach { neighbor =>
        next += neighbor
        parents(neighbor) = node
      }

treadstone90

trait ParallelAncestorManager {
  def getAncestor(id: Int): ParSeq[Int]
  def getParVertices: ParSeq[Int]
}

trait PBottomUpUpdater extends FrontierUpdater with ParallelAncestorManager {

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

treadstone90

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 {

treadstone90

class BFS(g: Graph) {

  val parent = ArrayBuffer.fill(g.numberVertices)(-1).toArray

  def bfs(source: Int, updater: (Seq[Int], Array[Int]) => Seq[Int]) = {
    var frontier = Seq(source)
    parent(source) = -2

    while (!frontier.isEmpty) {
      frontier = updater(frontier, parent)