C Datenstruktur Graph | Baum | Speichern eines geschedulden Graphen

[hell-student]

Hallo Zusammen,

Ich habe folgende Situation. Ich habe hier einen Beispielsgraphen, welcher schon gescheduled wurde, also die Graphknoten den einzelnen Steps (Zeitschritte 0 - 4) zugeordnet wurde. Wie kann ich mir diesen am effizientesten Speichern?



Vorraussetzung:

- Graph muss möglicherweise rescheduled werden -> einzelne Knoten werden also in Y-Achse nach unten verschoben -> mehr Steps
- Es müssen neue Knoten in den gescheduleden Graphen eingefügt werden.

Meine erste Idee war folgende:

1. Knoten in der Reihenfolge nach in einem Array speichern.
2. Zusätzliches Array verwenden, welches folgende Aussage hat:

step_size[x] = Startindex im Knotenarray
step_size[x+1] = Endindex im Knotenarray

Alle Knoten von Start (inklusive) bis End (exclusive) werden im step y gescheduled.

Beispiel hier am Graph:

Knotenarray: [1, 2, 3, 4, 5, 6, 7, 8]

step_size: [1, 4, 4, 5, 5, 6, 6, 7, 7, 9]

also:
Step 0: 1,4 d.h Knoten 1,2,3
Step 1: 4,5 d.h Knoten 4
Step 2: 5,6 d.h Knoten 5
Step 3: 6,7 d.h Knoten 6
Step 4: 7,9 d.h Knoten 7,8

Mein Problem ist hierbei, dass ich mit festen Arrays arbeiten würde, könnte also obige Voraussetzungen nicht erfüllen.

Meine nächste Idee ist, dass ich es als LinkedList abspeichere in der Art:




Ich möchte später für jeden Knoten etwas berechnen/tun und zwar in der Step Reihenfolge, also muss ich später zuerst die Steps durchgehn und dann die darin enthaltenen Knoten

Gibt es möglicherweise eine Lib die mir das alles erspaart? thx

 

[the_nobs]

Wie kann ich mir diesen am effizientesten Speichern?

HI
was heißt effizient?
Größe?
Zugriffszeit?
vermute mal du meinst speichern als File auf eine disk, oder?

 

[hell-student]

@the_nobs

Mein Programm wird später auf einem 70Mhz FPGA laufen und daher wäre es schon wichtig eine geeignete Datenstruktur zu finden, in der ich schnell auf die einzelnen Steps und Knoten zugreifen kann. Der Speicher ist auch nicht gerade der Größte. Mit speichern meinte ich aber eigentlich eine geeignete Repräsentation des zu finden, die es zulässt Knoten hinzuzufügen etc. Verwende ich beispielsweise Arrays, müsste ich, wenn ich einen zusätzlichen Knoten in Step 0 hinzufüge, das Array vergrößen und alle dannachkommenden Knoten verschieben. Dieses rumkopieren kostet ja auch Zeit/Performance

 

[blöderidiot]

Auf Deinem Bild 1 ist ein zyklischer Graph zu sehen. Hat das eine Bedeutung? Wenn nicht, könnte man es sehr einfach mit zwei int-Vektoren der Länge K(n) lösen (aus "Verbindungs"-Matrix von i, j - für j > i; der Index von v1 ist dann der Knoten, dessen Inhalt ist y, der Index von v2 ist wieder der Knoten und der Inhalt von v2 ist der Index des verbundenen Knotens -- oder -1, wenn es keinen gibt)

 

[maxwell-cs]

mein vorschlag sieht so aus, etwas in die richtung hast du ja auch schon gedacht:

- ein array, der mit levels indiziert wird, jeder eintrag enthält einen weiteren (dynamischen!) array mit den knoten dieser ebene
- fügst du einen knoten einer ebene hinzu, fügst du ihn am ende des arrays dieser ebene hinzu
- entfernst du einen knoten von einer ebene, tauschst du ihn mit dem letzten knoten dieser ebene und entfernst ihn dann. da er nun am ende des arrays stand, sind keine umkopierungen notwendig.
- außerhalb speicherst du dir die aktuelle position eines knoten in seinem ebenenarray, um nicht suchen zu müssen

diese variante wäre leicht zu implementieren und effizient, vorrausgesetzt, es gibt nicht sehr viele - wenn überhaupt - leere ebenen.

ob das sinn macht, hängt natürlich von der erwarteten größe der instanzen ab, wenns nur ein paar hundert knoten sind, kann man auch eine einfachere implementierung mit quadratischer laufzeit wählen.

falls du so vorgehst, wie in deiner idee beschrieben: du kannst dir die hälfte der einträge in step_size sparen und nur den ersten index eines knoten in dieser ebene speichern. so wie jetzt hast du immer denselben eintrag 2x hintereinander.

wie willst du die kanten speichern? wenn du jedem knoten eine liste (array) seiner nachfolger spendierst, müssen die knoten feste indizes haben - oder aber du updatest jedes mal, wenn ein neuer knoten nach vorne rutscht, auch alle kanten.

ich würde dir also dazu raten (wenn du das nicht sowieso vorhattest, wird nicht so ganz klar) die knoten mit festen indizes zu speichern und in einer weiteren datenstruktur nur knotenindizes zu verwalten.