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.
Zitat
Baum-Darstellung
