Graphenalgorithmen: Best Practice für Knoten-/Kanten-Attribute

[Naryxus]

Hallo,

ich stehe momentan vor einer kleinen Design-Entscheidung.

Ich habe bisher Knoten- und Kanten-Attribute, wie zum Beispiel, ob ein Knoten gesehen wurde oder die Kapazität einer Kante für Fluss-Algorithmen als tatsächliches Attribut eines Knotens oder einer Kante implementiert.
Ich frage mich, ob das tatsächlich sinnvoll ist, da es einerseits den Knoten oder die Kante recht "spezifisch" machen würde, da somit jede Kante eine Kapazität hätte, um bei dem Beispiel zu bleiben, auch für Algorithmen, die gar keinen Fluss berechnen.
Theoretisch könnte ich noch argumentieren, dass ich da dann super Vererbung etc. benutzen könnte.
Allerdings hat mir dieses Design schon einmal richtig das Genick gebrochen und zwar bei einem bestimmten Algorithmus, bei dem Kanten temporär aus dem Graphen gelöscht werden mussten. Da dies temporär war, musste ich den Graph "klonen", damit die Informationen nicht verloren gingen. Und da Java nur mit Pointern arbeitet, musste ich somit auch jede Kante und jeden Knoten und damit auch jedes einzelne Attribut klonen.

Nun habe ich mich gefragt, ob es nicht teilweise sinnvoller wäre, dass man diese Informationen zusätzlich in einer entsprechenden Datenstruktur (Array, Liste, etc.) mit an den bestimmten Algorithmus übergibt. So müssten diese Informationen nicht mehr in den Knoten und Kanten gespeichert werden.

Was haltet ihr denn davon?

Grüße, Naryxus

 

[Flown]

Also ein Knoten ist in einem Graph einfach eine Entität, der herumschwirrt und eventuell eine Kapazität und eine ID - also gewisse Eigenschaften - hat.
Kanten sind Verbindungsstücke die 2 Knoten miteinander verbindet (und gegebenenfalls auch eine Kapazität/Gewichtung besitzt).

Genauso würde ich das auch Designen, nämlich im Sinne von OO. Was dann die Graphalgorithmen damit anstellen ist dann eben eine andere Sache.

Allerdings hat mir dieses Design schon einmal richtig das Genick gebrochen und zwar bei einem bestimmten Algorithmus, bei dem Kanten temporär aus dem Graphen gelöscht werden mussten. Da dies temporär war, musste ich den Graph "klonen", damit die Informationen nicht verloren gingen. Und da Java nur mit Pointern arbeitet, musste ich somit auch jede Kante und jeden Knoten und damit auch jedes einzelne Attribut klonen.

Also Graphen sind eine Datenstruktur. Anders gefragt, wenn du eine Liste hast und etwas "temporär" rauslöscht, musst du auch den Urzustand speichern, bzw. die Liste kopieren. Gott sei Dank kann man sich dazu Methoden schreiben, die Logik clustern und vereinfachen.

Nun habe ich mich gefragt, ob es nicht teilweise sinnvoller wäre, dass man diese Informationen zusätzlich in einer entsprechenden Datenstruktur (Array, Liste, etc.) mit an den bestimmten Algorithmus übergibt. So müssten diese Informationen nicht mehr in den Knoten und Kanten gespeichert werden.

Wie du das dann machst bleibt die überlassen, aber etwas extra speichern in Arrays/Listen ist nicht sehr OOP.

 

[Naryxus]

Danke für deine Antwort.

Ich beschäftige mich nun schon seit einiger Zeit mit Graphenalgorithmen - Also sind mir die grundlegenden Möglichkeiten, wie man Graphen mit allem drum und dran implementieren kann bekannt.

Ich habe mich nur gefragt, wie es am sinnvollsten ist. Ich war vorerst auf dem Stand, wie sowohl du als auch ich oben schon geschrieben haben, dass die ganzen Attribute für Knoten und Kanten Objektvariablen der jeweiligen Klassen sind.
Allerdings bin ich da wie gesagt schon auf die Nase gefallen, als ich das kopieren musste. Das ist meiner Meinung nach recht ineffizient, da dann bis in die kleinste Klasse die clone()-Methode aufgerufen werden musste.
Und zudem muss ich dann auch noch "beweisen", dass die verschiedenen Datenstrukturen mit ihren Methoden eine bestimmte Laufzeitkomplexität einhalten (z.B. Löschen eines Elements aus einer ArrayList hat konstante Laufzeit), da ich dieses Programm in näherer Zukunft präsentieren und verteidigen muss.
Das ließe sich mittels Arrays und möglichst einfachen Datenstrukturen deutlich vereinfachen, vor allem, wenn alle Flüsse zum Beispiel in einem Array gespeichert werden würden und nicht über alle Kanten erfragt werden müssten.

Grüße

 

[mrBrown]

Wenn mans Objekt-Orientiert machen will: Knoten und Kanten als Objekte, Knoten kennen nur Kanten, Kanten nur Knoten und Gewichtung (=Kapazität). Dürfte dann eine ähnliche Laufzeitkomplexität wie mit Adjazenzliste haben.

Wenn dir Objekt-Orientierung egal ist, dann Adjazenzliste/Matrix mit durchnummerierten Knoten.


Die absolute Laufzeit ist mit der nicht-Objekt-Orientierten Variante geringer, die Komplexität der Algorithmen bleibt aber grundsätzlich gleich.

kopieren muss man immer irgendwas, sowohl bei der Objekt-Orientierten, als auch bei der anderen (#clone würde ich dafür allerdings nicht nutzen, eher einen Konstruktor für den Graphen, der einen Graphen entgegen nimmt).

 

[Naryxus]

Wenn dir Objekt-Orientierung egal ist, dann Adjazenzliste/Matrix mit durchnummerierten Knoten.

Die absolute Laufzeit ist mit der nicht-Objekt-Orientierten Variante geringer, die Komplexität der Algorithmen bleibt aber grundsätzlich gleich.

Ja so mache ich das auch momentan. Und es wäre bewundernswert, wenn die Komplexität der Algorithmen geringer werden würde, wenn man ein anderes Programmierparadigma verwendet

Danke dir

 

[mrBrown]

Ja so mache ich das auch momentan. Und es wäre bewundernswert, wenn die Komplexität der Algorithmen geringer werden würde, wenn man ein anderes Programmierparadigma verwendet

größer kann sie allerdings durch die Datenstrukturen werden, die sind ja mit OO durchaus mal anders