Demo using Scala generators constructing random instances of InductiveGraph with nodes having an edge to another node with 75% probability.

example.txt

Context(Adj(List((link,Node(-199040622)))), Node(21830181), 21830181, Adj(List((link,Node(-790790003))))) & 
Context(Adj(List((link,Node(-199040622)))), Node(-790790003), -790790003, Adj(List((link,Node(-621672804))))) & 
Context(Adj(List()), Node(-621672804), -621672804, Adj(List())) & 
Context(Adj(List()), Node(-199040622), -199040622, Adj(List())) & 
Empty

GraphGenerator.scala

package graph

trait Generator[+T] {
  self =>
  def generate: T 
  def map[U](f: T => U): Generator[U] = new Generator[U] {
    def generate: U = f(self.generate)
  }
  def flatMap[U](f: T => Generator[U]): Generator[U] = new Generator[U] {
    def generate: U = f(self.generate).generate
  }
}

object GraphGenerator {
  
  val integers = new Generator[Int] {
  	val rand = new java.util.Random()
    def generate = rand.nextInt
  }
  
  val floats = new Generator[Float] {
  	val rand = new java.util.Random()
    def generate = rand.nextFloat
  }
  
  def single[U](x: U) = new Generator[U] {
    def generate = x
  }
  
  def choose(lo: Int, hi: Int): Generator[Int] = 
    for (x <- integers) yield lo + x & (hi - lo)
    
  def oneOf[T](xs: T*): Generator[T] = 
    for (x <- choose(0, xs.length-1)) yield xs(x)

  val boolean = for (x <- integers) yield x > 0
  
  def nodes: Generator[Node] = for (x <- integers) yield Node(x)
  
  def nonEmptyAdjs(g: Graph[String, String]): Generator[Adj[String]] = for {
    node <- oneOf(g.nodes:_*) // tip list over into args
  	adj <- single(Adj(List(("link", node))))
  } yield adj
  
  def emptyAdjs: Generator[Adj[String]] = single(Adj(List()))

  def adjs(g: Graph[String, String]): Generator[Adj[String]] = for {
    isEmpty <- for (x <- floats) yield x < 0.25 // creates a more connected graph
    adj <- if (isEmpty || g.nodes.length <= 1) emptyAdjs else nonEmptyAdjs(g)
  } yield adj
  
  // Context(in, node, nodeval, out)
  def contexts(g: Graph[String, String]): Generator[Context[String, String]] = for {
      in <- adjs(g)
      node <- nodes
      out <- adjs(g)
    } yield Context(in, node, node.id.toString, out)
  
  def nonEmptyGraph: Generator[Graph[String, String]] = for {
    rest <- graphs
    context <- contexts(rest)
  } yield context &: rest
  
  def emptyGraph: Generator[Graph[String, String]] = single(Empty)
  
  def graphs: Generator[Graph[String, String]] = for {
    isEmpty <- for (x <- floats) yield x < 0.25 // creates a larger graph
    graph <- if (isEmpty) emptyGraph else nonEmptyGraph 
  } yield graph
  
  def main(args: Array[String]) {
  	println(graphs.generate)
  }
}

InductiveGraph.scala

package graph 

/**
 * Inductive graph implementation based on Martin Erwig's paper: 
 * http://web.engr.oregonstate.edu/~erwig/papers/InductiveGraphs_JFP01.pdf
 * 
 * Usage example
 *
 * val sample = 
 *     Context(Adj(List(("left", Node(2)), ("up", Node(3)))), 
 *             Node(1), "a", Adj(List(("right", Node(2))))) &:
 *     Context(Adj(List()), Node(2), "b", Adj(List(("down", Node(3))))) &:
 *     Context(Adj(List()), Node(3), "c", Adj(List())) &: 
 *     Empty
 * 
 * val updatedSample = sample.add("d")
 * 
 * val connectedSample = sample.connect(Node(3), Node(4), "new edge")
 */

case class Node(id: Int)
case class Adj[+B](links: List[(B, Node)])
case class Context[+A, +B](in: Adj[B], node: Node, content: A, out: Adj[B])

sealed abstract class Graph[+A, +B] {
  def isEmpty: Boolean

  def &:[C >: A, D >: B](c: Context[C, D]): Graph[C, D] = new &:(c, this)
  
  def :::[C >: A, D >: B](g: Graph[C, D]): Graph[C, D] = g match {
    case Empty => this
    case head &: rest => head &: rest ::: this
  }

  def size: Int = this match {
    case _ &: rest => 1 + rest.size
    case Empty => 0
  }

  def matchNode(n: Node): Option[Context[A, B]] = this match {
    case (ctx @ Context(_, node, _, _)) &: _ if n == node => Some(ctx)
    case _ &: rest => rest.matchNode(n)
    case Empty => None
  }

  def map[C >: A, D >: B](f: Context[C, D] => Context[C, D]): Graph[C, D] = {
    def loop(gg: Graph[C, D], acc: Graph[C, D]): Graph[C, D] = gg match {
      case ctx &: rest => loop(rest, f(ctx) &: acc)
      case Empty => acc
    }
    loop(this, Empty)
  }

  def ufold[T](init: T, f: (Context[A, B], T) => T): T = {
    def loop(gg: Graph[A, B], acc: T): T = gg match {
      case ctx &: rest => loop(rest, f(ctx, acc))
      case Empty => acc
    }
    loop(this, init)
  }

  def nodes[C >: A, D >: B]: List[Node] =
    ufold(List(), (c: Context[C, D], acc: List[Node]) => c.node :: acc)

  def successors(node: Node): List[Node] = {
    def succin(c: Context[A, B], acc: List[Node]): List[Node] =
      c.in.links.foldLeft(List[Node]())((a, i) => 
        if (i._2 == node) c.node :: a 
        else a
      ) ++ acc
    
    val outNodes = this.matchNode(node) match {
      case Some(ctx) => ctx.out.links.map(_._2)
      case None => List[Node]()
    }

    this.ufold(List[Node](), succin) ++ outNodes
  }

  def add[C >: A, D >: B](c: C): Graph[C,D] = 
    Context(in = Adj[D](List()), out = Adj[D](List()),
            node = Node(size+1), content = c ) &: this

  /*
   * Only works if at least one of the nodes exists. Will create edge to non-existing
   * node in case one of the two nodes does not exist. 
   */
  def connect[C >: A, D >: B](from: Node, to: Node, edgeLabel: D): Graph[C, D] = {
    def connector(graph: Graph[C, D], acc: Graph[C, D]): Graph[C, D] = graph match {
      case Context(in, n, con, out) &: rest if n == from => 
        // create outgoing link at from
        val newContext = Context(in, n, con, Adj((edgeLabel, to) :: out.links))
        newContext &: acc ::: rest
      case Context(in, n, con, out) &: rest if n == to => 
        // create incoming link at to
        val newContext = Context(Adj((edgeLabel, from) :: in.links), n, con, out)
        newContext &: acc ::: rest
      case head &: rest => connector(rest, head &: acc)
      case Empty => acc
    }
    connector(this, Empty)
  }
}

case class &:[A, B](c: Context[A, B], g: Graph[A, B]) extends Graph[A, B] {
  override def isEmpty: Boolean = false
  override def toString: String = "Context(" + c.in + ", " + c.node + 
    ", " + c.content + ", " + c.out + ") & \n" + g.toString
}

case object Empty extends Graph[Nothing, Nothing] {
  override def isEmpty: Boolean = true
}

object Graph {
  def empty[A, B]: Graph[A, B] = Empty

  def apply[A, B](n: A, t: Graph[A, B] = Empty): Graph[A, B] =
    new &:(Context(Adj[B](List()), Node(1), n, Adj[B](List())), t)
}