Ich fand einen sehr interessanten Artikel, der sich mit der effizienten Auslastung aller Kerne eines Prozessors bei der Abarbeitung voneinander abhängiger Tasks beschäftigt. Daraus wuchs der Wunsch, dies Idee zu implementieren und dann damit zu experimentieren.

Der Artikel beschreibt zunächst das Problem: Zahlreiche Tasks müssen abgearbeitet werden. Allerdings sind diese nicht völlg unabhängig voneinander, sondern es existieren solche, die erst nach der Abarbeitung bestimmter anderer gestartet werden dürfen.

Dazu wird ein Algorithmus vorgestellt - eben die namensgebende topologische Sortierung - und erläutert, wie man diese effizient auf das Beispielprojekt anwenden kann.

Meine Experimente erzeugten die unten angehängten Datenstrukturen und Klassen. Zusammengenommen stellen sie Werkzeuge zur Modellierung eines gerichteten Graphen dar. In der vorliegenden Version ist es möglich, den Graphen im dot-Format zu serialisieren, so dass man sich die Beziehungen der Knoten untereinander zum Beispiel hier visualisieren kann.

Beispiel für die Visualisierung des Datenmodells mittels dot bzw. GraphViz

Ein weiteres Beispiel ist hier im dot-Format zu sehen

digraph {
		rankdir=LR;
label="ModuleWorkspace";
"3";
"1";
"7" -> { "3", "1", "0"};
"6" -> { "3"};
"5" -> { "2"};
"8";
"10" -> { "7", "4"};
"4" -> { "3"};
"2";
"0";
}

Die Datenstruktur lässt sich natürlich auch mittels der zentralen Komponente der sQLshell und in dWb+ visualisieren, wie die beiden angehängten SVG-Graphiken zeigen sollen.

Lizenz

RankComparator.java

NodeCollection.java

Node.java

ForwardGraphGenerator.java

GraphViz-Visualisierung

ModuleWorkspace-Visualisierung

Artikel, die hierher verlinken