[linux-l] [GStreamer] graphs of media-handling components

[Volker Grabsch]

On Fri, Jan 05, 2007 at 11:45:47AM +0000, Detlef Lechner wrote:
> Hallo Olaf,
> 
> Am Donnerstag, den 04.01.2007, 23:53 +0100 schrieb
> olafBuddenhagen at gmx.net:
> 
> > Graphen sind ein Begriff aus der theoretischen Informatik. Die genaue
> > Definition kenne ich nicht, 
> 
> Hier eine Definition aus der Mathematik: "G = (V, E) heißt
> 'ungerichteter Graph' mit der Knotenmenge V und der Kantenmenge E,
> falls jedes e Element aus E eine zweielementige Teilmenge von V ist.  V
> ist endlich. Anmerkungen: Falls {v, w} Elemente aus E, sind v und w
> durch eine ungerichtete Kante miteinander verbunden. Beachte: {v, w} und
> {w, v} beschreiben dieselbe Menge, also auch Kante."

Dies beschreibt einen endlichen, ungerichteten Graph ohne Schlaufen,
Doppelkanten und Gewichte.

Der ist tatsächlich in der Mathematik üblich, aber auch ein Mathematiker
kennt verschiedene Arten von Graphen. :-)

> In der Informatik scheint es mehrere unterschiedliche Definitionen von
> 'Graph' zu geben. 

Es gibt verschiedene Arten von Graphen, je nach Anwendung. Auch die
Mathematik kennt mehrere, das Konzept des Graphen gehört dorthin. :-)
Auch wenn das einige vielleicht gern hätten: Mathematik und theoretische
Informatik sind nicht grundverschieden. Genaugenommen ist die
theoretische Informatik ein Teilgebiet der Mathematik *und* der
Informatik. Genauso wie die theoretische Physik ebenfalls den Teil der
Physik betrachtet, der auch Mathematik ist.

Darüberhinaus kann man Graphen auf anders konstruieren. Was du oben
geschrieben hast, ist genaugenommen eine Realisierung oder
konstruktive Definition eines Graphen.

Eigentlich genügt es, zu sagen, ein Graph ist eine Menge mit einer
Relation. Und Umgangsspachlich nennt man die Elemente dann Knoten,
Man sagt, eine Kante führt von A nach B, wenn die Relation zwischen
A und B besteht.

Mögliche Realisierungen der Knoten Menge:
* riesiges Array
* Liste
(obwohl man hier natürlich auch wieder verschiedene Möglichkeiten hat)

Mögliche Realisierungen der Kanten (d.h. der Relation):
* Funktion
* Menge von zweielementigen Knoten-Teilmengen
    (wobei man diese Menge wieder als Arrays, etc. modellieren kann)
* Menge von (geordneten) Knoten-Paaren
    (wobei man diese Menge wieder als Arrays, etc. modellieren kann)
* Adjazenzmatrix
* Adjazenzliste

Wobei diese "Realisierungen" auch wiederum theoretische Konzepte sind,
sie man in verschiedenen Programmiersprachen unterschiedlich umsetzen
kann.

Wenn man ganz hart nimmt, kann man sogar sagen, Relation und Graph
sind im Prinzip dasselbe. Eine Mathematiker macht sich nur selten die
Mühe, zwischen beiden zu unterscheiden. Man wechselt vom einem zum
anderen, jenachdem, was sich gerade leichter vorstellen bzw. besser
erklären lässt.

Beide beschreiben die abstrakte Idee, dass man gewisse Elemente hat,
die irgendwie miteinander verbunden sind (Graph) bzw. die in besimmten
Beziehungen zueinander stehen (Relation). Wenn man versucht, das in
entsprechende Axiome zu gießen, stellt man schnell fest, dass Graph
und Relation sich nicht unterscheiden. Nur unsere Anschauung von ihnen
ist unterschiedlich.

----------------------------------------------------------------------

Ein Spezialfall, der kreifreier zusammenhängender Graph, hat einen
extra Namen bekommen: Baum. Wenn jemand Baumstrukturen kennt, dann
kann man einen Graphen auch so beschreiben: Es ist ein Baum, bei dem
die Knoten auch kreuz und quer miteinander verbunden sein dürfen.

Warum sind Dateisysteme, Domain-Namen, etc. hierarchisch, also Baum-
Strukturen, statt Graphen-Strukturen? Weil sich Bäume leichter verwalten
lassen. Sie ermöglichen es, einen Knoten stellvertretend für all seine
Nachfolger zu betrachten. Man kann einen Baum also "auf- und zuklappen",
und genau das machen Menschen. Sie fassen Dinge zu Klassen zusammen und
behandeln diese wie eins. Ich rede z.B. von einem Computer. Und diesen
zerlege ich auch nicht gleich in Atome, sondern erstmal in Bildschirm,
Tastatur, etc., und die Tastator dann wieder in Kabel, Tasten, etc.

Die Relationen, die durch diese speziellen Graphen namens Bäume
beschrieben werden, nennt man auch "Ganzes/Teil-Relationen".

Aber nicht alles ist ein Baum, nicht alles ist streng hierarchisch
aufgebaut. Das allgemeinere Konzept des Graphen eigenet sich dann,
wenn man kompliziertere Zusammenhänge beschreiben will.

"Natürliche" Graphen, wie z.B. das Internet, oder die WWW-Seiten
sind meistens so aufgebaut: Es ist zwar insgesamt kein großer Baum,
aber wenn man kleinere Teilgraphen isoliert betrachtet, sind es sehr
wohl Bäume. (Man sagt, solch ein Graph besteht "lokal" aus Bäumen,
aber das ist nur ein sehr vaguer Begriff.)

Zum Beispiel besteht eine Webseite aus kleineren Seite, die meistens
Hierarchisch angeordnet sind, aber eben auch zu völlig anderen Webseiten
verlinken. Selbst in "chaotischen" Graphen-Gebilden wie den Wikipedia-
Artikel findet man mehrere "draufgesetzte" Hierarchien (z.B. Kategorien,
Einordnung in den Zeitstrahl, etc.). Und jedes Dokument selbst, jeder
Artikel, ist wieder in Baumstruktur (Kapitel, Unterkapitel, Absätze und
Bilder, etc.).

Wir Menschen betrachten gern Teilbäume von Graphen, weil wir diese
viel besser verstehen und damit besser umgehen können, als mit wirklich
chaotischen Bäumen. Unser Straßensystem besteht ebenfalls aus großen
Adern, die in kleinere verzweigen. Und wenn plötzlich viele kleine
"gleichwertige" Straßen kommen, verliert man sich schnell, wie in einem
Irrgarten.

Aber wir Menschen sind auch daran gewöhnt, dass eben nicht alles eine
große Hierarchie gibt, daher können wir auch, begrenzt, mit den
chaotischen Querverbindungen umgehen, indem wir diese als "vom
eigentlichen Baum" isoliert betrachten. Wir packen also einfach eine
Hierachie-Ebene darüber: Zum einem gibt es den großen Baum, und zum
anderen die Querverbindungen.

Etwas komplett in viele kleine unorganisierte Teile zerfallen zu lassen
(chaotischer Graph) ist daher genauso ungünstig, wie alles in eine
große Hierarchie (reiner Baum) hineinquetschen zu wollen. Dieser Teil
von Architektur und Design macht einen großen Teil dessen aus, was wir
als "Programmierung" kennen.

Dort geht es genaugenommen um die Handhabung von Komplexität, mit den
Waffen der Komposition und Abstraktionen. Beide Werkzeuge etablieren
letztlich Baumstruktion, meist auch "Schichten" genannt, weil man
Gedanklich die Knoten jeweils einer Hierarchieebene zusammenfässt.
Komposition bildet Baumstrukturen in den Daten. Abstraktion bildet
Baumstrukturen in den Prozessen/Funktionen. Beide gehen Hand in Hand,
die Auftrennung in zwei Begriffe ist wiederum nur menschliche Willkür,
um besser damit umgehen zu können.

(Weil unser Gehirn zwischen räumlichen und zeitlichen Dimensionen
unterscheidet, bedingt durch diese komische 3:1-Aufteilung in unserem
konkreten Universum. 3:1, das ist auch der tiefere Sinn dahinter, warum
unsere räumliche Vorstellungskraft besser geschult ist, und warum wir
zeitliche Ablkäufe uns immer irgendwie räumlich vorstellen, durch einen
Zeitstrahl, Kalender, u.Ä., obwohl ich es viel cooler fände, wenn wir
4-dimensionale Geometrie im Kopf beherrschen würden. ;-))

Das Hindernis bei Komplexität ist ja nicht die reale Welt, sondern nur
unser Geist, die Grenzen unserer Phantasie und Vorstellungskraft.
Komplexität zu beherrschen heißt, sie auf eine für unseren Geist
zugängliche Art zu strukturiren.

Die Konzepte von Bäumen und Graphen sind also sehr allgemein und ihre
Verwendung ist stark von der Art und Weise geprägt, wie unser Geist
arbeitet, und wie wir Komplexität beherrschen können.


Viele Grüße,

    Volker

-- 
Volker Grabsch
---<<(())>>---
Administrator
NotJustHosting GbR