Gerichteter azyklsicher Graph speichern

Hallo liebe Community!

Ich stehe mal wieder vor einem Problem. Hat Jemmand eine Idee wie ich einen gerichteten azyklischen Graphen abspeichern kann als Datei mit so wenig Platzverbrauch wie möglich.

Vllt irgendwelche Strategien oder Ideen?

Ein Beispielgraph wäre:

siehe Anhang

Danke im vorraus,

Wolf

Musst du per Node Daten speichern oder reichen dir die Edges?

Schau dir mal das dot Format von Graphviz an. Das ist zwar ein Textformat, aber als Anschauungsmaterial sicherlich nicht schlecht.

Hier einige Möglichkeiten, deinen Graph zu repräsentieren (angelehnt an dot):

1. Jede Edge einzeln: A->B;B->C;B->D;B->E;C->E;D->E;G->D;E->F
2. Jeden Ausgangsknoten einzeln: A->B;B->(C,D,E);C->E;D->E;G->D;E->F
3. Pfade: A->B->C->E->F;B->D;B->E;G->D->E
4. 2. und 3) kombiniert: A->B->C->E->F;B->(D,E);G->D->E

Am einfachsten zu speichern ist sicherlich Version 1, weil jede Edge als ein Paar Node IDs repräsentiert wird. Als Binärformat reicht es dann aus, zunächst die Anzahl Paare und danach je Paar die zwei IDs zu speichern. Die Auswahl des Datentyps für jeden Wert hängt vom Anwendungsfall ab (Größe des Graphs): für kleine Graphen z.B. bytes, oder allgemein z.B. 7-bit komprimierte Integer (siehe http://msdn.microsoft.com/en-us/library/system.io.binarywriter.write7bitencodedint.aspx)

Grüße,
Andre

Ich muss sowohl die Knotenübergänge speichern, als auch die Inhalte der Blätter am Ende (1 Byte groß pro Blatt).
Danke für die Ansätze erstmal!

MFG Wolf

Ich meine mich daran erinnern zu können, das man Graphen recht gut mit verketteten Listen im Speicher darstellen kann, also sollte es ja auch beim Speichern in einer Datei funktionieren:

Dazu zunächst einfach mal alle Knoten miteinander verknüpfen:

A - B - C - D - E - F - G

anschließend zu jedem Knoten speichern, welcher andere Knoten von diesem erreicht werden kann:

A - B
|
B - C - D - E
|
C - E
|
D - E
|
E - F
|
F
|
G - D

Kann man auch recht einfach mit XML oder soetwas umsetzen.