Der Weg ist das Ziel – Mit Dijkstra von Java nach Scala


Erst einmal ein Nachtrag zu meinem letzten Beitrag: Auch in teutschen Landen tut sich etwas in Sachen Scala. Noch nicht erschienen ist das Praxisbuch Scala: Programmieren in Scala für Ein- und Umsteiger. In der deutschsprachigen Blogosphäre bin ich auf dieses Scala Blog gestoßen. Es gibt sicher noch mehr, aber bevor ich lang herumsuche, schreibe ich doch lieber selber etwas:

Hier einmal ein etwas längeres Beispiel, wie man Java nach Scala übersetzten (oder sollte ich sagen: „eindampfen“) kann. Als nichttriviales Beispiel habe ich mir Dijkstras Algorithmus ausgesucht, der die kürzesten Wege in einem Graphen sucht.

Schritt eins: Irgendwo Java-Code klauen, z.B. von Literate Programs – eine gute Seite, um mal etwas Beispielcode verschiedener Sprachen anzuschauen.

import java.util.PriorityQueue;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

class Vertex implements Comparable<Vertex>
{
    public final String name;
    public Edge[] adjacencies;
    public double minDistance = Double.POSITIVE_INFINITY;
    public Vertex previous;
    public Vertex(String argName) { name = argName; }
    public String toString() { return name; }
    public int compareTo(Vertex other)
    {
        return Double.compare(minDistance, other.minDistance);
    }
}

class Edge
{
    public final Vertex target;
    public final double weight;
    public Edge(Vertex argTarget, double argWeight)
    { target = argTarget; weight = argWeight; }
}

public class Dijkstra
{
    public static void computePaths(Vertex source)
    {
        source.minDistance = 0.;
        PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
	vertexQueue.add(source);
	while (!vertexQueue.isEmpty()) {
	    Vertex u = vertexQueue.poll();
            // Visit each edge exiting u
            for (Edge e : u.adjacencies)
            {
                Vertex v = e.target;
                double weight = e.weight;
                double distanceThroughU = u.minDistance + weight;
		if (distanceThroughU < v.minDistance) {
		    vertexQueue.remove(v);
		    v.minDistance = distanceThroughU ;
		    v.previous = u;
		    vertexQueue.add(v);
		}
            }
        }
    }

    public static List<Vertex> getShortestPathTo(Vertex target)
    {
        List<Vertex> path = new ArrayList<Vertex>();
        for (Vertex vertex = target; vertex != null; vertex = vertex.previous)
            path.add(vertex);

        Collections.reverse(path);
        return path;
    }

    public static void main(String[] args)
    {
        Vertex v0 = new Vertex("Harrisburg");
	Vertex v1 = new Vertex("Baltimore");
	Vertex v2 = new Vertex("Washington");
	Vertex v3 = new Vertex("Philadelphia");
	Vertex v4 = new Vertex("Binghamton");
	Vertex v5 = new Vertex("Allentown");
	Vertex v6 = new Vertex("New York");
	v0.adjacencies = new Edge[]{ new Edge(v1,  79.83),
	                             new Edge(v5,  81.15) };
	v1.adjacencies = new Edge[]{ new Edge(v0,  79.75),
	                             new Edge(v2,  39.42),
	                             new Edge(v3, 103.00) };
	v2.adjacencies = new Edge[]{ new Edge(v1,  38.65) };
	v3.adjacencies = new Edge[]{ new Edge(v1, 102.53),
	                             new Edge(v5,  61.44),
	                             new Edge(v6,  96.79) };
	v4.adjacencies = new Edge[]{ new Edge(v5, 133.04) };
	v5.adjacencies = new Edge[]{ new Edge(v0,  81.77),
	                             new Edge(v3,  62.05),
	                             new Edge(v4, 134.47),
	                             new Edge(v6,  91.63) };
	v6.adjacencies = new Edge[]{ new Edge(v3,  97.24),
	                             new Edge(v5,  87.94) };
	Vertex[] vertices = { v0, v1, v2, v3, v4, v5, v6 };

        computePaths(v0);
        for (Vertex v : vertices)
	{
	    System.out.println("Distance to " + v + ": " + v.minDistance);
	    List<Vertex> path = getShortestPathTo(v);
	    System.out.println("Path: " + path);
	}
    }
}

Das ist einigermaßen lesbarer Java-Code. Setzen wir das Ganze einmal möglichst 1:1 in „Besseres-Java-Scala“ um:

object dijkstra {

class Vertex(val name:String) extends Ordered[Vertex] {
var adjacencies:Array[Edge] = _
var minDistance = Double.MaxValue
var previous: Vertex = _
override def toString() = name
def compare(other:Vertex) = Math.signum(minDistance – other.minDistance).toInt
}

case class Edge(target:Vertex, weight:Double)

def computePaths(source: Vertex) {
source.minDistance = 0.0
var vertexQueue = new scala.collection.immutable.TreeSet[Vertex]
vertexQueue += source

while (!vertexQueue.isEmpty) {
val u = vertexQueue.firstKey
vertexQueue -= u
// Visit each edge exiting u
for (e <- u.adjacencies) { val v = e.target val weight = e.weight val distanceThroughU = u.minDistance + weight if (distanceThroughU < v.minDistance) { vertexQueue -= v v.minDistance = distanceThroughU v.previous = u vertexQueue += v } } } } def getShortestPathTo(target:Vertex):List[Vertex] = { var path = new scala.collection.mutable.ListBuffer[Vertex] var vertex = target while(vertex != null) { path + vertex vertex = vertex.previous } path.toList } def main(args: Array[String]) { val v0 = new Vertex("Harrisburg") val v1 = new Vertex("Baltimore") val v2 = new Vertex("Washington") val v3 = new Vertex("Philadelphia") val v4 = new Vertex("Binghamton") val v5 = new Vertex("Allentown") val v6 = new Vertex("New York") v0.adjacencies = Array(Edge(v1, 79.83), Edge(v5, 81.15)) v1.adjacencies = Array(Edge(v0, 79.75), Edge(v2, 39.42), Edge(v3, 103.00)) v2.adjacencies = Array(Edge(v1, 38.65)) v3.adjacencies = Array(Edge(v1, 102.53), Edge(v5, 61.44), Edge(v6, 96.79)) v4.adjacencies = Array(Edge(v5, 133.04)) v5.adjacencies = Array(Edge(v0, 81.77), Edge(v3, 62.05), Edge(v4, 134.47), Edge(v6, 91.63)) v6.adjacencies = Array(Edge(v3, 97.24), Edge(v5, 87.94)) val vertices = Array(v0, v1, v2, v3, v4, v5, v6) computePaths(v0) for (v <- vertices) { println("Distance to " + v + ": " + v.minDistance) val path = getShortestPathTo(v) println("Path: " + path) } } } [/sourcecode] Kein großer Unterschied, außer dass man die Edge-Klasse jetzt mit der Lupe suchen muss. Das TreeSet ist ein Kompromiss, weil ich bei Scala-Klassen bleiben wollte, Scalas PriorityQueue aber kein "freies" Löschen von Elementen unterstützt. Schauen wir mal, wie das ganze etwas "idiomatischer" aussieht: [sourcecode language='java'] object dijkstra { class Vertex(val name:String) extends Ordered[Vertex] { var adjacencies = List[Edge]() def -> (e:Edge) = { adjacencies += e ; this}
var minDistance = Double.MaxValue
var previous: Option[Vertex] = None
override def toString() = name
def compare(other:Vertex) = Math.signum(minDistance – other.minDistance).toInt
}

case class Edge(target:Vertex, weight:Double)

def computePaths(source: Vertex) {
import scala.collection.immutable.TreeSet
def loop(vertexQueue:TreeSet[Vertex]) {
if (!vertexQueue.isEmpty) {
val u = vertexQueue.firstKey
// Visit each edge exiting u
loop(u.adjacencies.foldLeft(vertexQueue – u){ (vq ,e) =>
val v = e.target
val distanceThroughU = u.minDistance + e.weight
if (distanceThroughU < v.minDistance) { val vq1 = vq - v v.minDistance = distanceThroughU v.previous = Some(u) vq1 + v } else vq }) } } source.minDistance = 0.0 val vertexQueue = new TreeSet[Vertex] loop(vertexQueue + source) } def getShortestPathTo(target:Vertex) = { def path(target:Vertex):List[Vertex] = target :: target.previous.map(path).getOrElse(Nil) path(target).reverse } def main(args: Array[String]) { val v0 = new Vertex("Harrisburg") val v1 = new Vertex("Baltimore") val v2 = new Vertex("Washington") val v3 = new Vertex("Philadelphia") val v4 = new Vertex("Binghamton") val v5 = new Vertex("Allentown") val v6 = new Vertex("New York") v0 -> Edge(v1, 79.83) -> Edge(v5, 81.15)
v1 -> Edge(v0, 79.75) -> Edge(v2, 39.42) -> Edge(v3, 103.00)
v2 -> Edge(v1, 38.65)
v3 -> Edge(v1, 102.53) -> Edge(v5, 61.44) -> Edge(v6, 96.79)
v4 -> Edge(v5, 133.04)
v5 -> Edge(v0, 81.77) -> Edge(v3, 62.05) -> Edge(v4, 134.47) -> Edge(v6, 91.63)
v6 -> Edge(v3, 97.24) -> Edge(v5, 87.94)
val vertices = Array(v0, v1, v2, v3, v4, v5, v6)
computePaths(v0)
for (v <- vertices) { println("Distance to " + v + ": " + v.minDistance) val path = getShortestPathTo(v) println("Path: " + path) } } } [/sourcecode] Alle Null-Referenzen sind verschwunden, die Edge-Arrays in Vertex durch Listen ersetzt (die durch eine etwas bequemere Syntax zu füllen sind), das previous-Feld ist jetzt eine Option, was in getShortestPathTo ausgenutzt wird. Am stärksten hat sich computePaths verändert: Die while-Schleife wurde durch ein rekursive Funktion ersetzt und die for-Schleife durch ein foldLeft. Beide Änderungen dienten dazu, auch die vertexQueue-Struktur unveränderlich zu machen (man kann erkennen, wie sie "durchgereicht" wird) Vertex ist die einzige verbliebene veränderliche Struktur, aber um diese auch unveränderlich zu machen, ist etwas mehr Aufwand erforderlich. Das Problem ist nämlich, dass die Edges auf einen Vertex verweisen und Vertizes Edges haben. Diesen Teufelskreis kann man aber durchbrechen, indem man Vertex in einen "Identitätsteil" und einen "Datenteil" aufsplittet, und die Edges nur auf den Identitätsteil zeigen lässt. Hier die "funktionale" Version: [sourcecode language='java'] object dijkstra { type Graph = Map[Vertex, Data] type VertexQueue = Map[Data, Vertex] case class Vertex(name:String) { def apply(graph:Graph) = graph.getOrElse(this, error("no data for vertex " + name)) override def toString() = name } case class Data(adjacencies:List[Edge], minDistance:Double, previous:Option[Vertex]) extends Ordered[Data] { def compare(other:Data) = Math.signum(minDistance - other.minDistance).toInt def this(adjacencies:Edge*) = this(adjacencies.toList, Double.MaxValue, None) } case class Edge(target:Vertex, weight:Double) def computePaths(graph:Graph, source: Vertex) = { def foldLoop(u:Data, vertexQueue:VertexQueue, graph:Graph) = u.adjacencies.foldLeft((vertexQueue - u, graph)){ (tuple, edge) =>
val (vq, map) = tuple
val v = edge.target
val distanceThroughU = u.minDistance + edge.weight
if (distanceThroughU < v(map).minDistance) { val data = v(map) val newData = Data(data.adjacencies, distanceThroughU, vertexQueue get u) (vq - data + newData -> v, map + v -> newData)
} else (vq, map)
}

def loop(vertexQueue:VertexQueue, graph:Graph):Graph =
vertexQueue.keys.find(_ => true) match {
case Some(u) => val tuple = foldLoop(u, vertexQueue, graph)
loop(tuple._1, tuple._2)
case None => graph
}

val data = source(graph)
val newData = Data(data.adjacencies, 0.0, data.previous)
val vertexQueue = new scala.collection.immutable.TreeMap[Data,Vertex]
loop(vertexQueue + newData -> source, graph + source -> newData)
}

def getShortestPathTo(target:Vertex, graph:Graph) = {
def path(t:Vertex):List[Vertex] = t :: t(graph).previous.map(path).getOrElse(Nil)
path(target).reverse
}

def main(args: Array[String]) {
val v = Array(„Harrisburg“, „Baltimore“, „Washington“, „Philadelphia“,
„Binghamton“, „Allentown“,“New York“).map(Vertex(_))
val startGraph =
Map(v(0) -> new Data(Edge(v(1), 79.83), Edge(v(5), 81.15)),
v(1) -> new Data(Edge(v(0), 79.75), Edge(v(2), 39.42), Edge(v(3), 103.00)),
v(2) -> new Data(Edge(v(1), 38.65)),
v(3) -> new Data(Edge(v(1), 102.53), Edge(v(5), 61.44), Edge(v(6), 96.79)),
v(4) -> new Data(Edge(v(5), 133.04)),
v(5) -> new Data(Edge(v(0), 81.77), Edge(v(3), 62.05), Edge(v(4), 134.47),
Edge(v(6), 91.63)),
v(6) -> new Data(Edge(v(3), 97.24), Edge(v(5), 87.94)))
val graph = computePaths(startGraph, v(0))

for (vertex <- graph.keys) { println("Distance to " + vertex + ": " + vertex(graph).minDistance) val path = getShortestPathTo(vertex, graph) println("Path: " + path) } } } [/sourcecode] Wie angekündigt habe ich von Vertex die Klasse Data abgeteilt. Der Graph (eine Map aus den Vertizes und ihren Daten) muss nun immer durchgereicht werden. Ein Problem ergab sich daraus, dass Vertex jetzt nicht mehr "vergleichbar" ist, da ja die Distanzen in der Data-Klasse gelandet sind. Zuerst habe ich versucht, das ganze mit impliziten Parametern hinzubiegen, aber nach einiger Überlegung habe ich mich entschieden, einfach die Data-Klasse sortierbar zu machen, und die PriorityQueue des Originals nicht mehr durch ein TreeSet, sondern eine TreeMap abzubilden - wobei diesmal Data auf Vertex zeigt (also genau umgekehrt wie in der Graph-Map). Da die beiden genannten Typen oft vorkamen, habe ich die Typ-Aliase "Graph" und "VertexQueue" eingeführt. Data als Schlüssel für eine Map zu verwenden ist übrigens nicht ganz unproblematisch: In größeren Graphen muss man aufpassen, dass zwei Data-Instanzen nicht als "gleich" angesehen werden, nur weil sie zufällig die gleichen Nachbarorte im gleichen Abstand haben. Aus der inneren Funktion loop habe ich die Funktion foldLoop herausgebrochen, die die eigentliche Arbeit erledigt (wie foldLeft funktionert, hatte ich ja schon im Origami-Beitrag erklärt). Vermutlich wird mein Programm keinen Schönheitspreis gewinnen, aber im Gegensatz zu den üblichen Beispielen zur funktionalen Programmierung (die oft wie Taschenspielertricks wirken) kann man hier sehen, wie es aus einem imperativen Programm Schritt für Schritt entstanden ist, und auch, welche Schwierigkeiten es dabei gab. Sicher könnte man das Programm weiter verbessern, aber dann müsste man stärker von der vorgegebenen Struktur abweichen und es wäre nicht mehr sinnvoll, es Seite an Seite neben das Java-Original zu stellen und zu vergleichen. Dieser Code ist nur als "Demo" gedacht und ich vermute, dass er nicht besonders performant ist. Bei funktionaler Programmierung spielt die Auswahl der "richtigen" Datenstrukturen eine große Rolle, und diese sind hier sicher nicht optimal. Dabei ist es oft nicht die Geschwindigkeit, sondern der Speicherbedarf, der Probleme bereitet. Vermutlich sollte man sich erst einmal nach einer guten Graphen-Bibliothek umsehen, denn unveränderliche Datenstrukturen richtig zu schreiben ist nicht trivial. Weiterhin sollte man in unserem Beispiel abwägen, ob man nicht lokal auch imperative Konstrukte zulassen sollte. „Imperativ“ ist nicht gleich „schlecht“, schlecht sind vor allem Seiteneffekte und veränderliche Daten, die aus ihrer lokalen Umgebung „entkommen“, indem sie weitergereicht werden.

Schön, dass ihr bis hierhin durchgehalten habt. Und falls ihr mal dringend von Harrisburg nach Allentown müsst: Jetzt kennt ihr den kürzesten Weg!

Advertisements

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s