7. Graphen mit Kantenkosten

7.6 Union by Rank with Path Compression

Wir fügen der UnionByRank-Datenstruktur eine kleine Optimierung hinzu: wenn wir $\find(u)$ ausführen und den Pfad von $u$ hinauf zur Wurzel $x$ gelaufen sind, biegen wir alle parent-Zeiger der Knoten auf dem Pfad um und lassen sie auf $x$ zeigen. Es gilt danach also $\parent[v] = x$ für $x$ und alle seine Vorfahren. Durch diesen Trick werden die Bäume "flacher" und zukünftige find-Operationen billiger. Man nennt dies Path Compression, weil lange Pfade "zusammengepresst" werden. Die Datenstruktur nennen wir UnionByRankPathCompression.

Der Code unterscheidet sich nur minimal von UnionByRank:

class UnionByRankPathCompression:
    def __init__(self, n):
        self.parent = [i for i in range(n)] # jedes Element ist Wurzel seines eigenen Baumes 
        self.rank = [2 for i in range(n)] # jedes Element hat Rang 2 

    def find(self,u):
        
        if self.parent[u] == u:
            return u 
        else:
            root = self.find(self.parent[u])
            self.parent[u] = root # hier findet die Path Compression statt. Wir richten den parent-Zeiger von u direkt auf die Wurzel 
            return root
    
    def union(self, u, v):
        x = self.find(u)
        y = self.find(v)
        if (x == y):
            return # u, v sind bereits in der gleichen Menge 

        if self.rank[x] < self.rank[y]:
            self.parent[x] = y 
        elif self.rank[x] > self.rank[y]:
            self.parent[y] = x 
        else: 
            self.parent[x] = y 
            self.rank[y] += 1

    def __str__(self):
        return (str(self.parent))

# example < < > > & & 

Beachten Sie, dass nach Ausführung von $\find(e)$ und Umbiegen der Zeiger $\rank(h) = 4$ aber $\height(h) = 1$ gilt:

Die Gleichung $\rank(x) = \height(x)+2$ gilt also nicht mehr notwenigerweise. Allerdings gilt immer noch:

Laufzeitanalyse

Das Umbiegen der Zeiger direkt zur Wurzel hin wirkt wie eine kleine Optimierung der Implementierung. Tatsächlich aber führt es aber zu einer asymptotisch besseren Laufzeit. Und deren Analyse stellt sich als äußerst überraschend heraus.

Dicke Kanten und normale Kanten. Wenn $v = \parent(u)$ ist, dann gilt $\rank(v) \gt \rank(u)$. Soviel ist kar. Manchmal allerdings ist $\rank(v)$ deutlich größer als $\rank(u)$. Wir definieren: Die Kante $(u,v)$ ist eine dicke Kante wenn $\rank(v) \geq 2\, \rank(u)$. Der Knoten $u$ heißt dick wenn seine ausgehende Kante dick ist. Kanten und Knoten, die nicht dick sind, heißen dünn.

Wir führen nun eine amortisierte Laufzeitanalyse durch. Die Kosten einer find-Operation sind $O(1 + $Anzahl der Zeiger-Umbiegungen$)$. Der Einfachheit halber zählen wir nur die Zeiger-Umbiegungen. Im Worst-Case werden die auch dominieren. Die Kosten einer union-Operation werden von denen der beiden find-Operationen (Zeile 16, 17) dominiert. Es langt also völlig aus, die Gesamtzahl der Zeiger-Umbiegungen zu zählen. Jede Umbiegung kostet einen Euro, und wir müssen nun festlegen, wem diese Kosten in Rechnung gestellt werden. Betrachten wir also einen Zeitpunkt, wo parent[x] geändert wird.

1. Wenn $x$ ein dünner Knoten ist aber nicht die Wurzel, dann muss $x$ einen Euro bezahlen.
2. Wenn $x$ dick ist oder die Wurzel, dann bezahlt die find-Operation einen Euro.

Die Gesamtkosten über $m$ find-Operationen ergeben sich aus den zwei folgenden Behauptungen:

Als nächstes betrachten wir ein Element $x$ und die Anzahl von Euros, die es bezahlen muss. Wenn es überhaupt etwas bezahlen muss, dann wird irgendwann erstmals parent[x] verändert und $x$ hört zu diesem Zeitpunkt auf, eine Wurzel zu sein. Sei $k$ der Wert von $\rank(x)$ zu diesem Zeitpunkt. Beachten Sie, dass sich dieser Wert von nun an nicht mehr ändert.

Rechnen wir nun aus, wieviele Euros von den Elementen selbst bezahlt werden müssen. Dafür betrachten wir den Zustand der Datenstruktur nach Abschluss aller union- und find-Operationen und die Werte von $\rank(x)$ zu diesem Zeitpunkt. Die Gesamtkosten, die die Elemente selbst tragen müssen, sind also nach Behauptung 7.6.3 höchstens

\begin{align} \sum_{x} \rank(x) & = \sum_{k=2}^\infty k \cdot \left(\textnormal{Anzahl der Elemente mit Rang }\right) \nonumber \\ & \leq \sum_{k=2}^\infty k \cdot \frac{n}{2^{k-2}} \tag{Lemma 7.6.1} \\ & = \frac{n}{4} \cdot \sum_{k=1}^\infty k 2^{-k} \label{cost-by-elements} \end{align}

Werten wir nun die unendliche Summe aus (das sollten Sie sich sowieso merken):

\begin{align*} X & := \sum_{k=1}^{\infty} k 2^{-k} = \frac{1}{2} + \sum_{k=2}^{\infty} k 2^{-k} \\ & = \frac{1}{2} + \sum_{j=1}^{\infty} (j+1) 2^{-j-1} \tag{mit $j := k-1$}\\ & = \frac{1}{2} + \sum_{j=1}^\infty 2^{-j-1} + \sum_{j=1}^\infty j 2^{-j-1} \\ & = \underbrace{\frac{1}{2} + \left(\frac{1}{4} + \frac{1}{8} + \frac{1}{16} + \cdots \right)}_{=1} + \frac{1}{2} \cdot \underbrace{\sum_{j=1}^\infty j 2^{-j}}_{= X} \end{align*}

Also gilt $X = 1 + X/2$ und somit $X = 2$. Daher

\begin{align*} (\ref{cost-by-elements}) = \frac{n}{4} \cdot \sum_{k=2}^\infty k 2^{-k} = \frac{n}{2} \ . \end{align*}

Fassen wir zusammen: jede find-Operation muss $O(\log \log n)$ Euro bezahlen tragen, und die Elemente müssen insgesamt höchstens $n/2$ Euro bezahlen. Daher schließen wir:

Mit Path Compression und dem Begriff der dicken Kante / des dicken Knotens konnten wir die Laufzeit also von $O(m \log n + n)$ für UnionByRank auf $O(m \log \log n + n)$ verbessern. Um es noch einmal zu formulieren: ein dünnes Nicht-Wurzel-Element von Rang $k$ muss höchstens $k$ Euro bezahlen, danach wird es nämlich dick und muss nichts mehr bezahlen.

Dünn, dick, ultra-dick

Warum sollen wir mit dick aufhören? Könnten wir nicht folgendermaßen argumentieren: nachdem es $k$ Euros bezahlt hat, wird ein Element dick; nach weiteren $k$ Euros wird es ultradick; es von jetzt an übernimmt die find-Operation die Kosten. Wie sollen wir ultra-dick definieren?

Bisher war Knoten $u$ vom Rang $k$ dick wenn $\rank(\parent(u)) \geq 2 \cdot \rank(u)$. Wenn es oberhalb von $u$ einen weiteren dicken Knoten $x$ gibt, die Dinge also so aussehen:

Dann wird sich, wenn parent[u] geändert wird, der Rang von parent[u] auf mindestens $4k$ erhöhen. Das gilt aber nur, wenn es oberhalb von $u$ einen weiteren dicken Knoten gibt. Nach $i$ solches Umbiegungen wird der Rang von parent[u] auf mindestens $2^{i+1} k$ angewachsen sein. Nach $k$ Umbiegungen also auf mindestens $2^{k} k$. Wir definieren nun: sei $u$ ein Knoten von Rang $k$, der keine Wurzel ist, und $v = \parent(u)$. Wir bezeichnen $u$ als

• dünn, wenn $\rank(v) \lt \rank(u)$ gilt;
• dick, wenn $2k \leq \rank(v) \lt k 2^{k}$ gilt;
• ultra-dick, wenn $k2^{k} \leq \rank(v)$.

Als nächstes legen wir fest, wer welche anfallenden Kosten bezahlen muss. Zur Erinnerung: jedes Mal, wenn ein parent[u]-Zeiger umgebogen wird, wird ein Euro fällig. Wir legen fest:

• Die find-Operation zahlt die Euros für die Wurzel und die ultra-dicken Knoten; darüberhinaus für den obersten dicken und den obersten dünnen Knoten auf dem Pfad.
• Die restlichen Euros werden von den jeweiligen Knoten selbst getragen.

Überlegen wir uns informell, wie hoch die Anzahl $s$ von ultradicken Knoten auf einem Pfad werden kann. Seien $u_1, \dots, u_s$ die ultradicken Knoten auf dem Pfad, von unten nach oben aufgelistet. Sei $v_i = \parent(u_i)$. Da $u_{i+1}$ ein Vorfahre von $v_i$ ist, gilt $\rank(u_{i+1}) \geq \rank(v_i)$. Da die Kante $u_i$ dick ist, gilt $\rank(v_i) \geq \rank(u_i) \cdot 2^{\rank(u_i)}$. Also gilt

\begin{align*} \rank(u_1) & \geq 2 \\ \rank(u_2) & \geq 2 \cdot 2^2 = 8 \\ \rank(u_3) & \geq 8 \cdot 2^8 = 2048 \\ \rank(u_4) & \geq 2048 \cdot 2^{2048} \\ \rank(u_5) & \geq 2048 \cdot 2^{2048} \cdot 2^{ 2048 \cdot 2^{2048}} \end{align*}

In jeder realistischen Anwendung ist bereits ein Knoten wie $u_4$ völlig unrealistisch. Die maximal mögliche Anzahl ultradicker Knoten auf einem Pfad ist also eine extrem langsam wachsende Funktion in $n$. In der Tat in etwa $\log^*(n)$. Dies ist die Anzahl, wie oft Sie auf dem Taschenrechner $\log$ drücken müssen, um von $n$ zu $0$ oder weniger zu kommen. Jede find-Operation muss also höchstens $O(\log^* (n))$ Euros bezahlen.

Wie sieht es mit den Kosten aus, die ein Element bezahlen muss? Sei $u$ ein Element von Rang $k$ muss. Anfangs ist es ein dünnes Element. Nachdem es $k$ Euros bezahlt hat, hat sein Elternknoten mindestens Rang $2k$ und $u$ zählt von nun an als dick. Nach weiteren $k$ Euros wird $u$ einen Elternknoten vom Rang mindestens $k 2^k$ haben: jeder zusätzliche Euro beschert $u$ einen Elternknoten mit mindestens doppelt so hohem Rang als zuvor. Nach insgesamt $2k$ Euros ist $u$ ultra-dick geworden und muss von nun an nichts mehr selbst bezahlen. Die Gesamtkosten, die von den Elementen getragen werden müssen, sind also höchstens

\begin{align*} \sum_{u} 2\ \rank(u) & = \sum_{k=2}^\infty 2k \cdot (\textnormal{Aznahl der Elemente von Rankg $k$}) \\ & \leq \sum_{k=2}^\infty 2k \cdot \frac{n}{2^{k-2}} = n \ . \end{align*}

Wir sehen: dadurch, dass wir den Begriff der ultra-dicken Knoten eingeführt haben, konnten wir die Laufzeitanalyse von $O(m \log \log m + n)$ auf $O(m \log^*(m) + n)$ verbessern. Fassen wir zusammen:

1. Ohne Path Compression: $O(m \log (m) + n)$
2. Mit Path Compression, Analyse mit dünnen und dicken Knoten: $O(m \log \log (m) + n)$
3. Mit Path Compression und Analyse mit dünnen, dicken und ultra-dicken Knoten: $O(m \log^*(m) + n)$.

Wir können nun immer weitermachen und neue Dickheitsgrade einführen.

Beliebig viele Dickheitsgrade

Um ein Gefühl für die $f_i$ zu bekommen, spielen wir mit kleinen Werten von $i$ herum. Was ist $f_1(k)$? Nach Definition ist es das Ergebnis, wenn wir $f_0$ insgesamt $k$ mal auf $k$ anwenden. Also $2k$. Was ist $f_2(k)$? Wir haben gerade gesehen, dass $f_1$ die Verdopplung ist. Wir müssen nun $k$ insgesamt $k$ mal verdoppeln. Wir erhalten $k 2^k$. Alos gilt $f_2(k) = k 2^k$. Wir definieren nun den Dickheitsgrad eines Elements $u$.

Da $f_{i+1}(k) \gt f_i(k)$ gilt, gibt es genau ein solches $i$, und somit hat jedes Element eine Dickheit. Wir legen nun fest, welche Zeiger-Umbiegungen von wem getragen werden. Sei hierfür $u$ ein Element von Dickheit $i$.

• Wenn $u$ auf dem Pfad zur Wurzel das oberste Element von Dickheit $i$ ist, dann werden Umbiegungskosten von der find-Operation direkt getragen.
• Wenn es oberhalb von $u$ einen weiteren Knoten von Dickheit $i$ gibt, dann muss $u$ die Umbiegungskosten selbst bezahlen.

Dies gilt offensichtlich, weil die find-Operation nur für das jeweils oberste Element in einer Dickheitsstufe die Kosten übernimmt. Davon kann es höchstens $s$ viele geben. Etwas schwieriger wird es, wenn wir herausfinden wollen, wieviel Kosten ein einzelnes Element $u$ tragen muss. Hier ist eine Grafik, die illustriert, was geschieht, wenn ein Element $u$ von Rang $k$ und Dickheit $i$ Kosten tragen muss:

Anfangs ist $\rank(\parent(u)) \geq f_i(k)$. Wenn $u$ nun das nächste Mal einen Euro (in der Grafik einen Yuan) bezahlen muss, dann nur, weil es weiter oben einen weiteren Knoten $x$ mit Dickheit $i$ geben muss. Es gilt daher zu diesem Zeitpunkt:

\begin{align*} \rank({\rm root}) \geq \rank(\parent(x)) \geq f_i (\rank(x)) \geq f_i(\parent(u)) \geq f_i (f_i (u)) \ . \end{align*}

Durch das Umbiegen steigt also der "Eltern-Rang" von $u$ von $f_i(k)$ auf $f_i(f_i(k))$. Mit jedem weiteren Yuan kommt ein $f_i$ hinzu, und so steigt der Rang von $\parent(u)$ nach $k-1$ Yuans auf mindestens

\begin{align*} \underbrace{f_i (f_i (\dots f_i}_{k \textnormal{ mal}}(k))) = f_{i+1} (k) \ , \end{align*}

und $u$ hat von nun Dickheit mindestnes $i+1$. Pro Dickheit bezahlt $u$ also höchstens $k-1$ Yuan. Anfangs ist die Dickheit $0$, und zum Schluss ist sie höchstens $s$, die höchste jemals in der Datenstruktur vorkommende Dickheit. Also muss $u$ insgesamt höchstens $(k-1)s$ bezahlen. Runden wir es auf auf $ks$. Die Gesamtkosten, die von den Elementen getragen werden, sind höchstens

\begin{align*} \sum_{u} \rank(u) \cdot s & = \sum_{k=2}^\infty k \cdot (\textnormal{Anzahl der Elemente von Rang $k$}) \cdot s \\ & \leq \sum_{k=2}^\infty k\cdot \frac{n}{2^{k-2}} \dot s = \frac{sn}{2} \ . \end{align*}

Fassen wir nun die Kosten zusammen: jede find-Operation bezahlt maximal $s$, und die Elemente bezahlen zusammen höchstens $sn/2$. Es bleibt die Frage: wie groß kann $s$ werden? Wenn es ein Element $u$ von Dickheit $s$ gibt, dann gilt

\begin{align*} 2 + \log m \geq \rank(\parent(u)) \geq f_s (\rank(u)) \geq f_s(2) \ . \end{align*}

Um ein Gefühl dafür zu bekommen, wie extrem langsam dieses $s$ als Funktion von $n$ wachsen kann, müssen wir uns vor Augen halten, wie schnell $f_s(2)$ als Funktion von $s$ wächst.

Wie groß ist $f_s(2)$?

In Definition 7.6.5 haben wir $f_{i+1}(k)$ als die $k$-fache Anwendung von $f_i$ auf $k$ definiert. Hier ist meine beispielhafte Implementierung von $f_0$, $f_1$, $f_2$ und $f_3$ in Python:

def f_0(k):
    return k+1

def f_1(k):
    result = k 
    for i in range(k):
        result = f_0(result)
    return result

def f_2(k):
    result = k
    for i in range(k):
        result = f_1(result)
    return result

def f_3(k):
    result = k 
    for i in range(k):
        result = f_2(result)
    return result

Da keine rekursiven Funktionsaufrufe vorkommen, können wir alles ohne Funkionsaufruf schreiben, indem wir beispielsweise in der Implementierung von f_3 den Aufruf von f_2 durch den Körper von f_2 selbst ersetzen. Hierbei müssen wir nur auf die richtige Benennung der Variablen achten:

def F_1(k):
    result = k 
    for i in range(k):
        result = result + 1
    return result

def F_2(k):
    result = k 
    for i_1 in range(k):
        result_0 = result 
        for i_0 in range(result):
            result_0 = f_0(result_0)
        result = result_0 
    return result 

def F_3(k):
    result = k 
    for i_2 in range(k):
        result_1 = result 
        for i_1 in range(result):
            result_0 = result_1
            for i_0 in range(result_1):
                result_0 = result_0 + 1 
            result_1 = result_0 
        result = result_1
    return result

Wir sehen: der Code für $f_i$ besteht aus $i$ verschachtelten for-Schleifen, und es ist gar nicht klar, ob man es mit substantiell weniger Schleifen hinkriegt. Natürlich könnten wir für $f_2(k)$ einfach return k * 2**k schreiben, aber der **-Operator führt ja hinter den Kulissen auch nur eine Schleife aus. Unsere Implementierung oben würde für $f_s(k)$ also $s$ for-Schleifen benötigen. Was, wenn wir Code für f(s,k) schreiben wollten? Die Anzahl der for-Schleifen kann ja nicht von s abhängen, da dies ja nun ein Eingabeparameter geworden ist, den wir zur Zeit des Codeschreibens noch nicht kennen. Und in der Tat stellt sich heraus, dass man die Funktion $(s,k) \mapsto f_s(k)$ gar nicht mit einer festen Zahl an for-Schleifen berechnen kann (in einer passend formalisierten Programmiersprache). In der Literatur verwendet man allerdings meist nicht die obige Funktion $f_s(k)$ sondern die Ackermann-Funktion. Diese wurde von Wilhelm Ackermann und Gabriel Sudan genau mit dem Ziel definiert, zu zeigen, dass es eine berechenbare Funktion gibt, die man nicht mit einer konstanten Anzahl an for-Schleifen berechnen kann (da man in den 1920-Jahren noch keine Computer und Programmiersprachen kannte, spricht man in diesem Zusammenhang von eher von primitiv-rekursiven Funktionen als von Programmen mit einer festen Anzahl an for-Schleifen). Wenn Sie mehr über die Ackermann-Funktion lernen wollen, ist Wikipedia ein guter Ausgangspunkt. Auch ich habe in meinen Vorlesungsskripten ein Kapitel darüber: Kapitel 3.3 von Berechenbarkeit und Kreativität.

Wenn rekursive Funktionsaufrufe erlaubt sind, dann ist es sehr einfach, die Funktion $f_s(k)$ zu implementieren:

def f(s,k):
    if s == 0:
        return k+1
    result = k 
    for i in range(k):
        result = f(s-1, result)
    return result