Dijkstra meets Scala meets ScalaFX

A quick post for an naive implementation of Dijkstra in Scala and a visual representation of the solution using FXML and ScalaFX.
I have first defined a graph and a vertex class as follows:

case class Coordinates(val x: Int, val y: Int)

class Vertex(val id: String, val coords: Coordinates) {
  def dist(v: Vertex):Double = dist(v.coords.x, v.coords.y)
  def dist(x: Int, y: Int):Double = Math.sqrt(
    Math.pow(coords.x - x, 2) + Math.pow(coords.y - y, 2))
  override def toString = s"V($id)@$coords"
}

class Graph(val vertices: Seq[Vertex], val neighbours: Map[Vertex, Seq[Vertex]]) {
  def +(v: Vertex):Graph = new Graph(v +: vertices, neighbours) // adds a vertex to the graph
  def ~(v: Vertex, n: Vertex):Graph = { // sets a neighbour relationship between two vertices
    val g = new Graph(vertices, neighbours + (v -> (neighbours(v) :+ n)))
    new Graph(g.vertices, g.neighbours + (n -> (g.neighbours(n) :+ v)))
  }
  def closest(x: Int, y: Int): Vertex = vertices.minBy( v => v.dist(x, y))
  override def toString = s"G(Vertices: $vertices, Neighbours: $neighbours)"
}

Then comes my Scala version of Dijkstra (would be nice to share your version...)

object Dijkstra {
  def run(graph: Graph, source: Vertex, target: Vertex):Seq[Vertex] = {
    val neighbours = graph.neighbours

    def dj2(u: Vertex, vs: Seq[Vertex], distances: Map[Vertex, Double], queue: Seq[Vertex],
            visited: Seq[Vertex], previous: Map[Vertex, Vertex]):
    (Map[Vertex, Double], Seq[Vertex], Seq[Vertex], Map[Vertex, Vertex]) = {
      if (!vs.isEmpty) {
        val v = vs.head
        val alt = distances(u) + u.dist(v)
        if (alt < distances(v) && !visited.contains(v)) {
          dj2(u, vs.tail, distances + (v -> alt), v +: queue, visited, previous + (v -> u))
        } else if (!vs.tail.isEmpty) {
          dj2(u, vs.tail, distances, queue, visited, previous)
        } else (distances, queue, visited, previous)
      } else (distances, queue, visited, previous)
    } // dj2

    def dj1(distances: Map[Vertex, Double], queue: Seq[Vertex], visited: Seq[Vertex], previous: Map[Vertex, Vertex]):Seq[Vertex] = {
      if (!queue.isEmpty) {
        val u:Vertex = queue.filter(v => {!visited.contains(v)}).min(Ordering.by((v:Vertex) => distances(v)))
        if (u == target) {
          sequenceSol(previous, target)
        } else {
          val res = dj2(u, neighbours(u), distances, queue.filterNot(v => v.id == u.id), u +: visited, previous)
          dj1(res._1, res._2, res._3, res._4)
        }
      } else Seq()
    } // dj1

    dj1(Map(source -> 0.0) withDefaultValue Double.MaxValue, Seq(source), Seq(), Map())
  } // dijkstra

  def sequenceSol(previous: Map[Vertex, Vertex], to: Vertex): Seq[Vertex] = {
    def helper(seq: Seq[Vertex], current: Vertex): Seq[Vertex] =
      if (previous.contains(current)) helper(previous(current) +: seq, previous(current)) else seq
    helper(Seq(to), to)
  }
}

I would like to find a simpler version.. really. The FXML is a simple file like this:

<?xml version="1.0" encoding="UTF-8"?>

<?import java.lang.*?>
<?import java.util.*?>
<?import javafx.scene.control.*?>
<?import javafx.scene.layout.*?>
<?import javafx.scene.paint.*?>

<AnchorPane id="AnchorPane" fx:id="masterAnchorPane" maxHeight="-Infinity" maxWidth="-Infinity" minHeight="-Infinity" minWidth="-Infinity" prefHeight="400.0" prefWidth="600.0" xmlns:fx="http://javafx.com/fxml/1" xmlns="http://javafx.com/javafx/2.2" fx:controller="org.jts.dijkstra.DijkstraController">
  <children>
    <BorderPane fx:id="borderPane" prefHeight="400.0" prefWidth="600.0" style="-fx-background-color: #CCFF99" AnchorPane.bottomAnchor="0.0" AnchorPane.leftAnchor="0.0" AnchorPane.rightAnchor="0.0" AnchorPane.topAnchor="0.0">
      <top>
        <FlowPane minHeight="21.0" prefHeight="21.0" prefWidth="600.0">
          <children>
            <TextField fx:id="nbNodes" alignment="CENTER_RIGHT" prefWidth="50.0" promptText="# nodes" text="100" />
            <Button fx:id="applyButton" mnemonicParsing="false" onAction="#handleApply" text="Apply" />
          </children>
        </FlowPane>
      </top>
    </BorderPane>
  </children>
</AnchorPane>

And finally the controller:

package org.jts.dijkstra

import javafx.fxml.{Initializable, FXML}
import javafx.scene.{control => jfxctrl}
import javafx.scene.{layout => jfxlyt}
import javafx.{event => jfxe}
import scalafx.scene.effect.Bloom
import scalafx.scene.paint.Color
import scalafx.scene.{layout => scxlyt}
import scalafx.scene.{control => scxctrl}
import java.net.URL
import javafx.event.EventHandler
import javafx.scene.input.MouseEvent

object Constants {
  val nodeSize = 16
  val width = 1500
  val height = 800
}

class DijkstraController extends Initializable {
  @FXML private var nbNodes: jfxctrl.TextField = null
  @FXML private var applyButton: jfxctrl.Button = null
  @FXML private var borderPane: jfxlyt.BorderPane = null
  @FXML private var masterAnchorPane: jfxlyt.AnchorPane = null

  private var scxMasterPane: scxlyt.AnchorPane = null
  private var scxPane: scxlyt.BorderPane = null
  private var scxNbNodes: scxctrl.TextField = null
  private var scxApplyButton: scxctrl.Button = null
  private var scxCanvas: scalafx.scene.canvas.Canvas = null

  private var fromVertex: Option[Vertex] = None
  private var toVertex: Option[Vertex] = None

  override def initialize(url: URL, rb: java.util.ResourceBundle) {
    require(masterAnchorPane != null, "masterAnchorPane must not be null")
    scxMasterPane = new scxlyt.AnchorPane(masterAnchorPane)

    require(nbNodes != null, "nbNodes must not be null")
    scxNbNodes = new scxctrl.TextField(nbNodes)

    require(applyButton != null, "applyButton must not be null")
    scxApplyButton  = new scxctrl.Button(applyButton)

    require(borderPane != null, "centerPane must not be null")
    scxPane = new scxlyt.BorderPane(borderPane)

    scxCanvas = new scalafx.scene.canvas.Canvas(Constants.width, Constants.height)
    scxPane.setCenter(scxCanvas)
  }

  @FXML private def handleApply(event: jfxe.ActionEvent) {
    // TODO In Future not in EDT
    val maxNodes:Integer = scxNbNodes.getText.toInt
    val width = scxCanvas.width.toInt
    val height = scxCanvas.height.toInt
    println(s"Generating random graph with $maxNodes in ($width, $height)")

    val random = new java.util.Random
    val vertices = for(i <- 0 until maxNodes) yield {
      val x = random.nextInt(width)
      val y = random.nextInt(height)
      val vertex = new Vertex(s"v-$i", Coordinates(x, y))
      vertex
    }
    println(s"Generated vertices $vertices")

    def generateNeighbours(neighbours: Map[Vertex, Seq[Vertex]], nbTimes: Int): Map[Vertex, Seq[Vertex]] = {
      if (nbTimes >= maxNodes) neighbours
      else {
        val v1 = vertices(random.nextInt(maxNodes))
        val v2 = vertices(random.nextInt(maxNodes))
        val n1 = neighbours + (v1 -> (neighbours(v1) :+ v2))
        val n2 = n1 + (v2 -> (n1(v2) :+ v1))
        generateNeighbours(n2, nbTimes + 1)
      }
    }

    val neighbours = generateNeighbours(Map() withDefaultValue Seq(), 0)
    println(s"Generated neighbours $neighbours")

    val graph = new Graph(vertices, neighbours)
    drawGraph(graph)
    addMouseEventHandler(graph)
  }

  private def drawGraph(g: Graph, sol: Seq[Vertex] = Seq()) {
    val gc = scxCanvas.getGraphicsContext2D
    gc.clearRect(0, 0, Constants.width, Constants.height)
    gc.setFill(Color.BLACK)
    gc.fillRect(0, 0, Constants.width, Constants.height)

    gc.setFill(Color.LIGHTYELLOW)
    gc.setEffect(new Bloom())
    g.vertices.foreach(v => {
      gc.fillOval(v.coords.x, v.coords.y, Constants.nodeSize, Constants.nodeSize)
    })

    gc.setEffect(null)
    val offset = Constants.nodeSize / 2
    gc.setStroke(Color.LIGHTBLUE)
    g.neighbours.foreach(t => {
      val from = t._1
      t._2.foreach(to => {
        gc.strokeLine(from.coords.x + offset, from.coords.y + offset, to.coords.x + offset, to.coords.y + offset)
        gc.setLineWidth(1.0)
      })
    })

    if (!sol.isEmpty) {
      gc.setFill(Color.RED)
      gc.setStroke(Color.GREEN)
      gc.setEffect(new Bloom())
      val from = sol(0)
      val to = sol.last
      gc.fillOval(from.coords.x, from.coords.y, Constants.nodeSize, Constants.nodeSize)
      gc.fillOval(to.coords.x, to.coords.y, Constants.nodeSize, Constants.nodeSize)
      val path = sol.sliding(2, 1)

      gc.setLineWidth(5.0)
      while(path.hasNext) {
        val subPath = path.next
        if (subPath.size == 2) {
          val f = subPath(0)
          val t = subPath(1)
          gc.strokeLine(f.coords.x + offset, f.coords.y + offset, t.coords.x + offset, t.coords.y + offset)
        }
      }
    }
  }

  private def addMouseEventHandler(g: Graph) {
    scxCanvas.addEventHandler(MouseEvent.MOUSE_CLICKED, new EventHandler[MouseEvent]() {
      override def handle(me: MouseEvent) = {
        val closestVertex = g.closest(me.getX.toInt, me.getY.toInt)
        //println(s"Original vertex: $closestVertex")
        fromVertex = Some(closestVertex)
      }
    })

    scxCanvas.addEventHandler(MouseEvent.MOUSE_MOVED, new EventHandler[MouseEvent]() {
      override def handle(me: MouseEvent) = {
        val closestVertex = g.closest(me.getX.toInt, me.getY.toInt)
        //println(s"Closest vertex: $closestVertex")
        val oldToVertex = toVertex
        toVertex = Some(closestVertex)
        if (!oldToVertex.equals(toVertex)) runDijkstra(g)
      }
    })
  }

  private def runDijkstra(g: Graph) {
    (fromVertex, toVertex) match {
      case (Some(f), Some(t)) => {
        val sol = Dijkstra.run(g, f, t)
        drawGraph(g, sol)
        println(s"Sol from $f to $t is $sol")
      }
      case _ =>
    }
  }
}

I am still trying to grasp ScalaFX - but looks ok so far. Full source code available on request. Just email me.