Draft of inductive graph implementation in Scala based on http://web.engr.oregonstate.edu/~erwig/papers/InductiveGraphs_JFP01.pdf

Example.scala

import graph._

object Main { 
  def main(args: Array[String]): Unit = {
    println(" Exploring the graph ")

    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


    println(sample.isEmpty)
    println(sample.size)
    println(sample)

    println(sample.matchNode(Node(5)))
    println(sample.matchNode(Node(2)))

    def mappin(c: Context[String, String]): Context[String, String] = 
      Context(c.in, Node(c.node.id*100), c.content, c.out)
    println(sample.map(mappin))

    def countin(c: Context[String, String], acc: Int): Int = 1 + acc
    println(sample.ufold(0, countin)) 

    println(sample.nodes)

    println(sample.successors(Node(2)))
    
    val more = sample.add("d")
    println(more)

    val conn = more.connect(Node(1), Node(3), "newest")
    println(conn)
  }
  
}

InductiveGraph.scala

package graph 

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])

// defining the graph structure
sealed abstract class Graph[+A, +B] {
  def isEmpty: Boolean

  // todo: handle & operator as per paper definition
  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)
  }

  /*
   * Both regular and worst case kind of suck for this one...
   */
  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 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] = {
    val c = Context(Adj[B](List()), Node(1), n, Adj[B](List()))
    new &:(c, t)
  }

}