/**
 * A basic graph trait, with a Node type and an EdgeData type (used to form the triple (Node, Node, EdgeData))
 * @tparam Node The type of the nodes in the graph
 * @tparam EdgeData The data associated with a particular edge between two nodes.
 */
trait Graph[Node, EdgeData] {
  type Edge = (Node, Node, EdgeData)

  def addNode(node: Node): Graph[Node, EdgeData]
  val nodes: List[Node]

  def addEdge(n1: Node, n2: Node, dat: EdgeData): Graph[Node, EdgeData]
  val edges: List[Edge]
}

/**
 * An extension of the graph trait, where each node is itself a graph.
 *
 * @tparam Node The type of the nodes in the graph (which itself must be a graph)
 * @tparam EdgeData The data associated with a particular edge between two nodes
 */
trait RecursiveGraph[Node <: RecursiveGraph[Node, EdgeData], EdgeData] extends Graph[Node, EdgeData]

/**
 * A simple implementation of an immutable graph
 * @tparam Node The type of the nodes in the graph
 * @tparam EdgeData The data associated with a particular edge between two nodes.
 */
sealed class ImmutableGraph[Node, EdgeData] extends Graph[Node, EdgeData] {
  outer: ImmutableGraph[Node, EdgeData] =>

  val nodes = List.empty[Node]
  val edges = List.empty[Edge]

  final def addNode(node: Node) = new ImmutableGraph[Node, EdgeData] {
    override val nodes = node :: outer.nodes
    override val edges = outer.edges
  }

  final def addEdge(n1: Node, n2: Node, dat: EdgeData) = new ImmutableGraph[Node, EdgeData] {
    override val nodes = outer.nodes
    override val edges = (n1, n2, dat) :: outer.edges
  }