Verwaltung von Wegen in einem Netz

Hallo

für folgende Aufgabe suche ich einen geeigneten Ansatz oder Tipps, wie ich damit beginnen könnte:

es gibt Knoten und ungerichtete Kanten
bei den Knoten handelt es sich um Elemente unterschiedlicher Typen mit verschiedenen Attributen (also in verschiedenen Tabellen), die jeweils verbunden sind mit maximal vier Nachbarn über genannte ungerichtete Kanten ohne Attribute

automatisch verwaltet werden soll nun eine Tabelle von “Wegen” durch das Netz, diese “Wege” haben weiterhin Attribute, werden daher in einer weiteren Tabelle geführt

die Knoten unterteilen sich für die relevante Aufgabe in drei Typen:

  • Startelemente
    solche Knoten, an denen Wege beginnen können
  • Zielelemente
    solche Knoten, an denen Wege enden können
  • Via-Elemente
    solche Elemente, die auf dem Weg durchlaufen werden (das können konkret auf einem Weg 0 bis 255 sein)
    diese haben aber noch eine Besonderheit: elementtypabhängig ist nicht jede “Durchverbindung” durch den Knoten erlaubt, also ist ein Via zB. nur zwischen Nachbar 1 und 2 und umgekehrt und Nachbar 1 und 3 und umgekehrt erlaubt, aber nicht zwischen den Nachbarn 2 und 3 erlaubt


    die Aufgabe lautet nun, die Wege-Tabelle automatisch zu verwalten: wird ein neuer Knoten oder eine neue Kante angelegt, soll automatisch gesucht werden, ob dadurch ein neuer Weg von einem Startelement zu einem Zielelement möglich wird und im gegebenen Fall eine neuer Eintrag in der Wegetabelle angelegt werden, wird ein Knoten oder eine Kante gelöscht, sollen die darüberverlaufenden Wege aus der Tabelle gelöscht werden.


    Eventuell wird zu einem späteren Zeitpunkt auf gleichem Netz noch eine verwandte Aufgabe entstehen: dort soll eine Art “Gruppen-Tabelle” ebenso automatisch verwaltet werden, wobei die Knoten dort in zwei Typen eingeteilt werden: “innere Elemente” und “Grenzen”. In diesem Fall soll in der Gruppen-Tabelle jeweils ein Eintrag für eine zusammenhängende Gruppe von “inneren Elementen” geführt werden. Wird hierbei ein Knoten angelegt, bildet er erstmal eine eigene Gruppe, wird dann eine Kante angelegt, müssen die so verbundenen Gruppen zusammengeführt werden, wird eine Kante gelöscht, muss die Gruppe, in der sie lag, geteilt werden, es sei denn, die Elemente sind noch über einen anderen Weg verbunden. “Grenzknoten” wirken dabei genauso wie ein Fehlen einer Kante an dieser Stelle.

Zunächst einmal wäre ich für alle Tipps dankbar, wie derartiges in einer PostgreSQL Datenbank am besten verwaltet werden kann, möglichst sollten die benötigten Funktionen in plpgsql umgesetzt werden

Ganz toll wäre es natürlich, wenn schon einmal jemand ein ähnliches Problem hatte und mir weitere Tipps dazu geben könnte…

Vielen Dank
Markus

Hast Du 8.4 oder neuer?

Falls ja: es gibt da irgendwo ein PDF von David Fetter, in dem es um CTE bzw. writeableCTE geht. In diesem ist ein Beispiel für den ‘traveling salesman’, mit Lösung in SQL.


Andreas