Minimal implementation of a covariant graph abstract data type using adjacency lists

Graph.scala

package graph

trait Graph[+A] {
  def isEmpty: Boolean

  def size: Int

  def contains[A0 >: A](vertex: A0): Boolean

  def +[A0 >: A](vertex: A0): Graph[A0]

  def -[A0 >: A](vertex: A0): Graph[A0]

  def contains[A0 >: A](edge: (A0, A0)): Boolean

  def +[A0 >: A](edge: (A0, A0)): Graph[A0]

  def -[A0 >: A](edge: (A0, A0)): Graph[A0]

  def adjacencies[A0 >: A](vertex: A0): Seq[A0]
}

object Graph {
  def empty[A]: Graph[A] = new LinkedGraph[A](Nil)

  def ofVertices[A](vertices: A*): Graph[A] =
    vertices.foldLeft(empty[A])(_ + _)
}

private[graph] class LinkedGraph[+A](val graph: List[(A, List[A])]) extends Graph[A] {
  override def isEmpty: Boolean =
    graph.isEmpty

  override def size: Int =
    graph.size

  override def contains[A0 >: A](vertex: A0): Boolean =
    graph exists (_._1 == vertex)

  override def +[A0 >: A](vertex: A0): Graph[A0] =
    if (this contains vertex) this else new LinkedGraph[A0]((vertex, Nil) :: graph)

  override def -[A0 >: A](vertex: A0): Graph[A0] =
    if (!(this contains vertex)) this else new LinkedGraph[A0](
      graph.withFilter {
        case (`vertex`, _) => false
        case _ => true
      }.map {
        case (a, bs) => (a, bs filterNot (_ == vertex))
      }
    )

  override def contains[A0 >: A](edge: (A0, A0)): Boolean = {
    import edge.{_1, _2}
    graph.exists {
      case (a, bs) => a == _1 && (bs contains _2)
    }
  }

  override def +[A0 >: A](edge: (A0, A0)): Graph[A0] = {
    import edge.{_1, _2}
    if ((this contains _1) && (this contains _2) && !(this contains edge)) {
      val updatedGraph = graph.map {
        case (`_1`, bs) => (_1, _2 :: bs)
        case other => other
      }
      new LinkedGraph[A0](updatedGraph)
    } else this
  }

  override def -[A0 >: A](edge: (A0, A0)): Graph[A0] =
    if (this contains edge) {
      import edge.{_1, _2}
      val updatedGraph = graph.map {
        case (`_1`, bs) => (_1, bs filterNot (_ == _2))
        case other => other
      }
      new LinkedGraph[A0](updatedGraph)
    } else this

  override def adjacencies[A0 >: A](vertex: A0): Seq[A0] =
    graph.find(_._1 == vertex).map(_._2).getOrElse(Seq.empty)
}