Topologische Sortierung

vorhergehende Artikel in: Java Komponenten Markup
26.12.2017

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.

Screenshot 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

Sitemap mittels Graphviz

06.07.2019

Ich habe mein System zur Erzeugung der Webseite um die Erstellung einer Sitemap als Graph erweitert

Neue Datengeneratoren III

08.07.2017

Einige neue Generatoren wurden für das Framework zur Erzeugung von Testdaten geschaffen.

Alle Artikel rss Wochenübersicht Monatsübersicht Github Repositories Gitlab Repositories Mastodon Über mich home xmpp


Vor 5 Jahren hier im Blog

Neueste Artikel

  • SQL Funktionen in SQLite als BeanShell-Scripts

    Ich habe bereits hin und wieder über Erweiterungen der sQLshell berichtet, die bestimmte spezifische, proprietäre Features des jeweiligen DBMS in der sQLshell verfügbar machen.

    Weiterlesen...
  • Spieleengine IX

    Es gibt seit Ewigkeiten mal wieder Neues von meiner eigenen Spieleengine!

    Weiterlesen...
  • Neue Version plantumlinterfaceproxy napkin look

    Es gibt eine neue Version des Projektes plantumlinterfaceproxy - Codename napkin look.

    Weiterlesen...

Manche nennen es Blog, manche Web-Seite - ich schreibe hier hin und wieder über meine Erlebnisse, Rückschläge und Erleuchtungen bei meinen Hobbies.

Wer daran teilhaben und eventuell sogar davon profitieren möchte, muß damit leben, daß ich hin und wieder kleine Ausflüge in Bereiche mache, die nichts mit IT, Administration oder Softwareentwicklung zu tun haben.

Ich wünsche allen Lesern viel Spaß und hin und wieder einen kleinen AHA!-Effekt...

PS: Meine öffentlichen GitHub-Repositories findet man hier - meine öffentlichen GitLab-Repositories finden sich dagegen hier.