Softwareentwicklung: Graphs

Wenn Sie Software entwickeln und sich schon mal gefragt haben, ob Bäume und Listen wirklich der Weisheit letzter Schluß sind, dann lehnen Sie sich einmal zurück und lassen Sie Graphs auf sich wirken.

Datentypen

Jede Programmiersprache bietet Datentypen wie Integer, Long, etc. und meist auch die Möglichkeit, sich selbst welche zu erschaffen, z. B. als Strukturen, Bäume usw. In der Regel benutzt man den Datentyp, der für ein spezielles Problem a m geeignetsten scheint, aber wer ehrlich ist, wird zugeben, dass die Gewohnheit einen nicht unerheblichen Einfluß hat. Also nutzt man meist eher das, was man schon kennt. Und das bringt dann mit sich, dass man alle Probleme mit den mehr oder weniger gleichen Denkmustern oder Strategien zu lösen versucht. Und die sind meist streng hierarchisch gegliedert und gradlinig. Ein weniger bekannter Datentyp sind Graphs. Ich glaube, dass Graphs ein großes Potential hat, weil er Hierarchien zulässt, aber auch mit total anarchischen Gliederungen problemlos zurechtkommt. Besonders geeignet scheint er mir für Vernetzungen, und das ist ja das Thema heutzutage.

Graphs

Prinzipiell bestehen Graphs aus Knoten (nodes)und Verbindungen (arcs). (siehe Listing 1) So kann man auf jeden Knoten von 0 bis MAXN 0 D ES-1 zugreifen. Die Verbindungen entsprechen einem mehrdimensionalen Feld oder einer Matrix.

Was Graphs so einmalig macht, ist die Vielfalt von Verbindungen, die eindeutig festgelegt, abgefragt oder verändert werden können. So sind arcs z.B. von node A nach B nur in eine Richtung, in beide Richtungen oder auch ohne Richtung möglich. Auch ein arc von A nach A ist zugelassen und Mehrfachverbindungen, etwa <A,B>,<A,C>,< D,A>,etc.

Zudem können arcs mit Werten belegt werden, u m z.B. die Durchflußmenge in einem Rohrsystem zu erfassen bzw. zu regeln. Oft genügt es schon zu wissen, ob eine Verbindung existiert oder nicht. Beispielsweise lässt sich ein Ablaufplan von Handlungen mit Graphs realisieren, da eine Reihenfolge der Aktionen eindeutig festgelegt werden kann. Und es erlaubt auch parallele Handlungen, die zusammenlaufen. Etwa das Anrühren eines Omelettes und das Erhitzen einer Pfanne, die dann im node ("gieße Ei in Pfanne") zusammentreffen. In dem Fall müßte man einen Zeittakt benutzen, der ein Nebeneinander koordiniert. Neben der Frage nach einer direkten Verbindung stellt sich aber auch die Frage nach einer Verbindung über andere Knoten, also eine indirekte Verbindung, die möglicherweise über alle übrigen Knotenlaufen kann.

Um festzustellen, ob solch eine Verbindung n-t= Grades besteht, maximal ist MAXNODES möglich, müßte man einen Umweg über eine Matrix gehen.

Einen Graph kann man komprimiert als mehrdimensionales Array wie adj [MAXNODES][MAXNODES], darstellen.Das sagt aber lediglich aus, ob eine direkte Verbindung, z.B. zwischen adj[i]U], besteht. Nur 0 und 1 sollen hier zugelassen sein. Um festzustellen, ob eine Verbindung 2. Grades besteht, muß entsprechend der Matrix-Multiplikation ein Booleanisches Produkt gebildet werden, das Auskunft gibt, ob adj2[i]U] wahr ist, also die Verbindung über nur einen anderen Punkt. Das bis zu MAXNODES Produkten fortzuführen ist natürlich extrem aufwendig. Zum Glück gibt es Warshall's Algorithmus, benannt nach seinem Entdecker, der das wesentlich vereinfacht: (Siehe Listing 2)

Wenn man die Verbindungsmatrix 1. Grades bis MAXNODES-ten Grades bildet und alle mit OR verknüpft, erhält man das, was jetzt in path[][] steht.
Es sagt aus, ob eine Verbindung beliebigen Grades zwischen 2 nodes besteht.

Dijkstra's Algorithmus

Meist genügt es aber nicht, nur das zu wissen, sondern man möchte auch den kürzesten Weg kennen bzw. den mit dem geringsten Aufwand. Der Wert dafür kann im Array weight[][] festgehalten werden und kann für Wegstrecke Widerstand oder beliebige andere Bewertungen stehen. Wenn alle Werte positiv sind, bietet sich folgende Routine an, die einem Algorithmus von Dijkstra nachempfunden ist. S und t stehen für den Start- bzw. Endnode. Pd(path dista nce) enthält die Summe aller weights auf seinem Weg und precede[] sammelt die Verweise auf die benutzten nodes.

So steht in precede[t] der vorangehennode von t usw. zurück bis s. (Listing 3) Wenn keine Verbindung zwischen 2 n od es besteht, sollte im weight Feld ein maximaler Wert eingetragen sein wie weight[i]U] = IN FINITY. Auch liefert die Funktion nur sinnvolle Ergebnisse, wenn node t von s aus auch wirklich erreichbar ist, also path[s][t] existiert.

Praktische Anwendungen

Mit diesem Wissen könnte man Städte als nodes annehmen, die Straßen als arcs und Kilometer, mögliche Behinderungen als weight eintragen und schon würde das Programm die optimale Route ausdrucken. Zugegeben, in dem Fall wäre - für den persönlichen Gebrauch - ein Blick auf eine Straßenkarte sinnvoller. Aber vielleicht begegnet Ihnen das eine oder andere Problem, das sich mit Hilfe von Graphs wesentlich anschaulicher formulieren lässt.