Hey Leute!
Eine kleine theoretische Frage hätte ich hier an euch.
Zum Hintergrund: Ich musste vor kurzem eine allzweck-graphenklasse für allgemeine "experimente" erstellen. Hab da ohne lange zu überlegen mich für die Implementierung mit einer Adjazenzenliste entschieden, für jeden Knoten wird einfach gespeichert, zu welchen anderen knoten eine gerichtete Kante führt.
Das hat zwar einigermaßen akzeptabel funktioniert, allerdigs gefällt mir daran nicht, dass es so aufwendig ist, eingehende kanten zu finden. Dazu muss ich ja alle anderen einträge bei allen anderen Knoten (also im prinzip den gesammten Graphen) durchgehen, nur um paar doofe eingehende kanten zu finden.
Wozu das gut sein soll, eingehende kanten zu suchen, sei erstmal dahingestellt. Zum beispiel ist mir keine bessere Möglichkeit eingefallen, einen gerichteten Graphen auf schwachen wegzusammenhang zu testen (oder geht's ohne?).
Ferner sollte es imho möglich sein, den Graphen ohne jeglichen Aufwand auf die "ungerichtete" Perspektive umzustellen (wie soll ich zB sonst die Wege für ego-shooter bots darstellen, die sich plötzlich levitationsbonus geschnappt haben, und jetzt alle wände hochkommen, von den man sonst nur runterfallen kann?)
Fragen:
Ist es sinnvoll, für jeden Knoten statt den ausgehenden sowohl ausgehende als auch eingehende verbindungen zu speichern? Dann wäre zwar jede Kante zwei mal drin, aber irgendwie wäre es imho wesentlich leichter zweischen der gerichteten und der ungerichteten Perspektive umzuschalten.
Bei Kanten die in beide Richtungen verlaufen wäre es aber dann wiederum total bescheuert: ein und dieselbe Verbindung müsste schon 4 mal gespeichert werden.
Soll ich evtl nicht direkte Referenzen auf nachbarknoten, sondern referenzen auf kanten abspeichern?
Oder gibt es eine bessere Möglichkeit, auf die ich bisher nicht gekommen bin?
Vielen Dank im voraus.
greetz, Andrey
Eine kleine theoretische Frage hätte ich hier an euch.
Zum Hintergrund: Ich musste vor kurzem eine allzweck-graphenklasse für allgemeine "experimente" erstellen. Hab da ohne lange zu überlegen mich für die Implementierung mit einer Adjazenzenliste entschieden, für jeden Knoten wird einfach gespeichert, zu welchen anderen knoten eine gerichtete Kante führt.
Das hat zwar einigermaßen akzeptabel funktioniert, allerdigs gefällt mir daran nicht, dass es so aufwendig ist, eingehende kanten zu finden. Dazu muss ich ja alle anderen einträge bei allen anderen Knoten (also im prinzip den gesammten Graphen) durchgehen, nur um paar doofe eingehende kanten zu finden.
Wozu das gut sein soll, eingehende kanten zu suchen, sei erstmal dahingestellt. Zum beispiel ist mir keine bessere Möglichkeit eingefallen, einen gerichteten Graphen auf schwachen wegzusammenhang zu testen (oder geht's ohne?).
Ferner sollte es imho möglich sein, den Graphen ohne jeglichen Aufwand auf die "ungerichtete" Perspektive umzustellen (wie soll ich zB sonst die Wege für ego-shooter bots darstellen, die sich plötzlich levitationsbonus geschnappt haben, und jetzt alle wände hochkommen, von den man sonst nur runterfallen kann?)
Fragen:
Ist es sinnvoll, für jeden Knoten statt den ausgehenden sowohl ausgehende als auch eingehende verbindungen zu speichern? Dann wäre zwar jede Kante zwei mal drin, aber irgendwie wäre es imho wesentlich leichter zweischen der gerichteten und der ungerichteten Perspektive umzuschalten.
Bei Kanten die in beide Richtungen verlaufen wäre es aber dann wiederum total bescheuert: ein und dieselbe Verbindung müsste schon 4 mal gespeichert werden.
Soll ich evtl nicht direkte Referenzen auf nachbarknoten, sondern referenzen auf kanten abspeichern?
Oder gibt es eine bessere Möglichkeit, auf die ich bisher nicht gekommen bin?
Vielen Dank im voraus.
greetz, Andrey