Last active
January 27, 2018 21:56
-
-
Save jvz/b603ef675e64c153fbe543371d93c6b8 to your computer and use it in GitHub Desktop.
Minimal implementation of a covariant graph abstract data type using adjacency lists
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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) | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment