Contraction Hierarchies für kontinuierliche Graphsimplifizierung

Abstract

Mithilfe von Contraction Hierarchies lassen sich kürzeste Pfade eines Graphen effizient finden. Hierbei findet vor der eigentlichen Suche des kürzesten Pfades eine Vorverarbeitung statt, deren zentrale Operation die Kontraktion von Knoten ist. Hierbei wird der entsprechende Knoten zunächst aus dem Graphen entfernt; falls dadurch die kürzeste-Wege-Distanz der benachbarten Knoten vergrößert wird, werden dem Graphen neue Kanten, sogenannte Shortcuts, hinzugefügt. Durch die iterative Entfernung der Knoten kann jedoch auch eine Simplifizierung des Originalgraphen durchgeführt werden. Hierzu werden in dieser Arbeit verschiedene Kontraktionsreihenfolgen untersucht. Die betrachteten Kriterien zur Sortierung der Knoten sind die Edge Difference, die räumliche Dichte der Knoten, die durchschnittliche Kantendistanz der zum Knoten inzidenten Kanten sowie (bei Knoten vom Grad zwei) der Winkel der zum Knoten inzidenten Kanten. Hierzu wird ein Verfahren erläutert, mit dem die unterschiedlichen Kriterien miteinander kombiniert werden können. Des Weiteren wird ein Verfahren vorgestellt, mit dem aus der Ausgabe der Vorverarbeitung ein simplifizierter Graph erzeugt werden kann. Dabei werden Knoten abhängig vom Zeitpunkt ihrer Kontraktion aus dem Graphen entfernt. Von den verbleibenden Kanten werden zu lange Shortcuts rekursiv entpackt, d.h. durch die ursprünglichen Kanten ersetzt.