trait Graph[G <: AnyRef] extends Equal[G]{ self =>

  def vertices(g: G): Iterable[Int]
  def edges(g: G): Iterable[Int]

  /** The order of the graph. This is equal to the number of vertices stored.
    *
    * WARNING: Will not complete for graphs where |V| is functionally infinite.
    *
    * @return The number of vertices in the graph
    */
  def order(g: G): Int = vertices(g).size

  /** The size of the graph. This is equal to the number of edges stored.
    *
    * WARNING: Will not complete for graphs where |E| is functionally infinite.
    *
    * @return The number of edges in the graph
    */
  def size(g: G): Int = edges(g).size

  def findVertex[V : Vertex](g: G)(f: V => Boolean): Option[V]

  def findEdge[E[_, _] : Edge](g: G)(f: E => Boolean): Option[E]

  def plusVertex[V : Vertex](g: G, v: V): G

  def minusVertex[V : Vertex](g: G, v: V): G

  def plusEdge[E[_, _] : Edge](g: G, e: E): G

  def minusEdge[E[_, _] : Edge](g: G, e: E): G

  override def equal(g1: G, g2: G) = {
    import scalaz.std.iterable._
    (g1 eq g2) ||
      ((self.order(g1) === self.order(g2)) &&
        (self.size(g1) === self.size(g2)) &&
        (self.vertices(g1) === self.vertices(g2)) &&
        (self.edges(g1) === self.vertices(g2)))

    //Last two === cannot be resolved
  }
}