<=<= <=<= <=<= <=<= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= Universität Stuttgart Fakultät Informatik ? Institut für Informatik Breitwiesenstraße 20-22 D-70565 Stuttgart Hierarchische Graphen zur kürzesten Wegesuche in planaren Graphen Friedhelm Buchholz und Bernhard Riedhofer Report Nr. 1997/13 August 1997  Zusammenfassung Für ungerichtete Graphen werden hierarchische und regionenhierarchische Graphen definiert. In planaren hierarchischen Graphen läßt sich die kürzeste Entfernung zwischen zwei Knoten in der Laufzeit O(pn) ermitteln (n sei die Anzahl der Knoten in dem gegebenen Graphen). Der kürzeste Weg mit l Knoten kann in O(pn + l) Operationen berechnet werden. Beide Typen von hierarchischen Graphen benötigen dabei O(n1:5) Platz für die Speicherung der Hilfstabellen. Während für den Aufbau von allgemeinen hierarchischen Graphen O(n2) Operationen benötigt werden, können regionenhierarchische Graphen in O(n1:5) Operationen aufgebaut werden. Zur Konstruktion der hierarchischen Graphen benutzen wir das Separatortheorem von Lipton und Tarjan [11]. 1 Einführung Die kürzeste Wegesuche ist ein ausführlich untersuchtes Problem in der Graphentheorie, das allerdings insbesondere in den letzten Jahren erneut bzgl. anderer Nebenbedingungen bearbeitet wird. Wenn man keine Preprocessing-Phase erlaubt, läßt sich die kürzeste Entfernung in einem planaren Graphen mit n Knoten in O(n) Zeit finden [10]. Wenn man in einer Preprocessing-Phase in O(n2) Operationen alle kürzesten Entfernungen berechnet und in einer Tabelle zwischenspeichert, kann man durch Zugriff auf die Tabelle in O(1) Operationen die kürzeste Entfernung bestimmen. Es stellt sich die Frage nach hierarchischen Datenstrukturen, die wenig Platz benötigen und sich in einer Preprocessing-Phase effizient konstruieren lassen, so daß die Entfernungsberechnung ebenfalls effizient möglich ist. Diese Fragestellung ist insbesondere im Bereich von Verkehrsinformationssystemen von großem Interesse. In [9],[1],[3],[4],[8],[13] finden sich diverse praktische Ansätze zur Hierarchiebildung, deren Effektivität zum Teil an realen Straßendaten nachgewiesen wurde. Leider wurden diese Verfahren entweder nicht bezüglich der Komplexität untersucht, oder sie berechnen lediglich Näherungen zum Bestweg. Um Komplexitätsuntersuchungen zu vereinfachen, d.h. um insbesondere die Ergebnisse der Separation von planaren Graphen ausnutzen zu können [11], betrachten wir in dieser Arbeit planare Graphen. Für diese konstruieren wir in einer Preprocessing-Phase in O(n1:5) Zeit auf O(n1:5) Platz einen hierarchischen Graph, der die Berechnung der kürzesten Entfernung zwischen zwei Knoten in O(pn) Zeit zusichert. Zur Berechnung kürzester Wege innerhalb unseres Verfahrens benutzen wir einen linearen Algorithmus, der von Klein u.a. entwickelt wurde [10]. Einzelne Ergebnisse dieser Arbeit sind auch in [12] nachzulesen. Die Arbeit ist folgendermaßen aufgebaut: Abschnitt 2 enthält grundlegende Definitionen, in Abschnitt 3 werden hierarchische Graphen definiert, und in Abschnitt 4 wird ein Konstruktionsverfahren für hierarchische Graphen vorgestellt. In Abschnitt 5 werden einige vorbereitende Überlegungen über den Verlauf von Wegen gemacht, die in den Abschnitten 6 und 7 beim Aufbau von gewichteten und regionengewichteten hierarchischen Graphen benutzt werden. Hinweise zur Implementierung und Ergebnisse von Experimenten sind in den Abschnitten 8 und 9 zusammengefaßt. 1  2 Definitionen In dieser Arbeit betrachten wir nur ungerichtete Graphen ohne Mehrfachkanten. Schlingen, d.h. Kanten von einem Knoten zu sich selbst, spielen bei unseren Untersuchungen keine Rolle, so daß wir darauf nicht weiter eingehen. Die Übertragung der Ergebnisse auf gerichtete Graphen bereitet keine Probleme. Ein ungerichteter Graph G = (V; E) besitzt die Knotenmenge V und die Kantenmenge E ? ffu; vg j u 2 V; v 2 V g. Der Graph heißt vollständig, wenn für die Kantenmenge gilt: E = ffu; vg j u 2 V; v 2 V g. Für beliebige Knotenmengen A; B ? V sei: [A; B] := ffa; bg j a 2 A; b 2 Bg In dem Graphen G = (V; E) induziert die Knotenmenge A ? V den Graph GA = (A; ffu; vg 2 E j u; v 2 Ag) Ein Graph G0 = (V 0; E0) ist ein Teilgraph vom Graphen G = (V; E), wenn gilt: V 0 ? V und E0 ? E (Schreibweise G0 ? G). Ein Graph G = (V; E) heißt planar, wenn sich der Graph G so in die Ebene zeichnen läßt, daß sich keine Kanten überkreuzen. Eine Menge fA1; A2; : : : ; Akg heißt eine Partition einer Menge M , wenn gilt: Ai ? M 8 1 <= i <= k M = k[ i=1 Ai Ai \ Aj = ; 8 1 <= i < j <= k Die Mächtigkeit einer Menge M bezeichnen wir mit jM j. Zu einem Graphen G = (V; E) heißt die Partition fA; B; Cg der Knotenmenge V eine Separation mit trennender Knotenmenge C , wenn gilt: E \ [A; B] = ;. Es gibt also keine Kante in E zwischen den Knotenmengen A; B. Ein Graph G = (V; E; ffi) ist ein Graph G = (V; E) mit Kantengewichtsfunktion ffi : E ! IR+. Ein Weg w = [u1; u2; : : : ; uk] im Graphen G ist eine Knotenfolge ui 2 V für 1 <= i <= k, wobei die Kanten fui; ui+1g für 1 <= i < k in der Kantenmenge E liegen. s(w) sei der Startknoten u1 des Weges w und e(w) sei der Endknoten uk. Der Weg w verläuft vollständig in einem induzierten Graphen G0 von G, falls w ein Weg in G ist und alle Knoten auf w in der Knotenmenge von G0 liegen. Die Kantengewichtsfunktion ffi sei wie folgt auf Wege w = [u1; u2; : : : ; uk] für k >= 2 (für k = 1 sei ffi(w) = 0) und Knotenpaare u; v 2 V fortgesetzt: ffi(w) := k?1 X i=1 ffi(fui; ui+1g) ffi(u; v) := minfffi(w) j s(w) = u; e(w) = v; w ist ein Weg in Gg Falls kein Weg von u nach v in G existiert, setzen wir ffi(u; v) := 1. Die endliche Menge ? nennen wir auch ein endliches Alphabet. Die Menge aller Wörter über dem Alphabet ? sei ?? := S1i=0 ?i. Dabei enthält ?i alle Wörter >= der Länge i (Schreibweise j>=j = i und ?0 = ffflg). ?i;j := f>= 2 ?? j i <= j>=j <= jg sind alle Wörter mit einer Länge zwischen i und j, wobei i <= j gelte. (>=)i sei das Präfix der Länge 0 <= i <= j>=j des Wortes >=. ffi bezeichne die Konkatenation von Wörtern. 2  3 Hierarchische Graphen Definition 1 Gegeben seien ein Graph G = (V; E) und das Alphabet ? = f1; 2g. HG := fG>= j >= 2 ?0;kg heißt hierarchischer Graph mit k Stufen von G, wenn gilt: 1. Für alle >= 2 ?0;k gilt: G>= = (R>=; [T>=; R>=]) ist ein Graph mit T>= ? R>=. 2. R- = V . 3. Für alle >= 2 ?0;k?1 und x 2 ? gilt: G>= = (R>=; [T>=; R>=]) 2 HG =) G>=ffix = (R>=ffix; [T>=ffix; R>=ffix]) 2 HG und R>=ffi1; R>=ffi2; T>= ist eine Separation von R>= mit trennender Knotenmenge T>= in dem von R>= induzierten Graphen GR>= ? G = (V; E). 4. Für alle >= 2 ?k gilt: T>= = R>=. Ein Graph G>= 2 HG heißt Graph der Stufe j>=j. r(v) = >= heißt der Regionenname des Knotens v 2 V , falls v 2 T>= gilt. Der Aufbau eines hierarchischen Graphen HG aus einem Graphen G erfolgt sukzessive von Stufe Null bis zur Stufe k. V = R- ist die Knotenmenge des obersten Graphen Gffl, d.h. der Graph der Stufe Null aus HG. Dann wird eine Separation R1; R2; T- von G mit der trennenden Knotenmenge T- festgelegt, wodurch der Graph G- = (Rffl; [Tffl; Rffl]) vollständig bestimmt ist. Die Graphen G1 = (R1; [T1; R1]) und G2 = (R2; [T2; R2]) werden durch Separation der Knotenmengen R1; R2 in R11; R12; T1 bzw. R21; R22; T2 bzgl. der durch R1; R2 in G induzierten Graphen bestimmt usw. Alle Graphen auf der Stufe k eines hierarchischen Graphen sind vollständig, da T>= = R>= ist. In Abbildung 1 ist ein planarer Graph und eine mögliche Separation in Teilgraphen dargestellt. Man beachte, daß die Graphen GR>= nicht zum hierarchischen Graphen gehören, sondern die von R>= in dem gegebenen Graphen induzierten Teilgraphen sind. Die trennenden Mengen auf der Stufe drei sind: T111 = fv1g; T112 = ;; T121 = fv3g; T122 = fv7g; T211 = fv10g; T212 = ;; T221 = fv14g; T222 = fv16g. Der Aufbau des zugehörigen hierarchischen Graphen HG ist in Abbildung 2 skizziert, und die Graphen Gffl; G1 2 HG sind exemplarisch dargestellt. Die Stufe 0 <= i <= k eines hierarchischen Graphen mit k+1 Stufen besteht aus 2i Graphen. Aus Gründen der Einfachheit haben wir nur den speziellen Fall des 'vollständig ausgeglichenen' hierarchischen Graphen definiert. Die Verallgemeinerung ergibt sich durch Entfernen von leeren Graphen. Definition 2 Seien f : IN ?! IR+ eine monoton wachsende Funktion und ff; fi 2 IR+ feste Parameter mit 12 <= ff < 1; fi >= 0. Ein hierarchischer Graph HG mit n Knoten in G- 2 HG heißt ff-fi-f(n)-HG, wenn für alle Graphen G>= = (R>=; [T>=; R>=]) 2 HG gilt: 1. jR>=j <= ffj>=jn und 2. jT>=j <= fif(jR>=j). 3  v4 v1 v2 v3 v5 v6 v7 v10 v11 v12 v13 v14 v15 v16 v10 v11 v12 v13 v14 v15 v16 v4 v1 v2 v3 v5 v6 v7 v8 v9 T- T1 T2 v4 v1 v3 v6 v7 v10 v12 v14 v15 v16 T11 T12 T21 T22 GR11 GR12 GR21 GR22 GR1 GR2 G = GR- Abbildung 1: Ein planarer Graph mit Separationen in Teilgraphen. Durch Einsetzen der ersten Bedingung in die zweite folgt: jT>=j <= fif(ffj>=jn). Dies werden wir bei den Komplexitätsuntersuchungen ausnutzen. Man beachte, daß ein hierarchischer fffi-f(n)-HG Graph , der nur nichtleere Graphen enthält, wegen Bedingung (1) nicht mehr als O(log n) nicht-leere Stufen besitzt. Für f(n) werden wir pn einsetzen, d.h. jede trennende Knotenmenge T>= enthält in einem ff-fi-pn-HG höchstens fipffj>=jn Knoten. 4 Aufbau eines hierarchischen Graphen Das folgende Theorem wurde in einer allgemeineren Form von Lipton und Tarjan bewiesen [11]. Theorem 1 Gegeben sei ein planarer Graph G = (V; E) mit n Knoten. Eine Separation fA; B; Cg von V mit trennender Knotenmenge C, die folgende Bedingungen erfüllt: - jAj; jBj <= ffn und - jCj <= fipn existiert für die Parameter ff = 12 ; fi = 2p2 1?p 23 <= 15:5 stets und kann in O(n) Operationen berechnet werden. 4  T- v4 v1 v2 v3 v5 v7 v10 v11 v12 v13 v15 v16 T1 v4 v1 v2 v3 v5 v7 G1 G2 G11 G12 G21 G22 G111 G112 G121 G122 G211 G212 G221 G222 G1 G- G- v6 v8 v6 v9 v14 Abbildung 2: Struktur eines hierarchischen Graphen HG und Gffl; G1 2 HG. Es wurden mehrfache Verbesserungen dieses Separatortheorems für die Parameter ff und fi angegeben, die in [5] und [7] nachgelesen werden können. Für die Komplexitätsuntersuchungen, die wir durchführen, sind die genauen Werte irrelevant, so daß wir ff und fi als konstant annehmen können. Theorem 2 Gegeben seien obige Parameter ff und fi und ein planarer Graph G = (V; E). Zu G läßt sich ein hierarchischer ff-fi-pn-HG Graph der Stufe O(log n) in O(n1:5) Operationen konstruieren. Beweis: Der hierarchische Graph habe k + 1 Stufen. Er wird sukzessive von Stufe Null bis zur Stufe k durch Anwendung des Separatortheorems 1 aufgebaut. Da die Separierung nur linearen Aufwand in der Anzahl der Knoten benötigt und in jeder Stufe weniger als n verschiedene Knoten existieren, ist insgesamt höchstens mit O(n log n) Operationen für die Separierung zu rechnen. Da die Knotenmengen T>= für alle >= 2 ?0;k paarweise diskunkt sind, ist zum Aufbau der Kantenmengen [T>=; R>=] in jedem Graph G>= 2 HG 5  folgender Aufwand notwendig: j [ >=2?0;k [T>=; R>=]j = X >=2?0;k j[T>=; R>=]j = X >=2?0;k jT>=jjR>=j <= |{z} nach Def. 2 kX i=0 fi q (ffin) X >=2?i jR>=j <= |{z} wegen P>=2?i jR>=j<=n fin1:5 kX i=0 (pff)i 2 |{z} wegen P1i=0(pff)i= 1 1?pff O(n1:5) Ein hierarchischer ff-fi-pn-HG Graph zu einem planaren Graph benötigt nach Theorem 2 höchstens den Speicheraufwand O(n1:5). In dem Beispiel ist ein hierarchischer 12 -1-pn-HG Graph dargestellt (siehe Abbildung 2). 5 Vorbereitung zur Wegsuche im hierarchischen Graphen Definition 3 Sei HG ein hierarchischer Graph zum Graphen G = (V; E). Für die Knoten u; v 2 V heißt LGG(u; v) = >= letzter gemeinsamer Graphname genau dann, wenn gilt: >= ist das längste gemeinsame Präfix von r(u) und r(v). Die Knotenmenge Rand(u; v) = SjLGG(u;v)j i=0 T(LGG(u;v))i heißt Randknotenmenge von u; v 2 V . Lemma 1 Gegeben sei ein hierarchischer Graph HG zu einem Graph G. In jedem Weg w, der vollständig in einem Teilgraphen GR>= für G>= = (R>=; [T>=; R>=]) 2 HG verläuft, aber für alle x 2 ? = f1; 2g nicht vollständig in GR>=ffix für G>=ffix 2 HG verläuft, gibt es einen Knoten v 2 T>=. Beweis: Da R>=ffi1; R>=ffi2; T>= eine Separation mit trennender Knotenmenge T>= in GR>= ist, folgt die Aussage. Lemma 2 Gegeben sei ein hierarchischer Graph HG zu dem Graphen G. Ein Weg w, der vollständig in GR>= für G>= 2 HG verläuft, verläuft auch vollständig in GR(>=)i für jedes 0 <= i <= j>=j. Beweis: Die Aussage folgt aus GR(>=)j ? GR(>=)i für 0 <= i <= j <= j>=j. 6  Theorem 3 Sei HG ein hierarchischer Graph zum Graphen G = (V; E). Für jeden Weg w von u nach v in G gibt es einen Knoten z 2 Rand(u; v), der auf dem Weg w liegt. Beweis: Sei LGG(u; v) = >=. Für den Fall u 2 T>= oder v 2 T>= sind wir bereits fertig, da u oder v der gesuchte Knoten ist. Im anderen Fall sei o.B.d.A. u 2 R>=ffi1 und v 2 R>=ffi2. Der Weg w verläuft vollständig in G, aber nicht vollständig in GR>=ffi1 und nicht vollständig in GR>=ffi2 . Nach Lemma 2 gibt es ein maximales 0 <= i <= j>=j, so daß w vollständig in GR(>=)i verläuft. Nach Lemma 1 gibt es dann einen Knoten z 2 T(>=)i, der auf w liegt. Aus Rand(u; v) = Sj>=ji=0 T(>=)i folgt das Theorem. In dem Beispiel ist der letzte gemeinsame Graphname LGG(v3; v4) = 1. Jeder Weg vom Knoten v3 zum Knoten v4 führt also über einen der Knoten Rand(v3; v4) = T- [ T1 = fv2; v5; v8; v9g (siehe Abbildung 1). Lemma 3 Sei ff-fi-pn-HG ein hierarchischer Graph zum Graphen G = (V; E). Es gilt für alle Knotenpaare u; v 2 V : jRand(u; v)j 2 O(pn). Beweis: Der hierarchische Graph habe k + 1 Stufen. Nach Definition 2 und 3 gilt: jRand(u; v)j <= jLGG(u;v)j X i=0 jT(LGG(u;v))ij <= kX i=0 fipffin <= fipn 1 X i=0 (pff)i 2 O(pn) 6 Gewichtete hierarchische Graphen Wir betrachten nun gewichtete planare Graphen und erweitern alle Graphen eines hierarchischen Graphen um eine Kantengewichtsfunktion. Definition 4 Der um die Kantengewichtsfunktion erweiterte hierarchische Graph HG zu dem Graphen G = (V; E; ffi) heißt gewichteter hierarchischer Graph zu G, wenn für alle Graphen G>= = (R>=; [T>=; R>=]; ffi>=) 2 HG gilt: ffi>=(fu; vg) = ffi(u; v) 8fu; vg 2 [T>=; R>=]: Theorem 4 Gegeben sei ein planarer Graph G = (V; E; ffi). Ein gewichteter hierarchischer Graph ff-fi-pn-HG zu G läßt sich in O(n2) Schritten berechnen. Beweis: Ohne die Kantengewichtsfunktion läßt sich der hierachische Graph HG nach Theorem 2 in O(n1:5) Schritten berechnen. Mit dem von Klein u.a. entwickelten Verfahren zur Berechnung der kürzesten Entfernung in O(n) Zeit in planaren Graphen lassen sich in O(n2) Zeit für alle Knotenpaare die kürzesten Entfernungen bestimmen [10]. 7  Zwar benötigen wir im hierarchischen Graphen nicht die Entfernung für jedes Knotenpaar, aber zur Berechnung der kürzesten Entfernungen auf den Stufen größer als Null im hierarchischen Graphen reicht die Betrachtung der induzierten Graphen nicht aus, sondern es muß der gesamte gegebene planare Graph einbezogen werden. Auch die Einbeziehung bereits berechneter Entfernungen bringt keine Laufzeitverbesserung, da die gesamte Randknotenmenge betrachtet werden muß (siehe auch [12]). Theorem 5 Gegeben sei ein gewichteter hierarchischer ff-fi-pn-HG Graph zu dem planaren Graphen G = (V; E; ffi). Die Länge des kürzesten Weges ffi(u; v) kann für je zwei beliebige Knoten u; v 2 V in O(pn) Operationen berechnet werden. Beweis: In O(log n) Schritten wird LGG(u; v) berechnet (vgl. Abschnitt 8). Dann wird ein Knoten z 2 Rand(u; v) mit folgender Eigenschaft gesucht: ffi(u; z) + ffi(z; v) = minfffi(u; y) + ffi(y; v) j y 2 Rand(u; v)g Nach Theorem 3 gilt: ffi(u; v) = ffi(u; z) + ffi(z; v), und nach Lemma 3 (jRand(u; v)j 2 O(pn)) folgt die Behauptung. In dem Beispielgraphen aus Abschnitt 3 sei das Kantengewicht ffi(fv1; v4g) = 3 und alle anderen Kantengewichte seien eins. Dann ergibt sich der in Abbildung 3 dargestellte Teilgraph G1 2 HG für den gewichteten hierarchischen Graphen. Die kürzeste Entfernung ffi(v3; v4) = 4 läßt sich durch die Betrachtung von Rand(v3; v4) = fv2; v5; v8; v9g ermitteln. T1 v4 v1 v2 v3 v7 1 3 3 3 2 2 1 1 G1 3 2 1 v6 v5 Abbildung 3: Gewichteter Teilgraph G1 2 HG. Wenn ein kürzester Weg mit l Knoten ausgegeben werden soll, sind dazu weitere O(l) Operationen aufzuwenden. Für jede Kante in einem Graphen G>= des hierarchischen Graphen, an der nach Definition 4 der kürzeste Weg vermerkt ist, muß dazu ein Knoten auf diesem kürzesten Weg gespeichert werden. Da auch die Teilwege von kürzesten Wegen kürzeste Wege sind, kann anhand dieser Knoten durch erneuten Zugriff auf den Graphen G>= in O(l) Operationen der kürzeste Weg zusammengesetzt werden. 7 Regionengewichtete hierarchische Graphen Die Kantengewichte in gewichteten hierarchischen Graphen entsprechen immer den kürzesten Entfernungen im zugrundeliegenden Graphen. Es reicht jedoch für die Wegberechnung mit 8  dem hierarchischen Graphen aus, die kürzeste Entfernung in einem induzierten Teilgraphen des zugrundeliegenden Graphen zu vermerken. Für eine Kante des Graphen G>= = (R>=; [T>=; R>=]) 2 HG werden wir die kürzeste Entfernung bezogen auf den von R>= in G induzierten Graphen GR>= bestimmen. Definition 5 Der hierarchische Graph HG zu G = (V; E; ffi) heißt regionengewichteter hierarchischer Graph, falls für alle G>= = (R>=; [T>=; R>=]; ffi>=) 2 HG und für alle Kanten fu; vg 2 [T>=; R>=] gilt: ffi>=(fu; vg) = ffiR>=(u; v) Dabei ist ffiR>= die auf Knoten fortgesetzte Kantengewichtsfunktion in dem von R>= ? V in G induzierten Graphen. Der regionengewichtete hierarchische Graph zum Beispielgraphen aus Abschnitt 3 als gewichteter Graph mit ffi(fv1; v4g) = 3 (alle anderen Kantengewichte seien eins) ist wiederum exemplarisch für G1 2 HG in Abbildung 4 dargestellt. T1 v4 v1 v2 v3 v7 1 3 3 2 2 1 1 G1 4 4 1 4 v6 v5 Abbildung 4: Regionengewichteter Teilgraph G1 2 HG. Theorem 6 Gegeben sei ein planarer Graph G = (V; E; ffi). Ein regionengewichteter hierarchischer ff-fi-pn-HG Graph zu G läßt sich in O(n1:5) Operationen berechnen. Beweis: Nach Theorem 2 wird der hierarchische Graph HG ohne die Kantengewichtsfunktion in O(n1:5) Operationen berechnet. Um die Kantengewichte ffi>=(fu; vg) für einen Knoten u 2 T>= und alle Knoten v 2 R>= zu bestimmen, genügt es, den Algorithmus aus [10] in dem planaren Teilgraphen GR>= ? G einzusetzen. Im worst-case wird somit höchstens der Aufwand O(jR>=j) benötigt. Zur Berechnung von allen Kantengewichten von [T>=; R>=] für alle Graphen G>= 2 HG ergibt sich nach den selben Gleichungsumformungen wie im Beweis zu Theorem 2 für einen hierarchischen Graphen mit k + 1 Stufen: X >=2?0;k jT>=jO(jR>=j) 2 O(n1:5) 9  Um nachzuweisen, daß die Bestimmung der kürzesten Entfernung mit regionengewichteten hierarchischen Graphen in O(pn) Zeit möglich ist, beziehen wir uns auf das Theorem 3: Jeder Weg von einem Knoten u 2 V zu einem Knoten v 2 V enthält einen Knoten aus Rand(u; v). Die kurze Argumentation im Beweis zu Theorem 5 reicht hier nicht aus, da im regionengewichteten Graphen die Kantengewichte i.A. nicht den kürzesten Entfernungen im zugrundeliegenden Graphen entsprechen. Theorem 7 Sei ff-fi-pn-HG ein regionengewichteter hierarchischer Graph zu einem Graphen G. Die Länge des kürzesten Weges ffi(u; v) kann für je zwei beliebige Knoten u; v 2 V in O(pn) Operationen berechnet werden. Beweis: Wir verfolgen zunächst dieselbe Argumentation wie in Theorem 3. Sei LGG(u; v) = >=, und o.B.d.A. seien u 2 R>=ffi1 und v 2 R>=ffi2. Nach Lemma 2 gibt es ein maximales 0 <= i <= j>=j, so daß der kürzeste Weg w von u nach v vollständig in GR(>=)i verläuft. Nach Lemma 1 gibt es dann einen Knoten z 2 T(>=)i, der auf w liegt. Es gilt also: ffi(w) = ffi(u; z) + ffi(z; v) = ffiR(>=)i(u; z) + ffiR(>=)i(z; v) Da im regionengewichteten hierarchischen Graphen für alle Kanten fp; qg 2 [T(>=)i; R(>=)i] gilt: ffi(>=)i(fp; qg) = ffiR(>=)i(p; q) genügt die Betrachtung von Rand(u; v), um die Länge des kürzesten Weges von u nach v zu bestimmen. Nach Lemma 3 (jRand(u; v)j 2 O(pn)) folgt das Theorem. In dem gewichteten Beispiel (ffi(fv1; v4g) = 3) gibt es zwei kürzeste Wege zwischen v3 und v4, die beide über den Knoten v8 führen (siehe Abbildung 1). In dem Graphen G- des regionengewichteten hierarchischen Graphen HG gibt es die Kanten fv4; v8g; fv3; v8g mit folgenden Kantengewichten: ffiffl(fv4; v8g) = ffiRffl(v4; v8) = 1 und ffiffl(fv3; v8g) = ffiRffl(v3; v8) = 3. Die Betrachtung der Randknotenmenge Rand(v3; v4) genügt wiederum, um die kürzeste Entfernung zwischen v3 und v4 zu bestimmen. In regionengewichteten hierarchischen Graphen wird nach Theorem 7 analog zu den gewichteten hierarchischen Graphen ein kürzester Weg mit l Knoten in O(pn+ l) Operationen berechnet. 8 Implementierung Der zugrundeliegende Graph sei in Form von Adjazenzlisten gespeichert. Bei der Separierung sind zum einen die induzierten Teilgraphen des zugrundeliegenden Graphen ebenfalls in Form von Adjazenzlisten zu speichern. Dies ist in jeder Stufe in O(n) Zeit möglich. Zum anderen wird die Kantengewichtsfunktion jedes Graphen G>= = (R>=; [T>=; R>=]; ffi>=) eines hierarchischen Graphen in einer Tabelle mit jR>=j Zeilen und jT>=j Spalten gespeichert, so daß der Zugriff für ein Knotenpaar in konstanter Zeit möglich ist. Jeder Tabelleneintrag Tab(u; v) enthält neben dem Kantengewicht den nächsten Knoten nach u, der auf dem kürzesten Weg von u nach v liegt. Dieser Knoten wird gebraucht, um den kürzesten Weg ausgeben zu können. Außerdem wird bei der Separation ein Baum B mit den Wörtern >= 2 ?0;k als Knoten aufgebaut, bei 10  dem für jeden Knoten >= ein Verweis auf die trennende Menge T>= mitgeführt wird. Für jeden Knoten v 2 V des zugrundeliegenden Graphen wird weiterhin der Regionenname r(v) (falls v 2 T>=) vermerkt. Die Berechnung des kürzesten Weges zwischen u; v 2 V erfolgt dann in zwei Schritten: 1. Berechne LGG(u; v). Dies ist das längste gemeinsame Präfix von r(u) und r(v), d.h. es werden höchstens O(log n) Operationen benötigt. 2. Minimumbildung über Rand(u; v). Im Baum B werden vom Knoten LGG(u; v) (direkter Zugriff) auf dem Pfad bis zur Wurzel die trennenden Mengen aufgesucht. Das Kantengewicht kann jeweils durch einen Zugriff auf die angelegten Tabellen ermittelt werden. 9 Experimente Da Straßennetze in der Regel wegen Brücken und Untertunnelungen nur fast planar sind, läßt sich das Separatortheorem nicht direkt anwenden. Stattdessen haben wir eine Heuristik zur Separation verwendet. Die uns vorliegenden Straßendaten sind im GDF-Format gespeichert, in dem die Straßen in neun Geschwindigkeitsklassen eingeteilt sind. Das Straßennetz vom Großraum Stuttgart mit 15224 Knoten und 38032 Kanten wurde sukzessive von der Stufe i = 0 bis zur Stufe i = 8 entlang der Straßen der Klasse i separiert. Da bei jeder Separation mindestens fünf verschiedene Zusammenhangskomponenten aufgetreten sind, haben wir einen hierarchischen Graphen zu ? = f1; 2; 3; 4; 5g konstruiert. Der Graph besitzt neun Stufen und benötigt 42.8 MBytes Speicherplatz. Schon das Stuttgarter Straßennetz benötigt 3.5 MBytes. Dieser spezielle hierarchische Graph ist ein ff-fi-pn-HG mit ff = 12 und fi = 52 . Auf einer SPARCstation 10=40 mit 128 MBytes Hauptspeicher ergaben sich unter dem Betriebssystem SunOS 5.4 folgende Laufzeiten: Der gewichtete hierarchische Graph wurde in 104 Minuten aufgebaut, und die Berechnung der kürzesten Entfernung benötigt im average-case 0:305 Millisekunden. Im Vergleich dazu brauchte der Dijkstra Algorithmus 586 Millisekunden [6]. Eine vollständige Tabelle für die Entfernungen aller Knotenpaare braucht fast 0:5 GBytes an Speicherplatz, die nicht im Hauptspeicher untergebracht werden konnten. Die reine CPU- Zeit zur Entfernungsberechnung beträgt unter 0.3 Millisekunden, aber da ein Plattenzugriff notwendig ist, ergibt sich eine gesamte Laufzeit von durchschnittlich 60 Millisekunden pro Tabellenzugriff. 10 Ausblick Wir werden versuchen, die Ergebnisse von planaren Graphen auf dünne Graphen ((jEj 2 O(n)) zu verallgemeinern. Zwar haben Bui und Jones in [2] nachgewiesen, daß bereits die Separation von Graphen mit Grad drei auch für Näherungen NP-hart ist, aber uns genügen Separationen der Größe O(pn). Für Verkehrsinformationssysteme ist es entscheidend, daß ein Update auf dem zugrundeliegenden Straßennetz nur zu kleinen Änderungen in der hierarchischen Struktur führt. Da sich Straßennetze jährlich durchschnittlich um 5 % ändern, wäre eine Neuberechnung der hierarchischen Struktur bei jeder Änderung inakzeptabel. Es sind die Bedingungen festzustellen, unter denen ein Update nur kleine Änderungen des hierarchischen Graphen nach sich zieht. 11  Literatur [1] R. Agrawal and H.V. Jagadish. Algorithms for searching massive graphs. IEEE Transactions on knowledge and data engineering, 9(2):225 { 238, april 1994. [2] T. N. Bui and C. Jones. Finding good approximate vertex and edge partitions is NP-hard. Information Processing Letters, 42(3):153{159, may 1992. [3] A. Car and A.U. Frank. Modelling a hierarchy of space applied to large road networks. In Proceedings of IGIS'94, International Workshop on Advanced Research in Geographic Information Systems, pages 15{24, Ascona, Switzerland, 1994. [4] Adrijana Car. Hierarchical Spatial Reasonig: Theoretical Consideration and its Application to Modeling Wayfinding. PhD thesis, Department of Geoinformation der TU Wien, 1996. Geoinfo-Serie Nr. 10. [5] Chung. Improved separators for planar graphs. In ICTAG: 6th Quadrennial International Conference on the Theory and Applications of Graphs, 1991. [6] E.W. Dijkstra. A note on two problems in connection with graphs. Numerical Mathematics, 1:269 { 271, 1959. [7] Djidjev and Venkatesan. Reduced constants for simple cycle graph separation. Acta Informatica, 34:231 { 243, 1997. [8] K. Ishikawa, S. Azume M. Ogawa, and T. Ito. Map navigation software of the Electro Multivision of the `91 Toyota Soarer. In Int. Conf. on Vehicle Navigation and Information Systems (VNIS IVHS), IEEE, pages 463{473, 1991. [9] S. Jung and S. Pramanik. HiTi graph model of topographical road maps in navigation systems. In Proc. IEEE 12th Int. Conf. Data Engineering, pages 76{84. New Orleans, LA, 1996. [10] Philip N. Klein, Satish Rao, Monika H. Rauch, and S. Subramanian. Faster shortest-path algorithms for planar graphs. In Proc. 26th Symp. Theory of Computing, pages 27{37. Assoc. for Computing Machinery, 1994. [11] R.J. Lipton and R.E. Tarjan. A separator theorem for planar graphs. SIAM Journal Appl. Math., 36:177 { 189, 1979. [12] Bernhard Riedhofer. Hierarchische Strassengraphen. Diplomarbeit 1452, Universität Stuttgart, Institut für Informatik, 1997. [13] Jacob Shapiro, Jerry Waxman, and Danny Nir. Level graphs and approximate shortest path algorithms. Networks, 22:691{717, 1992. 12