Graphen in XML darstellen?

[jfheins]

Hallo,
ich möchte gerne einen Graphen in einer XML-Datei darstellen (abspeiochern und laden bekomm ich noch hin)

Frage ist jetzt: Wie geht das am effizientesten?

im Moment haben wir node-Elemente, die eine id haben und edge-Elemente, die 2 Node-id's haben. Es werden erst alle Nodes eingelesen und dann die Edges, wobei jede Ecke beim einlesen beide Nodes sucht, um die id zu einer Referenz aufzulösen.

Da das auch mal ein paar mehr Zeiler werden könnten, soll es aber möglichst effizient sein. Jeden Knoten zweimal mit seiner id zu suchen, halte ich nicht für effizient.

Erster Gedanke war, die Nodes beim einlesen in ein Dictionary<id, GraphNode> zu packen, Zugriffe auf ein Dictionary sollten iirc O(1) sein.

Bessere Ideen?

Die XML-Struktur kann auch noch verändert werden, falls das dann besser geht.

P.S.: Es handelt sich um einen gerichteten, zyklenfrien Graphen ohne Mehrfachkanten.

[Dax]

Eine weitere Möglichkeit wäre, den Knoten Unterelemente <edge to=".." /> zu geben. Wenn das ganze azyklisch ist, kannst du es dir auch einfach machen und den Graphen falsch herum in die XML-Datei schreiben, die Nodes aufsteigenend nummerieren und in eine Liste packen. Wenn es allerdings garantiert immer gerichtet, azyklisch und einfachbekantet ist, schachtele die Nodes doch einfach.

[jfheins]

Es ist zwar garantiert immer azyklisch, gerichtet und einfachbekantet, aber es kann durchaus mehrere Wege von A nach B geben ;)

Also sowas:

Code:

* D
  ^^
 /  \
B   C
^   ^
 \ /
  A

kann durchaus vorkommen.

Wenn ich den Knoten ein edgeto element gebe, muss ich auch wieder suchen. Und suchen könnte langsam sein...

[Dax]

Ok, ich dachte, jede Knoten hätte nur eine Eingangskante - das würde das schön einfach machen, offensichtlich ;) Auf jeden Fall wirst du irgend eine Art des Lookups brauchen, um die Knoten wieder zu finden. Wenn die Knoten selbst durch klassen repräsentiert werden, ist das auch gar kein Problem - die Klasse selbst ist viel schwerer als ein Zeiger darauf, also tun vier(acht) Byte extra für einen Listeneintrag nicht weh.

[himitsu]

da du selber Referenzen verwendest, aber in XML einen Index nutzt, wirst immer suchen müssen.

zum Optimieren:

du könntest wärend des Ladens ein(e) Array/Liste führen, wo du die erstellten Punte und ihren Index speicherst, zum schnellerem Suchen.

B und C könnten als Unterknoten von A gespeichert sein, dann muß man da nicht mehr suchen
D als Unterknoten von B = ebenfalls kein suchen
in C kommt ein to="D", da D ja schon in B drin ist
oder ein to="A.B.D", samt schnellem Suchpfad

[Uwe Raabe]

Ich würde in die XML-Datei zwei Haupt-Nodes einfügen: eine Liste der einzelnen Knoten und eine Liste der Kanten.
Beim Abspeichern der Knoten bekommt jeder Punkt einen Index, der temporär im Knoten abgelegt wird. Beim Speichern der Kanten werden die Knoten-Indizes geschrieben.
Bei Einlesen werden zunächst alle Knoten der Reihe nach in ein Array geschrieben. Damit kann beim Einlesen der Kanten jeder Knoten über seinen Index mit O(1) gefunden werden.

Nur so ein Gedanke...