Wer moderne Software anfertigt, kämpft mit hoher Komplexität, die sich nur mit ebenso modernen Tools und Verfahren beherrschen lässt. Die Titelgeschichten dieser Ausgabe helfen die richtigen auszuwählen.

Das Cover dieses Linux-Magazins zeigt eine Phantasie-Maschine, die aus einer magischen Schmelze zuerst eine Art Metallfolien gießt, die abkühlen und das Substrat für einen Quellcode bilden, den schließlich ein Roboterarm ritzt. Das Ganze soll – so die Idee der Redaktion – den Entwicklungszyklus von Software symboliseren, den das Titelthema dieser Ausgabe im Fokus hat.

Wer eine Informatikausbildung besitzt und mit Hilfe eines guten Auges den zarten Code entziffert, den der starke Maschinenarm gerade graviert, erkennt vielleicht den Dijkstra-Algorithmus wieder. (Normalsichtige dürfen auch auf den Pseudocode aus Listing 1 zurückgreifen.)

Der Algorithmus ist nach dem 2002 verstorbenen niederländischen Informatiker und Turing-Award-Preisträger Edsger Wybe Dijkstra benannt. Der Wegbereiter des strukturierten Programmierens (“Goto considered harmful”) hatte übrigens auch als Erster das Verklemmungs-Problem der “speisenden Philosophen” beschrieben sowie Threads mit Semaphoren synchronisiert.

Der Dijkstra-Algorithmus also berechnet den kürzesten Pfad zwischen einem Startknoten und dem Ziel »t« in einem kantengewichteten Graphen. Den repräsentiert hier eine Liste von Vorgängern »p[]« . Das Verfahren folgt derjenigen Kante, die den kürzesten Streckenabschnitt vom Startknoten aus verspricht. Andere Kanten betrachtet es erst dann, wenn keine kürzeren Abschnitte erkennbar zum Ziel führen.

Da einmal berechnete Distanzen vom Startknoten dauerhaft gültig bleiben, gehört der Dijkstra- zu den so genannten Greedy-Algorithmen [2], die in jedem Schritt die momentan aussichtsreichste Teillösung bevorzugen. Anders als andere Greedy-Algorithmen berechnet Dijkstra jedoch die optimale Lösung. Auf praktische Implentierungen des Verfahrens trifft man beispielsweise bei Routingsoftware.

Agil gegen die Wand

Einen stets optimalen Dijkstra-Weg durch ihren Alltag wünscht sich sicher mancher Programmierer. Denn das Anfertigen moderner Applikationen ist von hoher Komplexität – nicht so sehr algorithmisch, aber beim “Drumherum”: Das aktuelle Projekt mit verteilt arbeitenden Mitgliedern will verwaltet sein. Für den Wust an Quellcodedateien mit ihren verschlungenen Abhängigkeiten und auseinanderdriftenden Versionen gilt das Gleiche. Und wie sollen in robuster Weise daraus Binärcode und schließlich Pakete für den Distribtionszoo entstehen? Ganz zu schweigen vom Testen des Ganzen.

Das vorliegende Linux-Magazin versucht den Weg zu weisen zwischen den Kanten und Knoten dieses komplexen Gebildes aus Tools und Verfahren. Die Auswahl, so viel sei vorab verraten, ist riesig. Als Startknoten wählt der Schwerpunkt das agile Entwicklungsmodell und die Betrachtung darüber, ob es sich für Community-Projekt eignet. Der Zielpunkt ist erreicht, wenn Qt-Programme unter Zuhilfenahme einer Testbibliothek an die Wand fahren.

01 func path(t, p[])
02 w[] = [t];
03 u = t;
04 while !p[u]:
05 u = p[u];
06 w[] <- u;
07 return p[];