\section[Algorithmus zum Entfernen von Zyklen]{Algorithmus zum schnellen Entfernen aller Zyklen aus einem gerichteten Graphen}
 \label{ch:zyklen}

Die Kategoriestruktur der Wikipedia ist per Konvention als (gerichteter) azyklischer Graph angelegt. In der Praxis kommen durchaus Zyklen vor, die gefunden und entfernt werden müssen, um eine Thesaurus-Relation der Über- \bzw Unterordnung zu erhalten, die den Kriterien für eine \textit{Halbordnung} genügt. Hier wird nun ein Algorithmus vorgestellt, der diese Aufgabe auf einem Graphen mit potentiell mehreren Millionen Knoten effizient bewältigen kann.

Die Grundidee ist, alle möglichen Pfade durch den Graphen zu durchlaufen und dabei auf Zyklen zu untersuchen: Ausgehend von allen "`Wurzeln"' (Knoten ohne eingehende Kanten) wird mittels \textit{Tiefensuche} jeder Knoten besucht; liegt der nächste Knoten bereits auf dem aktuellen Pfad, so ist ein "`Backlink"', und damit ein Zyklus gefunden.

Zu beachten ist, dass jeder Knoten nur einmal besucht werden muss: ist ein Knoten einmal abgearbeitet (und damit auch alle von diesem Knoten aus erreichbaren Knoten), so ist der Knoten nicht (mehr) Teil eines Zyklus, und es ist auch kein Zyklus (mehr) von ihm aus erreichbar. Wird der Knoten also später beim Durchlaufen eines anderen Pfades noch einmal gefunden, muss er nicht mehr bearbeitet werden: Die Tiefensuche beschränkt sich damit auf einen \lingo{Spanning Tree}\index{Spanning Tree} des Graphen. Damit liegt der Aufwand des Algorithmus bei $\mathcal{O}(n)$, wobei $n$ die Anzahl der Knoten ist.

Zunächst wird der Graph so normiert, dass es nur noch eine einzige "`Wurzel"' (Knoten ohne eingehende Kanten) gibt: Es wird ein neuer Knoten  als "`Elternknoten"' aller bisherigen Wurzeln eingefügt; Hat der Graph bislang gar keine Wurzel, so wird ein beliebiger Knoten aus jedem separaten Teilbaum als Kind des künstlichen Wurzelknotens bestimmt. 
\later{FIXME: IMPL! check no island is left over!}

\begin{algorithm}[htbp]
 \caption{Beseitigen von Zyklen}
 \label{alg:zyklen-beseitigen}
 \begin{algorithmic}[1]
  \State{ $G = (V, E)$;}    \Comment Ein Graph mit Knoten V und Kanten E
  \State{ $X = \emptyset$;} \Comment Die Menge von schon bearbeiteten Knoten
  \State{ $P = ()$;}        \Comment Liste, die den aktuellen Pfad speichert
  \State{ $r =$ makeRoot($G$);}   \Comment Künstliche Wurzel einfügen

  \State{ decycle($E, X, P, r$)};

  \Procedure{decycle}{$E$, $X$, $P$, $n$}
    \If{$n \in X$}       \Comment Schon einmal bearbeitet
      \If{$n \in P$}     \Comment Liegt auf dem Pfad
         \State{ $E$.remove($P$.last, $n$);} \Comment Zyklus gefunden!
      \EndIf
    \Else
      \State{ $X \gets X \cup {n}$;} \Comment Als bearbeitet markieren
      \State{ $P$.append($n$);} \Comment Knoten an Pfad anhängen
      \For{$m \in {m: (n, m) \in E}$} \Comment Für alle Kinder
        \State{ decycle($E, X, P, m$);} \Comment Rekursiv aufrufen
      \EndFor
      \State {$P$.remove($n$);} \Comment Knoten von Pfad entfernen
    \EndIf
  \EndProcedure
 \end{algorithmic}
\end{algorithm}

Ausgehend von dieser Wurzel wird nun eine \textit{Tiefensuche} durchgeführt, wobei der Pfad von der Wurzel zum aktuellen Knoten mitgeführt wird. Bei jedem Schritt wird zunächst geprüft, ob der aktuelle Knoten bereits in der Menge der bereits verarbeiteten Knoten ist: Wenn nicht, so wird der Knoten dieser Menge hinzugefügt und dann die Tiefensuche rekursiv fortgesetzt. Wenn der Knoten aber bereits vorher einmal bearbeitet wurde, so wird geprüft, ob er auch Teil des aktuellen Pfades ist, ob also ein "`Backlink"' gefunden wurde. Wenn das so ist, so wird diese Kante entfernt. In jedem Fall aber wird die rekursive Suche abgebrochen, wenn der Knoten schon einmal bearbeitet worden ist.

Der aktuelle Pfad, der von der Wurzel aus durch den Graph genommen wurde, wird bei der Tiefensuche mitgeführt. Ist nun der für den nächsten Schritt vorgesehene Knoten bereits in dem Pfad \textit{zu} diesem Knoten enthalten, so ist ein "`Backlink"', und damit ein Zyklus, gefunden. Um den Zyklus zu beheben, wird nun einfach der soeben gefundene "`Backlink"' entfernt --- auf diese Weise entstehen keine Inseln, alle Knoten auf dem Pfad bleiben weiter von der Wurzel aus erreichbar.

In der Praxis hat sich gezeigt, dass es sich lohnt, den Graphen vor der Anwendung dieses Algorithmus zunächst so zu reduzieren, dass er keine "`losen Enden"' mehr hat. Die Idee ist, dass ein "`Blatt"' (ein Knoten ohne ausgehende Kanten) auf der Suche nach Zyklen nicht zu betrachtet werden braucht. Solche Knoten können also sofort entfernt werden --- und zwar wiederholt, solange, bis keine "`Blätter"' mehr vorhanden sind und jeder verbleibende "`Ast"' des Graphen durch einen Zyklus abgeschlossen wird.

\begin{algorithm}[htbp]
 \caption{Reduktion des Graphen}
 \label{alg:zyklen-reduktion}
 \begin{algorithmic}[1]
  \Procedure{prune}{$G = (V, E)$} \Comment Ein Graph mit Knoten V und Kanten E
    \While {$\exists v \in V: \not \exists (v, w) \in E$} \Comment Solange es blätter gibt
      \For {$v \in V: \not \exists (v, w) \in E$}         \Comment Für jedes Blatt\ldots
        \State{ $G$.remove($v$);}                           \Comment Entferne es
      \EndFor
    \EndWhile
  \EndProcedure
 \end{algorithmic}
\end{algorithm}

Realisieren lässt sich dieser Ansatz wie folgt: Solange es Blätter im Graphen gibt, wird die Menge aller Blätter durchlaufen, und jedes Blatt entfernt (\rrr[Alg.]{alg:zyklen-reduktion}). Die äußere Schleife ist notwendig, da ja durch das Entfernen eines Blattes neue Blätter entstehen können. Der Aufwand der inneren Schleife liegt bei  \var{n} Schritten; die Anzahl von Iterationen der äußeren Schleife ergibt sich aus der Länge des längsten Pfades von einer Wurzel zu einem Blatt --- im schlechtesten Fall also ebenfalls  \var{n}, im Fall eines balancierten Baumes oder eines \lingo{Small-World}\index{Small-World} Graphen, wie der Kategorie-Struktur der Wikipedia \qq{Voss2006tt}{voss05measuring}, aber nur \var{log(n)}.

\subsection*{Beispiel}


 \begin{figure}[htbp]
   \centering
   \subfigure[Ausgangsdaten]{
     \label{abb:zyklen-reduktion-a}
     \includegraphics[height=3cm]{cycles-a}
   }
   \subfigure[Reduzieren]{
     \label{abb:zyklen-reduktion-b}
     \includegraphics[height=3cm]{cycles-b}
   }
   \subfigure[Weiter]{
     \label{abb:zyklen-reduktion-c}
     \includegraphics[height=3cm]{cycles-c}
   }
   \caption{Reduzieren des Graphen}
   \label{abb:zyklen-reduktion}
 \end{figure}

Sei ein Graph mit neun Knoten, \var{n1} -- \var{n9}, gegeben; \var{n1} ist der künstlich hinzugefügte Wurzelknoten, er wurde über den "`\nospell{Proto-Wurzeln}"' \var{n2} und \var{n3} eingehängt. Der Graph enthält zwei (sich überlappende) Zyklen: \var{(n3, n7, n6)} und \var{(n3, n4, n7, n6)}.

Zunächst soll der Graph reduziert werden: Im ersten Schritt werden nun alle Blätter markiert (\var{n5} und \var{n8}, siehe \rrr[Abb.]{abb:zyklen-reduktion-a}) und entfernt. Im ersten Schritt werden wieder alle Blätter markiert (\var{n9}, \rrr[Abb.]{abb:zyklen-reduktion-b}) und entfernt. Nun gibt es keine Blätter mehr (\rrr[Abb.]{abb:zyklen-reduktion-c}) und der eigentliche Algorithmus zum finden von Zyklen wird gestartet.

Ausgehend von der Wurzel \var{n1} wird mittels Tiefensuche der Graph durchlaufen. Bei dem Schritt von \var{n7} zu \var{n6} wird erkannt, dass \var{n7} bereits auf dem aktuellen Pfad \var{(n1, n2, n6, n3, n7)} liegt: somit ist ein Zyklus gefunden, der zu entfernende "`Backlink"' ist die Kante \var{(n7, n6)} (\rrr[Abb.]{abb:zyklen-entfernen-a}). Die Tiefensuche wird dann fortgesetzt: der nächste interessante Schritt ist der von \var{n4} nach \var{n7}: er wird nicht vollzogen, weil \var{n7} als "`schon bearbeitet"' markiert ist. Dasselbe gilt für den Schritt von \var{n1} nach \var{n3}. Damit ist der Algorithmus beendet (\rrr[Abb.]{abb:zyklen-entfernen-b}): alle Zyklen sind beseitigt, die verwendeten Kanten bilden einen \lingo{Spanning Tree} über dem Graphen.
 
 \begin{figure}[htbp]
   \centering
   \subfigure[Zyklus gefunden]{
     \label{abb:zyklen-entfernen-a}
     \includegraphics[height=4cm]{cycles-d}
   }
   \subfigure[Spanning Tree]{
     \label{abb:zyklen-entfernen-b}
     \includegraphics[height=4cm]{cycles-e}
   }
   \caption{Entfernen von Zyklen}
   \label{abb:zyklen-entfernen}
 \end{figure}

\subsection*{Anwendung}

Das hier beschriebene Vorgehen ist also eine Tiefensuche in einem gerichteten Graph, während der Zyklen in diesem Graph gefunden und beseitigt werden. Die naive Tiefensuche wurde optimiert a) durch Beschränkung auf einen \lingo{Spanning Tree} und b) durch Reduktion des Graphen durch iteratives Entfernen aller Blätter. Der resultierende Algorithmus ist geeignet, Zyklen aus großen Graphen effizient zu entfernen. Das wird im Rahmen dieser Arbeit dazu verwendet, unerwünschte zyklische Verknüpfungen aus der Kategoriestruktur der Wikipedia zu entfernen, um zu einer Halbordnung von über- \bzw untergeordneten Konzepten zu gelangen.

Eine Implementation dieses Algorithmus befindet sich in der Klasse \javaid{CycleFinder} im Package \javaid{de.brightbyte.wikiword.store.builder} und wird in der Methode \javaid{deleteBroaderCycles} in der Klasse \javaid{DatabaseWikiWordConceptStoreBuilder} in demselben Package verwendet. Im Experiment ergab sich eine Laufzeit von unter 30 Sekunden für einen Graph mit 65\thinspace000 Knoten und 2 Millionen Kanten, wobei etwa 500 Zyklen gefunden wurden\footnote{Angaben für die Anwendung auf die deutschsprachige Wikipedia}.

