LARA

package minijava.controlflow
 
/** Mutable Directed Graph with Labels */
abstract trait LabeledDirectedGraph[LabelType] {
  /** The type of the vertices */
  type Vertex
  /** The type of the edges */
  type Edge
  /** The vertices */
  def V: Set[Vertex]
  /** The edges */
  def E: Set[Edge]
  /** Adds a new vertex to the graph */
  def newVertex: Vertex
  /** Adds a new labeled edge between two vertices */
  def += (from: Vertex, lab: LabelType, to: Vertex)
  /** Returns the set of incoming edges for a given vertex */
  def inEdges(v: Vertex): Set[Edge]
  /** Returne the set of outgoing edges for a given vertex */
  def outEdges(v: Vertex): Set[Edge]
  /** Removes an edge from the graph */
  def -= (from: Vertex, lab: LabelType, to: Vertex)
  /** Generates a new, isomorphic labeled directed graphs where the new labels
   * are obtained by mapping the function to the existing ones */
  def labelMap[NewLabel](f: LabelType => NewLabel): LabeledDirectedGraph[NewLabel]
}
 
/** A concrete yet type-paremetric implementation */
class LabeledDirectedGraphImp[LabelType] extends LabeledDirectedGraph[LabelType] {
  /** Inner class to define vertices. Later exposed through the type member Vertex. */
  case class VertexImp[L](var name: String) {
    var in: Set[EdgeImp[L]] = Set[EdgeImp[L]]()
    var out: Set[EdgeImp[L]] = Set[EdgeImp[L]]()
    override def toString = name
  }
  /** Inner class to define edges. Later exposed through the type member Vertex. */
  case class EdgeImp[L](v1: VertexImp[L], lab: L, v2: VertexImp[L]) {
    val name = EdgeCounter.getNew
    override def toString = name + ":" + v1 + "-" + lab + "-" + v2
  }
 
  object EdgeCounter {
    var count = 0
    def getNew: String = {
      count = count + 1
      ("e" + count)
    }
  }
 
  type Vertex = VertexImp[LabelType]
  type Edge = EdgeImp[LabelType]
 
  private var vertices = Set[Vertex]()
  private var edges = Set[Edge]()
  def V = vertices
  def E = edges
 
  var counter = 0
  def newVertex = { 
    counter = counter + 1
    new Vertex("v" + counter)
  }
 
  def +=(from: Vertex, lab : LabelType, to: Vertex) = {
    val edge = EdgeImp[LabelType](from, lab, to)
    edges += edge
    vertices += from
    vertices += to
    from.out += edge
    to.in += edge
  }
 
  def -=(from: Vertex, lab: LabelType, to: Vertex) = {
    val edge = EdgeImp[LabelType](from, lab, to)
    edges -= edge
    vertices -= from
    vertices -= to
    from.out -= edge
    to.in -= edge
  }
 
  def inEdges(v: Vertex)  = v.in
  def outEdges(v: Vertex) = v.out
 
  def labelMap[NewLabel](f: LabelType => NewLabel): LabeledDirectedGraphImp[NewLabel] = {
    val g = new LabeledDirectedGraphImp[NewLabel]
    var vertexMap = Map[Vertex, g.Vertex]()
    for (v <- vertices) {
      vertexMap += ((v, g.newVertex))
    }
    for (e <- edges) {
      g += (vertexMap(e.v1), f(e.lab), vertexMap(e.v2))
    }
    g
  }
 
  /** For visualization purposes. */
  override def toString: String = edges.toList.map(_.toString).mkString("{ ", ", ", " }")
 
  /** The following method prints out a string readable using GraphViz. */
  def toDotString: String = {
    var res: StringBuffer = new StringBuffer()
    def emit(s: String) = res.append(s)
    def arrow(x: String, y: String) = {
      emit("  "); emit(x); emit(" -> "); emit(y); emit(";\n")
    }
 
    def makeBoxed(id : String, name : String) = {
      emit(id); emit("[shape=box,color=lightblue,style=filled,label=\""); 
      emit(name); emit("\"];\n")
    }
 
    emit("digraph D {\n")
    edges.foreach(edge => {
      arrow(edge.v1.name, edge.name)
      arrow(edge.name, edge.v2.name)
      makeBoxed(edge.name, edge.lab.toString)
    })
    emit("}\n") 
    res.toString
  }
 
  /** Writes the graph to a file readable with GraphViz. */
  def writeDottyToFile(fname: String): Unit = {
    import java.io.{BufferedWriter, FileWriter}
    val out = new BufferedWriter(new FileWriter(fname))
    out.write(toDotString)
    out.close
  }
 
  /** If you have installed the GraphViz utilities, you can also try
   * directly viewing the generated file using one of the two following
   * methods. */
  def dotGvView: Unit = {
    writeDottyToFile(dotFileName)
    exec("dot " + dotFileName + " -Tps -o" + psFileName)
    exec("gv " + psFileName)
  }
 
  def dottyView: Unit = {
    writeDottyToFile(dotFileName)
    exec("dotty " + dotFileName)
  }
 
  private val dotFileName = "graph.dot"
  private val psFileName = "graph.ps"
 
  private def exec(command: String): Unit = Runtime.getRuntime.exec(command)
}