diff options
| -rw-r--r-- | graph/TSP.cpp | 3 | ||||
| -rw-r--r-- | graph/bellmannFord.cpp | 40 | ||||
| -rw-r--r-- | graph/bitonicTSP.cpp | 19 | ||||
| -rw-r--r-- | graph/capacityScaling.cpp | 35 | ||||
| -rw-r--r-- | graph/dijkstra.cpp | 36 | ||||
| -rw-r--r-- | graph/edmondsKarp.cpp | 14 | ||||
| -rw-r--r-- | graph/euler.cpp | 15 | ||||
| -rw-r--r-- | graph/floydWarshall.cpp | 15 | ||||
| -rw-r--r-- | graph/graph.tex | 57 | ||||
| -rw-r--r-- | graph/maxCarBiMatch.cpp | 10 | ||||
| -rw-r--r-- | graph/minCostMaxFlow.cpp | 21 | ||||
| -rw-r--r-- | graph/scc.cpp | 32 | ||||
| -rw-r--r-- | tcr.pdf | bin | 221901 -> 226676 bytes | |||
| -rw-r--r-- | tcr.tex | 18 |
14 files changed, 199 insertions, 116 deletions
diff --git a/graph/TSP.cpp b/graph/TSP.cpp index c38cbb2..0161d3c 100644 --- a/graph/TSP.cpp +++ b/graph/TSP.cpp @@ -1,4 +1,5 @@ -//nodes[0] has to be the start and end node. +// Laufzeit: O(n*2^n) +// nodes[0] ist Start- und Endknoten. vector<vector<int>> dist; vector<int> TSP() { int n = dist.size(), m = 1 << n; diff --git a/graph/bellmannFord.cpp b/graph/bellmannFord.cpp index 94fa034..45efd6b 100644 --- a/graph/bellmannFord.cpp +++ b/graph/bellmannFord.cpp @@ -1,18 +1,30 @@ -//n = number of vertices, edges is vector of edges -dist.assign(n, INF); dist[0] = 0; -parent.assign(n, -1); -for (i = 0; i < n - 1; i++) { - for (j = 0; j < (int)edges.size(); j++) { - if (dist[edges[j].from] + edges[j].cost < dist[edges[j].to]) { - dist[edges[j].to] = dist[edges[j].from] + edges[j].cost; - parent[edges[j].to] = edges[j].from; +// Laufzeit: O(|V|*|E|) +struct edge { + int from; int to; int cost; + edge () {}; + edge (int from, int to, int cost) : from(from), to(to), cost(cost) {}; +}; + +vector<edge> edges; // Kanten einfügen! +vector<int> dist, parent; + +void bellmannFord() { + dist.assign(NUM_VERTICES, INF); dist[0] = 0; + parent.assign(NUM_VERTICES, -1); + for (int i = 0; i < NUM_VERTICES - 1; i++) { + for (int j = 0; j < (int)edges.size(); j++) { + if (dist[edges[j].from] + edges[j].cost < dist[edges[j].to]) { + dist[edges[j].to] = dist[edges[j].from] + edges[j].cost; + parent[edges[j].to] = edges[j].from; + } } } -} -//now dist and parent are correct shortest paths -//next lines check for negative cycles -for (j = 0; j < (int)edges.size(); j++) { - if (dist[edges[j].from] + edges[j].cost < dist[edges[j].to]) { - //NEGATIVE CYCLE found + + // "dist" und "parent" sind korrekte kürzeste Pfade. + // Folgende Zeilen prüfen nur negative Kreise. + for (int j = 0; j < (int)edges.size(); j++) { + if (dist[edges[j].from] + edges[j].cost < dist[edges[j].to]) { + // Negativer Kreis gefunden. + } } } diff --git a/graph/bitonicTSP.cpp b/graph/bitonicTSP.cpp index 4e4dda0..bf01f9e 100644 --- a/graph/bitonicTSP.cpp +++ b/graph/bitonicTSP.cpp @@ -1,13 +1,16 @@ -vector< vector<double> > dp; //initialize with -1 -vector< vector<double> > dist; //initialize with all dists between points -vector<int> lr, rl; //left-to-right and right-to-left paths -int n; //number of points -double get(int p1, int p2) { //call get(0, 0) to get length of shortest bitonic route +// Laufzeit: O(|V|^2) +vector< vector<double> > dp; // Initialisiere mit -1 +vector< vector<double> > dist; // Initialisiere mit Entfernungen zwischen Punkten. +vector<int> lr, rl; // Links-nach-rechts und rechts-nach-links Pfade. +int n; // #Knoten + +// get(0, 0) gibt die Länge der kürzesten bitonischen Route. +double get(int p1, int p2) { int v = max(p1, p2) + 1; if (v == n - 1) return dist[p1][v] + dist[v][p2]; if (dp[p1][p2] > -0.5) return dp[p1][p2]; double tryLR = dist[p1][v] + get(v, p2), tryRl = dist[v][p2] + get(p1, v); - if (tryLR < tryRL) lr.push_back(v); //reconstructs the path, pushes v to rl if the choice does not matter - else rl.push_back(v); //change this if needed + if (tryLR < tryRL) lr.push_back(v); // Baut die Pfade auf. Fügt v zu rl hinzu, falls beide gleich teuer. + else rl.push_back(v); // Änder das, falls nötig. return min(tryLR, tryRL); -}
\ No newline at end of file +} diff --git a/graph/capacityScaling.cpp b/graph/capacityScaling.cpp new file mode 100644 index 0000000..2349ddd --- /dev/null +++ b/graph/capacityScaling.cpp @@ -0,0 +1,35 @@ +// Ford Fulkerson with capacity scaling. +// Laufzeit: O(|E|^2 * log C) +const int MAXN = 190000, MAXC = 1<<29; +struct edge { int dest, capacity, rev; }; +vector<edge> adj[MAXN]; +int vis[MAXN], target, iter, cap; + +void addedge(int x, int y, int c) { + adj[x].push_back(edge {y, c, (int)adj[y].size()}); + adj[y].push_back(edge {x, 0, (int)adj[x].size() - 1}); +} + +bool dfs(int x) { + if (x == target) return 1; + if (vis[x] == iter) return 0; + vis[x] = iter; + for (edge& e: adj[x]) + if (e.capacity >= cap && dfs(e.dest)) { + e.capacity -= cap; + adj[e.dest][e.rev].capacity += cap; + return 1; + } + return 0; +} + +int maxflow(int S, int T) { + cap = MAXC, target = T; + int flow = 0; + while(cap) { + while(++iter, dfs(S)) + flow += cap; + cap /= 2; + } + return flow; +}
\ No newline at end of file diff --git a/graph/dijkstra.cpp b/graph/dijkstra.cpp index 1d4f7a1..649cf6e 100644 --- a/graph/dijkstra.cpp +++ b/graph/dijkstra.cpp @@ -1,20 +1,26 @@ -priority_queue<ii, vector<ii>, greater<ii> > pq; -vector<int> dist; -dist.assign(NUM_VERTICES, INF); -dist[START] = 0; -pq.push(ii(0, START)); +// Laufzeit: O((|E|+|V|)*log |V|) +void dijkstra(int start) { + priority_queue<ii, vector<ii>, greater<ii> > pq; + vector<int> dist, parent; + dist.assign(NUM_VERTICES, INF); + parent.assign(NUM_VERTICES, -1); -while (!pq.empty()) { - ii front = pq.top(); pq.pop(); - int curNode = front.second, curDist = front.first; - - if (curDist > dist[curNode]) continue; - - for (int i = 0; i < (int)adjlist[curNode].size(); i++) { - int nextNode = adjlist[curNode][i].first, nextDist = curDist + adjlist[curNode][i].second; + dist[start] = 0; + pq.push(ii(0, start)); + + while (!pq.empty()) { + ii front = pq.top(); pq.pop(); + int curNode = front.second, curDist = front.first; + + if (curDist > dist[curNode]) continue; - if (nextDist < dist[nextNode]) { - dist[nextNode] = nextDist; pq.push(ii(nextDist, nextNode)); + for (int i = 0; i < (int)adjlist[curNode].size(); i++) { + int nextNode = adjlist[curNode][i].first, nextDist = curDist + adjlist[curNode][i].second; + + if (nextDist < dist[nextNode]) { + dist[nextNode] = nextDist; parent[nextNode] = curNode; + pq.push(ii(nextDist, nextNode)); + } } } } diff --git a/graph/edmondsKarp.cpp b/graph/edmondsKarp.cpp index 9181062..dcfd85b 100644 --- a/graph/edmondsKarp.cpp +++ b/graph/edmondsKarp.cpp @@ -1,7 +1,8 @@ -int s, t, f; //source, target, single flow -int res[MAX_V][MAX_V]; //adj-matrix +// Laufzeit: O(|V|*|E|^2) +int s, t, f; // Quelle, Senke, single flow +int res[MAX_V][MAX_V]; vector< vector<int> > adjlist; -int p[MAX_V]; //bfs spanning tree +int p[MAX_V]; void augment(int v, int minEdge) { if (v == s) { f = minEdge; return; } @@ -10,14 +11,15 @@ void augment(int v, int minEdge) { res[p[v]][v] -= f; res[v][p[v]] += f; }} -int maxFlow() { //first inititalize res, adjList, s and t +// Initialisiere res, adjList, s und t. +int maxFlow() { int mf = 0; while (true) { f = 0; bitset<MAX_V> vis; vis[s] = true; queue<int> q; q.push(s); memset(p, -1, sizeof(p)); - while (!q.empty()) { //BFS + while (!q.empty()) { // BFS int u = q.front(); q.pop(); if (u == t) break; for (int j = 0; j < (int)adjlist[u].size(); j++) { @@ -26,7 +28,7 @@ int maxFlow() { //first inititalize res, adjList, s and t vis[v] = true; q.push(v); p[v] = u; }}} - augment(t, INF); //add found path to max flow + augment(t, INF); // Pfad zu Fluss hinzufügen. if (f == 0) break; mf += f; } diff --git a/graph/euler.cpp b/graph/euler.cpp index 74b3399..6551ac3 100644 --- a/graph/euler.cpp +++ b/graph/euler.cpp @@ -1,3 +1,4 @@ +// Laufzeit: O(|V|+|E|) vector< vector<int> > adjlist; vector< vector<int> > otherIdx; vector<int> cycle; @@ -14,9 +15,9 @@ void swapEdges(int n, int a, int b) { // Vertauscht Kanten mit Indizes a und b v otherIdx[neighB][idxNeighB] = a; } -void removeEdge(int n, int i) { // Entfernt Kante i von Knoten n (und die zugehoerige Rueckwaertskante). +void removeEdge(int n, int i) { // Entfernt Kante i von Knoten n (und die zugehörige Rückwärtskante). int other = adjlist[n][i]; - if (other == n) { //Schlingen + if (other == n) { //Schlingen. validIdx[n]++; return; } @@ -28,14 +29,14 @@ void removeEdge(int n, int i) { // Entfernt Kante i von Knoten n (und die zugeho validIdx[other]++; } -//findet Eulerzyklus an Knoten n startend -//teste vorher, dass Graph zusammenhaengend ist! (isolierte Punkte sind ok) -//teste vorher, ob Eulerzyklus ueberhaupt existiert! +// Findet Eulerzyklus an Knoten n startend. +// Teste vorher, dass Graph zusammenhängend ist! Was ist mit isolierten Knoten? +// Teste vorher, ob Eulerzyklus überhaupt existiert! void euler(int n) { while (validIdx[n] < (int)adjlist[n].size()) { int nn = adjlist[n][validIdx[n]]; removeEdge(n, validIdx[n]); euler(nn); } - cycle.push_back(n); //Zyklus am Ende in cycle -}
\ No newline at end of file + cycle.push_back(n); // Zyklus am Ende in cycle (umgekehrte Reihenfolge). +} diff --git a/graph/floydWarshall.cpp b/graph/floydWarshall.cpp index f5c950d..30d463a 100644 --- a/graph/floydWarshall.cpp +++ b/graph/floydWarshall.cpp @@ -1,8 +1,11 @@ -//initialize adjmat, adjmat[i][i] = 0, adjmat[i][j] = INF if no edge is between i and j, length otherwise -for (k = 0; k < MAX_V; k++) { - for (i = 0; i < MAX_V; i++) { - for (j = 0; j < MAX_V; j++) { - if (adjmat[i][k] + adjmat[k][j] < adjmat[i][j]) adjmat[i][j] = adjmat[i][k] + adjmat[k][j]; +// Laufzeit: O(|V|^3) +// Initialize adjmat: adjmat[i][i] = 0, adjmat[i][j] = INF if no edge is between i and j, length otherwise. +void floydWarshall() { + for (k = 0; k < NUM_VERTICES; k++) { + for (i = 0; i < NUM_VERTICES; i++) { + for (j = 0; j < NUM_VERTICES; j++) { + if (adjmat[i][k] + adjmat[k][j] < adjmat[i][j]) adjmat[i][j] = adjmat[i][k] + adjmat[k][j]; + } } } -}
\ No newline at end of file +} diff --git a/graph/graph.tex b/graph/graph.tex index 38deee6..7a85337 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -1,11 +1,17 @@ \section{Graphen} \subsection{Minimale Spannbäume} +% Add an implementation. Benutze Algorithmus von \textsc{Kruskal} oder Algorithmus von \textsc{Prim}. -\begin{description} - \item[Schnitteigenschaft] Für jeden Schnitt $C$ im Graphen gilt: Gibt es eine Kante $e$, die echt leichter ist als alle anderen Schnittkanten, so gehört diese zu allen minimalen Spannbäumen. ($\Rightarrow$ Die leichteste Kante in einem Schnitt kann in einem minimalen Spannbaum verwendet werden.) - \item[Kreiseigenschaft] Für jeden Kreis $K$ im Graphen gilt: Die schwerste Kante auf dem Kreis ist nicht Teil des minimalen Spannbaums. -\end{description} + +\paragraph{Schnitteigenschaft} +Für jeden Schnitt $C$ im Graphen gilt: +Gibt es eine Kante $e$, die echt leichter ist als alle anderen Schnittkanten, so gehört diese zu allen minimalen Spannbäumen. +($\Rightarrow$ Die leichteste Kante in einem Schnitt kann in einem minimalen Spannbaum verwendet werden.) + +\paragraph{Kreiseigenschaft} +Für jeden Kreis $K$ im Graphen gilt: +Die schwerste Kante auf dem Kreis ist nicht Teil des minimalen Spannbaums. \subsection{Kürzeste Wege} @@ -14,20 +20,23 @@ Kürzeste Pfade in Graphen ohne negative Kanten. \lstinputlisting{graph/dijkstra.cpp} \subsubsection{\textsc{Bellmann-Ford}-Algorithmus} -Kürzestes Pfade in Graphen mit negativen Kanten. Erkennt negative Zyklen. +Kürzestes Pfade in Graphen mit negativen Kanten. +Erkennt negative Zyklen. \lstinputlisting{graph/bellmannFord.cpp} \subsubsection{\textsc{Floyd-Warshall}-Algorithmus} -Alle kürzesten Pfade im Graphen. \lstinputlisting{graph/floydWarshall.cpp} \begin{itemize} - \item \textsc{Floyd-Warshall} findet auch negative Kreise. Es existiert genau dann ein negativer Kreis, wenn \lstinline{dist[i][i] < 0} ist. - \item Evtl. überschreibt die Eingabe die Nullen auf der Hauptdiagonalen. + \item \textsc{Floyd-Warshall} findet auch negative Kreise. + Es existiert genau dann ein negativer Kreis, wenn \lstinline{dist[i][i] < 0} ist. + \item \textbf{Evtl. überschreibt die Eingabe die Nullen auf der Hauptdiagonalen.} + Das ist fast immer ungewollt! \end{itemize} \subsection{Strongly Connected Components (\textsc{Tarjans}-Algorithmus)} \lstinputlisting{graph/scc.cpp} +% TODO (pjungeblut): This has errors for bridges! \subsection{Artikulationspunkte und Brücken} \lstinputlisting{graph/articulationPoints.cpp} @@ -36,26 +45,38 @@ Alle kürzesten Pfade im Graphen. \item Zyklus existiert, wenn jeder Knoten geraden Grad hat (ungerichtet), bzw. bei jedem Knoten Ein- und Ausgangsgrad übereinstimmen (gerichtet). \item Pfad existiert, wenn alle bis auf (maximal) zwei Knoten geraden Grad haben (ungerichtet), bzw. bei allen Knoten bis auf zwei Ein- und Ausgangsgrad übereinstimmen, wobei einer eine Ausgangskante mehr hat (Startknoten) und einer eine Eingangskante mehr hat (Endknoten). \item \textbf{Je nach Aufgabenstellung überprüfen, wie isolierte Punkte interpretiert werden sollen.} - \item Der Code unten läuft in Linearzeit. Wenn das nicht notwenidg ist (oder bestimmte Sortierungen verlangt werden), gehts mit einem \lstinline{set} einfacher. + \item Der Code unten läuft in Linearzeit. + Wenn das nicht notwenidg ist (oder bestimmte Sortierungen verlangt werden), gehts mit einem \lstinline{set} einfacher. \end{itemize} \begin{figure}[h] -\begin{lstlisting} -VISIT(v): - forall e=(v,w) in E - delete e from E - VISIT(w) - print e -\end{lstlisting} -\caption{Idee für Eulerzyklen} + \begin{lstlisting} + VISIT(v): + forall e=(v,w) in E + delete e from E + VISIT(w) + print e + \end{lstlisting} + \caption{Idee für Eulerzyklen} \end{figure} \lstinputlisting{graph/euler.cpp} +\paragraph{Achtung:} +\begin{itemize} + \item Die Ausgabe erfolgt in falscher Reihenfolge. + \item Algorithmus schlägt nicht fehl, falls kein Eulerzyklus existiert. + Die Existenz muss separat geprüft werden. +\end{itemize} \subsection{Lowest Common Ancestor} \lstinputlisting{graph/LCA.cpp} -\subsection{Max-Flow (\textsc{Edmonds-Karp}-Algorithmus)} +\subsection{Max-Flow} + +\subsubsection{\textsc{Edmonds-Karp}-Algorithmus} \lstinputlisting{graph/edmondsKarp.cpp} +\subsubsection{Capacity Scaling} +\lstinputlisting{graph/capacityScaling.cpp} + \subsubsection{Maximum Edge Disjoint Paths} Finde die maximale Anzahl Pfade von $s$ nach $t$, die keine Kante teilen. \begin{enumerate} diff --git a/graph/maxCarBiMatch.cpp b/graph/maxCarBiMatch.cpp index fb9cb3d..c086abc 100644 --- a/graph/maxCarBiMatch.cpp +++ b/graph/maxCarBiMatch.cpp @@ -1,5 +1,6 @@ -vector< vector<int> > adjlist; //seems to work directed, from left to right -vector<int> pairs; //for every node, stores the matching node on the other side or -1 +// Laufzeit: O(n*(|V|+|E|)) +vector< vector<int> > adjlist; // Gerichtete Kanten, von links nach rechts. +vector<int> pairs; // Zu jedem Knoten der gematchte Knoten rechts, oder -1. vector<bool> visited; bool dfs(int i) { @@ -13,12 +14,13 @@ bool dfs(int i) { return false; } -int kuhn(int n, int m) { // n = nodes on left side (numbered 0..n-1), m = nodes on the right side +// n = #Knoten links (0..n-1), m = #Knoten rechts +int kuhn(int n, int m) { pairs.assign(n + m, -1); int ans = 0; for (int i = 0; i < n; i++) { visited.assign(n + m, false); ans += dfs(i); } - return ans; //size of the MCBM + return ans; // Größe des Matchings. } diff --git a/graph/minCostMaxFlow.cpp b/graph/minCostMaxFlow.cpp index 56e6223..a4e997f 100644 --- a/graph/minCostMaxFlow.cpp +++ b/graph/minCostMaxFlow.cpp @@ -1,23 +1,24 @@ -int s, t, f, c; //source, target, single flow, single cost -int res[MAX_V][MAX_V]; //residual graph -vector<edge> edges; //edge list -vector<int> p, dist; //parent pointer, dist field +// Laufzeit: O(|V|^2 * |E|^2) +int s, t, f, c; // Quelle, Senke, single flow, single cost +int res[MAX_V][MAX_V]; +vector<edge> edges; +vector<int> p, dist; void augment(int v, int minEdge) { - if (v == s) { f = minEdge; c = minEdge * dist[t]; return; } //c = minEdge * dist[t] added + if (v == s) { f = minEdge; c = minEdge * dist[t]; return; } // c = minEdge * dist[t] added else if (p[v] != -1) { augment(p[v], min(minEdge, res[p[v]][v])); res[p[v]][v] -= f; res[v][p[v]] += f; }} -//first inititalize res, edges, s and t -int minCostMaxFlow(int v) { //v is number of vertices +// Initialisiere res, edges, s und t. +int minCostMaxFlow(int v) { // v = #Knoten int mf = 0, mc = 0, i, j; while (true) { f = 0; c = 0; dist.assign(v, INF); dist[s] = 0; p.assign(v, -1); - for (i = 0; i < v - 1; i++) { //Bellmann-Ford + for (i = 0; i < v - 1; i++) { // Bellmann-Ford. for (j = 0; j < (int)edges.size(); j++) { if (res[edges[j].from][edges[j].to] > 0 && dist[edges[j].from] + edges[j].cost < dist[edges[j].to]) { dist[edges[j].to] = dist[edges[j].from] + edges[j].cost; @@ -26,9 +27,9 @@ int minCostMaxFlow(int v) { //v is number of vertices } } - augment(t, INF); //add found path to max flow, method as in EdmondsKarp + augment(t, INF); // Gefunden Pfad zum Fluss hinzufügen. if (f == 0) break; mf += f; mc += c; } - return mf; //returns max flow, for in cost, use mc + return mf; // mf is der maximale Fluss, mc sind die minimalen Kosten. }
\ No newline at end of file diff --git a/graph/scc.cpp b/graph/scc.cpp index b33616b..f2883ef 100644 --- a/graph/scc.cpp +++ b/graph/scc.cpp @@ -1,4 +1,5 @@ -int counter, sccCounter, n; //n == number of vertices +// Laufzeit: O(|V|+|E|) +int counter, sccCounter; vector<bool> visited, inStack; vector< vector<int> > adjlist; vector<int> d, low, sccs; @@ -6,11 +7,8 @@ stack<int> s; void visit(int v) { visited[v] = true; - d[v] = counter; - low[v] = counter; - counter++; - inStack[v] = true; - s.push(v); + d[v] = counter; low[v] = counter; counter++; + inStack[v] = true; s.push(v); for (int i = 0; i < (int)adjlist[v].size(); i++) { int u = adjlist[v][i]; @@ -25,9 +23,7 @@ void visit(int v) { if (d[v] == low[v]) { int u; do { - u = s.top(); - s.pop(); - inStack[u] = false; + u = s.top(); s.pop(); inStack[u] = false; sccs[u] = sccCounter; } while(u != v); sccCounter++; @@ -35,20 +31,20 @@ void visit(int v) { } void scc() { - //read adjlist - - visited.clear(); visited.assign(n, false); - d.clear(); d.resize(n); - low.clear(); low.resize(n); - inStack.clear(); inStack.assign(n, false); - sccs.clear(); sccs.resize(n); + // Initialisiere adjlist! + visited.clear(); visited.assign(NUM_VERTICES, false); + d.clear(); d.resize(NUM_VERTICES); + low.clear(); low.resize(NUM_VERTICES); + inStack.clear(); inStack.assign(NUM_VERTICES, false); + sccs.clear(); sccs.resize(NUM_VERTICES); counter = 0; sccCounter = 0; - for (i = 0; i < n; i++) { + for (i = 0; i < NUM_VERTICES; i++) { if (!visited[i]) { visit(i); } } - //sccs has the component for each vertex + // sccCounter ist Anzahl der starkem Zusammenhangskomponenten. + // sccs enthält den Index der SCC für jeden Knoten. }
\ No newline at end of file Binary files differ@@ -34,7 +34,7 @@ breakautoindent=true, breakatwhitespace=false, postbreak=\space, - tabsize=4, + tabsize=2, basicstyle=\ttfamily\footnotesize, showspaces=false, showstringspaces=false, @@ -46,14 +46,14 @@ } % Listings doesn't support UTF8. This is just enough for German umlauts. \lstset{literate=% - {Ö}{{\"O}}1 - {Ä}{{\"A}}1 - {Ü}{{\"U}}1 - {ß}{{\ss}}1 - {ü}{{\"u}}1 - {ä}{{\"a}}1 - {ö}{{\"o}}1 - {~}{{\textasciitilde}}1 + {Ö}{{\"O}}1 + {Ä}{{\"A}}1 + {Ü}{{\"U}}1 + {ß}{{\ss}}1 + {ü}{{\"u}}1 + {ä}{{\"a}}1 + {ö}{{\"o}}1 + {~}{{\textasciitilde}}1 } % Don't waste space at the page borders. |